Skip to main content

A sublinear algorithm for sparse reconstruction with ℓ2/ ℓ2 recovery guarantees

Publication ,  Journal Article
Calderbank, R; Howard, S; Jafarpour, S
Published in: CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing
December 1, 2009

Compressed Sensing aims to capture attributes of a sparse signal using very few measurements. Candès and Tao showed that sparse reconstruction is possible if the sensing matrix acts as a near isometry on all k-sparse signals. This property holds with overwhelming probability if the entries of the matrix are generated by an iid Gaussian or Bernoulli process. There has been significant recent interest in an alternative signal processing framework; exploiting deterministic sensing matrices that with overwhelming probability act as a near isometry on k-sparse vectors with uniformly random support, a geometric condition that is called the Statistical Restricted Isometry Property or StRIP. This paper considers a family of deterministic sensing matrices satisfying the StRIP that are based on Delsarte-Goethals Codes codes (binary chirps) and a k-sparse reconstruction algorithm with sublinear complexity. In the presence of stochastic noise in the data domain, this paper derives bounds on the ℓ2 accuracy of approximation in terms of the ℓ2 norm of the measurement noise and the accuracy of the best k-sparse approximation, also measured in the ℓ2 norm. This type of ℓ2/ℓ2 bound is tighter than the standard ℓ2/ℓ1 or ℓ1/ℓ1 bounds. © 2009 IEEE.

Duke Scholars

Published In

CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing

DOI

Publication Date

December 1, 2009

Start / End Page

209 / 212
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Calderbank, R., Howard, S., & Jafarpour, S. (2009). A sublinear algorithm for sparse reconstruction with ℓ2/ ℓ2 recovery guarantees. CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, 209–212. https://doi.org/10.1109/CAMSAP.2009.5413298
Calderbank, R., S. Howard, and S. Jafarpour. “A sublinear algorithm for sparse reconstruction with ℓ2/ ℓ2 recovery guarantees.” CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, December 1, 2009, 209–12. https://doi.org/10.1109/CAMSAP.2009.5413298.
Calderbank R, Howard S, Jafarpour S. A sublinear algorithm for sparse reconstruction with ℓ2/ ℓ2 recovery guarantees. CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2009 Dec 1;209–12.
Calderbank, R., et al. “A sublinear algorithm for sparse reconstruction with ℓ2/ ℓ2 recovery guarantees.” CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Dec. 2009, pp. 209–12. Scopus, doi:10.1109/CAMSAP.2009.5413298.
Calderbank R, Howard S, Jafarpour S. A sublinear algorithm for sparse reconstruction with ℓ2/ ℓ2 recovery guarantees. CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2009 Dec 1;209–212.

Published In

CAMSAP 2009 - 2009 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing

DOI

Publication Date

December 1, 2009

Start / End Page

209 / 212