A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees

Details A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees

2008-06-24

arxiv.org/abs/0806.3799v2

Computer Science

Information Theory

Scientific paper

Compressed Sensing aims to capture attributes of a sparse signal using very few measurements. Cand\`{e}s and Tao showed that sparse reconstruction is possible if the sensing matrix acts as a near isometry on all $\boldsymbol{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 $\boldsymbol{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 \srm codes (binary chirps) and a $\boldsymbol{k}$-sparse reconstruction algorithm with sublinear complexity. In the presence of stochastic noise in the data domain, this paper derives bounds on the $\boldsymbol{\ell_2}$ accuracy of approximation in terms of the $\boldsymbol{\ell_2}$ norm of the measurement noise and the accuracy of the best $\boldsymbol{k}$-sparse approximation, also measured in the $\boldsymbol{\ell_2}$ norm. This type of $\boldsymbol{\ell_2 /\ell_2}$ bound is tighter than the standard $\boldsymbol{\ell_2 /\ell_1}$ or $\boldsymbol{\ell_1/ \ell_1}$ bounds.

Affiliated with

Also associated with

No associations

Rating

A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-97112