Share Email Print

Proceedings Paper

Sublinear approximation of signals
Author(s): Anna C. Gilbert; Martin J. Strauss; Joel A. Tropp; Roman Vershynin
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

It has recently been observed that sparse and compressible signals can be sketched using very few nonadaptive linear measurements in comparison with the length of the signal. This sketch can be viewed as an embedding of an entire class of compressible signals into a low-dimensional space. In particular, d-dimensional signals with m nonzero entries (m-sparse signals) can be embedded in O(m log d) dimensions. To date, most algorithms for approximating or reconstructing the signal from the sketch, such as the linear programming approach proposed by Candes-Tao and Donoho, require time polynomial in the signal length. This paper develops a new method, called Chaining Pursuit, for sketching both m-sparse and compressible signals with O(m polylog d) nonadaptive linear measurements. The algorithm can reconstruct the original signal in time O(m polylog d) with an error proportional to the optimal m-term approximation error. In particular, m-sparse signals are recovered perfectly and compressible signals are recovered with polylogarithmic distortion. Moreover, the algorithm can operate in small space O(m polylog d), so it is appropriate for streaming data.

Paper Details

Date Published: 4 May 2006
PDF: 9 pages
Proc. SPIE 6232, Intelligent Integrated Microsystems, 623206 (4 May 2006); doi: 10.1117/12.669596
Show Author Affiliations
Anna C. Gilbert, Univ. of Michigan (United States)
Martin J. Strauss, Univ. of Michigan (United States)
Joel A. Tropp, Univ. of Michigan (United States)
Roman Vershynin, Univ. of California, Davis (United States)

Published in SPIE Proceedings Vol. 6232:
Intelligent Integrated Microsystems
Ravindra A. Athale; John C. Zolper, Editor(s)

© SPIE. Terms of Use
Back to Top