Geodesic
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. 
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/
@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},
     year = {2012},
     volume = {203},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2012_203_2_a1/}
}
TY  - JOUR
AU  - E. D. Livshits
TI  - On the efficiency of the Orthogonal Matching Pursuit in compressed sensing
JO  - Sbornik. Mathematics
PY  - 2012
SP  - 183
EP  - 195
VL  - 203
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SM_2012_203_2_a1/
LA  - en
ID  - SM_2012_203_2_a1
ER  - 
%0 Journal Article
%A E. D. Livshits
%T On the efficiency of the Orthogonal Matching Pursuit in compressed sensing
%J Sbornik. Mathematics
%D 2012
%P 183-195
%V 203
%N 2
%U http://geodesic.mathdoc.fr/item/SM_2012_203_2_a1/
%G en
%F SM_2012_203_2_a1

[1] R. G. Baraniuk, “Compressive sensing”, IEEE Signal Processing Magazine, 24:4 (2007), 118–121 | DOI

[2] E. J. Candès, “Compressive sampling”, Proceedings of the international congress of mathematicians (Madrid, Spain, 2006), v. III, Invited lectures, Eur. Math. Soc., Zürich, 2006, 1433–1452 | MR | Zbl

[3] D. L. Donoho, “Compressed sensing”, IEEE Trans. Inform. Theory, 52:4 (2006), 1289–1306 | DOI | MR

[4] B. S. Kashin, V. N. Temlyakov, “A remark on compressed sensing”, Math. Notes, 82:5–6 (2007), 748–755 | DOI | MR | Zbl

[5] S. S. Chen, D. L. Donoho, M. A. Saunders, “Atomic decomposition by basis pursuit”, SIAM Rev., 43:1 (2001), 129–159 | DOI | MR | Zbl

[6] V. N. Temlyakov, “Greedy approximation”, Acta Numer., 17 (2008), 235–409 | DOI | MR | Zbl

[7] S. G. Mallat, Z. Zhang, “Matching pursuit with time-frequency dictionaries”, IEEE Trans. Signal Process, 41:12 (1993), 3397–3415 | DOI | Zbl

[8] A. C. Gilbert, M. Muthukrishnan, M. J. Strauss, “Approximation of functions over redundant dictionaries using coherence”, Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms (Baltimore, MD, USA, 2003), Association for Computing Machinery, New York, 2003, 243–252 | MR | Zbl

[9] D. L. Donoho, M. Elad, V. N. Temlyakov, “Stable recovery of sparse overcomplete representations in the presence of noise”, IEEE Trans. Inform. Theory, 52:1 (2006), 6–18 | DOI | MR

[10] J. A. Tropp, “Greed is good: algorithmic results for sparse approximation”, IEEE Trans. Inform. Theory, 50:10 (2004), 2231–2242 | DOI | MR

[11] E. J. Candes, T. Tao, “Decoding by linear programming”, IEEE Trans. Inform. Theory, 51:12 (2005), 4203–4215 | DOI | MR

[12] E. J. Candes, T. Tao, “Near-optimal signal recovery from random projections: universal encoding strategies?”, IEEE Trans. Inform. Theory, 52:12 (2005), 5406–5425 | DOI | MR

[13] B. S. Kašin, “Diameters of some finite-dimensional sets and classes of smooth functions”, Math. USSR-Izv., 11:2 (1977), 317–333 | DOI | MR | Zbl | Zbl

[14] R. Baraniuk, M. Davenport, R. DeVore, M. Wakin, “A simple proof of the restricted isometry property for random matrices”, Constr. Approx., 28:3 (2008), 253–263 | DOI | MR | Zbl

[15] R. Gribonval, M. Nielsen, “On the strong uniqueness of highly sparse expansions from redundant dictionaries”, Proc. Int Conf. Independent Component Anal. (ICA'04), 2004

[16] V. N. Temlyakov, P. Zheltov, “On performance of greedy algorithms”, J. Approx. Theory, 163:9 (2011), 1134–1145 | DOI

[17] D. L. Donoho, M. Elad, V. N. Temlyakov, “On Lebesgue-type inequalities for greedy approximation”, J. Approx. Theory, 147:2 (2007), 185–195 | DOI | MR | Zbl

[18] E. D. Livshits, On the optimality of Orthogonal Greedy Algorithm for $M$-coherent dictionaries, arXiv: 1003.5349

[19] M. A. Davenport, M. B. Wakin, “Analysis of orthogonal matching pursuit using the restricted isometry property”, IEEE Trans. Inform. Theory, 56:9 (2010), 4395–4401 | DOI | MR

[20] E. Liu, V. M. Temlyakov, Orthogonal super greedy algorithm and applications in compressed sensing, 2010 http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/LiuTemlyakov.pdf

[21] H. Rauhut, “On the impossibility of uniform sparse reconstruction using greedy methods”, Sampl. Theory Signal Image Process., 7:2 (2008), 197–215 | MR | Zbl

[22] W. Dai, O. Milenkovic, “Subspace pursuit for compressive sensing signal reconstruction”, IEEE Trans. Inform. Theory, 55:5 (2009), 2230–2249 | DOI | MR

[23] R. A. DeVore, V. N. Temlyakov, “Some remarks on greedy algorithms”, Adv. Comput. Math., 5:1 (1996), 173–187 | DOI | MR | Zbl