On the efficiency of the Orthogonal Matching Pursuit in compressed sensing
Sbornik. Mathematics, Tome 203 (2012) no. 2, pp. 183-195
Voir la notice de l'article provenant de la source Math-Net.Ru
The paper shows that if a matrix $\Phi$ has the restricted isometry property (RIP) of order $[CK^{1.2}]$ with isometry constant $\delta=cK^{-0.2}$ and if its coherence is less than $1/(20K^{0.8})$, then the Orthogonal Matching Pursuit (the Orthogonal Greedy Algorithm) is capable to exactly recover an arbitrary $K$-sparse signal from the compressed sensing $y=\Phi x$ in at most $[CK^{1.2}]$ iterations. As a result, an arbitrary
$K$-sparse signal can be recovered by the Orthogonal Matching Pursuit from $M=O(K^{1.6}\log N)$ measurements.
Bibliography: 23 titles.
Keywords:
Orthogonal Matching Pursuit, compressed sensing, coherence, restricted isometry property, sparsity.
@article{SM_2012_203_2_a1,
author = {E. D. Livshits},
title = {On the efficiency of the {Orthogonal} {Matching} {Pursuit} in compressed sensing},
journal = {Sbornik. Mathematics},
pages = {183--195},
publisher = {mathdoc},
volume = {203},
number = {2},
year = {2012},
language = {en},
url = {http://geodesic.mathdoc.fr/item/SM_2012_203_2_a1/}
}
E. D. Livshits. On the efficiency of the Orthogonal Matching Pursuit in compressed sensing. Sbornik. Mathematics, Tome 203 (2012) no. 2, pp. 183-195. http://geodesic.mathdoc.fr/item/SM_2012_203_2_a1/