Advertisement
Published in:
2012 | OriginalPaper | Chapter
Sparse Recovery Algorithms: Sufficient Conditions in Terms of Restricted Isometry Constants
Author : Simon Foucart
Published in: Approximation Theory XIII: San Antonio 2010
Publisher: Springer New York
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We review three recovery algorithms used in Compressive Sensing for the reconstruction
s
-sparse vectors
x
∈
ℂ
N
from the mere knowledge of linear measurements
y
=
A
x
∈
ℂ
m
,
m
<
N
. For each of the algorithms, we derive improved conditions on the restricted isometry constants of the measurement matrix
A
that guarantee the success of the reconstruction. These conditions are δ
2
s
<0.4652 for basis pursuit, δ
3
s
<0.5 and δ
2
s
<0.25 for iterative hard thresholding, and δ
4
s
<0.3843 for compressive sampling matching pursuit. The arguments also applies to almost sparse vectors and corrupted measurements. The analysis of iterative hard thresholding is surprisingly simple. The analysis of basis pursuit features a new inequality that encompasses several inequalities encountered in Compressive Sensing.