×

A sharp RIP condition for orthogonal matching pursuit. (English) Zbl 1381.94032

Summary: A restricted isometry property (RIP) condition \(\delta_K + \sqrt{K}\theta_{K,1} < 1\) is known to be sufficient for orthogonal matching pursuit (OMP) to exactly recover every \(K\)-sparse signal \(x\) from measurements \(y=\Phi x\). This paper is devoted to demonstrate that this condition is sharp. We construct a specific matrix with \(\delta_K + \sqrt{K}\theta_{K,1}=1\) such that OMP cannot exactly recover some \(K\)-sparse signals.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[2] Donoho, D. L., Compressed sensing, IEEE Transactions on Information Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[3] Xu, Z., Compressed sensing: a survey, Scientia Sinica Mathematica, 42, 9, 865-877 (2012) · Zbl 1488.94044 · doi:10.1360/012011-1043
[4] Donoho, D. L.; Elad, M., Optimally sparse representation in general (nonorthogonal) dictionaries via \(l_1\) minimization, Proceedings of the National Academy of Sciences of the United States of America, 100, 5, 2197-2202 (2003) · Zbl 1064.94011 · doi:10.1073/pnas.0437847100
[5] Saab, R.; Yılmaz, Y., Sparse recovery by non-convex optimization—instance optimality, Applied and Computational Harmonic Analysis, 29, 1, 30-48 (2010) · Zbl 1200.90158 · doi:10.1016/j.acha.2009.08.002
[6] Tropp, J. A., Greed is good: algorithmic results for sparse approximation, IEEE Transactions on Information Theory, 50, 10, 2231-2242 (2004) · Zbl 1288.94019 · doi:10.1109/TIT.2004.834793
[7] Maleh, R., Improved RIP analysis of orthogonal matching pursuit
[8] Xu, Z., The performance of orthogonal multi-matching pursuit under RIP
[9] Donoho, D. L.; Huo, X., Uncertainty principles and ideal atomic decomposition, IEEE Transactions on Information Theory, 47, 7, 2845-2862 (2001) · Zbl 1019.94503 · doi:10.1109/18.959265
[10] Cai, T. T.; Wang, L.; Xu, G., Stable recovery of sparse signals and an oracle inequality, IEEE Transactions on Information Theory, 56, 7, 3516-3522 (2010) · Zbl 1366.94085 · doi:10.1109/TIT.2010.2048506
[11] Candes, E. J.; Tao, T., Decoding by linear programming, IEEE Transactions on Information Theory, 51, 12, 4203-4215 (2005) · Zbl 1264.94121 · doi:10.1109/TIT.2005.858979
[12] Davenport, M. A.; Wakin, M. B., Analysis of orthogonal matching pursuit using the restricted isometry property, IEEE Transactions on Information Theory, 56, 9, 4395-4401 (2010) · Zbl 1366.94093 · doi:10.1109/TIT.2010.2054653
[13] Huang, S.; Zhu, J., Recovery of sparse signals using OMP and its variants: convergence analysis based on RIP, Inverse Problems, 27, 3 (2011) · Zbl 1220.94017 · doi:10.1088/0266-5611/27/3/035003
[14] Liu, E.; Temlyakov, V. N., The orthogonal super greedy algorithm and applications in compressed sensing, IEEE Transactions on Information Theory, 58, 4, 2040-2047 (2012) · Zbl 1365.94180 · doi:10.1109/TIT.2011.2177632
[15] Dan, W.; Wang, R. H., Robustness of orthogonal matching pursuit under restricted isometry property, Science China Mathematics, 56 (2013) · Zbl 1307.65021 · doi:10.1007/s11425-013-4655-4
[16] Wang, J.; Shim, B., Improved recovery bounds of orthogonal matching pursuit using restricted isometry property
[17] Mo, Q.; Shen, Y., A remark on the restricted isometry property in orthogonal matching pursuit, IEEE Transactions on Information Theory, 58, 6, 3654-3656 (2012) · Zbl 1365.94182 · doi:10.1109/TIT.2012.2185923
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.