A Caltech Library Service

Algorithmic linear dimension reduction in the ℓ_1 norm for sparse vectors

Gilbert, A. C. and Strauss, M. J. and Tropp, J. A. and Vershynin, R. (2006) Algorithmic linear dimension reduction in the ℓ_1 norm for sparse vectors. . (Submitted)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


This paper develops a new method for recovering m-sparse signals that is simultaneously uniform and quick. We present a reconstruction algorithm whose run time, O(m log^2(m) log^2(d)), is sublinear in the length d of the signal. The reconstruction error is within a logarithmic factor (in m) of the optimal m-term approximation error in l_1. In particular, the algorithm recovers m-sparse signals perfectly and noisy signals are recovered with polylogarithmic distortion. Our algorithm makes O(m log^2 (d)) measurements, which is within a logarithmic factor of optimal. We also present a small-space implementation of the algorithm. These sketching techniques and the corresponding reconstruction algorithms provide an algorithmic dimension reduction in the l_1 norm. In particular, vectors of support m in dimension d can be linearly embedded into O(m log^2 d) dimensions with polylogarithmic distortion. We can reconstruct a vector from its low-dimensional sketch in time O(m log^2(m) log^2(d)). Furthermore, this reconstruction is stable and robust under small perturbations.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Tropp, J. A.0000-0003-1024-1791
Additional Information:ACG is an Alfred P. Sloan Research Fellow and has been supported in part by NSF DMS 0354600. MJS has been supported in part by NSF DMS 0354600 and NSF DMS 0510203. JAT has been supported by NSF DMS 0503299. ACG, MJS, and JAT have been partially supported by DARPA ONR N66001-06-1-2011. RV is an Alfred P. Sloan Research Fellow. He was also partially supported by the NSF grant DMS 0401032.
Funding AgencyGrant Number
Alfred P. Sloan FoundationUNSPECIFIED
Office of Naval Research (ONR)N66001-06-1-2011
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Subject Keywords:Approximation, embedding, dimension reduction, sketching, sparse approximation, sublinear algorithms
Record Number:CaltechAUTHORS:20180828-150010838
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:89264
Deposited By: Tony Diaz
Deposited On:28 Aug 2018 22:24
Last Modified:03 Oct 2019 20:14

Repository Staff Only: item control page