Geodesic
On the efficiency of the Orthogonal Matching Pursuit in compressed sensing
Sbornik. Mathematics, Tome 203 (2012) no. 2, pp. 183-195 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     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
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/

[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