2012 | OriginalPaper | Buchkapitel
Sparse Recovery Algorithms: Sufficient Conditions in Terms of Restricted Isometry Constants
verfasst von : Simon Foucart
Erschienen in: Approximation Theory XIII: San Antonio 2010
Verlag: Springer New York
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.