Orthogonal matching pursuit (OMP) algorithm is a classical greedy algorithm widely used in compressed sensing. In this paper, by exploiting the Wielandt inequality and some properties of orthogonal projection matrix, we obtained a new number of iterations required for the OMP algorithm to perform exact recovery of sparse signals, which improve significantly upon the latest results as we know.

References

• Bernstein, D. S. (2005). Matrix mathematics: Theory, facts, and formulas with application to linear systems theory. Princeton University Press. 
• Cai, T., & Wang, L. (2011). Orthogonal matching pursuit for sparse signal recovery with noise. IEEE Transactions on Information Theory, 57(7), 4680–4688. https://doi.org/10.1109/TIT.2011.2146090 
• Cai, T., Wang, L., & Xu, G. (2010). New bounds for restricted isometry constants. IEEE Transactions on Information Theory, 56(9), 4388–4394. https://doi.org/10.1109/TIT.2010.2054730 
• Cai, T., Xu, G., & Zhang, J. (2009). On recovery of sparse signals via l1 minimization. IEEE Transactions on Information Theory, 55(7), 3388–3397. https://doi.org/10.1109/TIT.2009.2021377 
• Candes, E. J., & Tao, T. (2005). Decoding by linear programming. IEEE Transactions on Information Theory, 51(12), 4203–4215. https://doi.org/10.1109/TIT.2005.858979 
• Chang, L. H., & Wu, J. Y. (2014). An improved RIP-based performance guarantee for sparse signal recovery via orthogonal matching pursuit. IEEE Transactions on Information Theory, 60(9), 405–408. https://doi.org/10.1109/TIT.18 
• Davenport, M. A., & Wakin, M. B. (2010). Analysis of orthogonal matching pursuit using the restricted isometry property. IEEE Transactions on Information Theory, 56(9), 4395–4401. https://doi.org/10.1109/TIT.2010.2054653 
• Huang, S., & Zhu, J. (2011). Recovery of sparse signals using OMP and its variants: convergence analysis based on RIP. Inverse Problems, 27(3), 035003. https://doi.org/10.1088/0266-5611/27/3/035003
• Li, H. F., & Wen, J. M. (2019). A new analysis for support recovery with block orthogonal matching pursuit. IEEE Signal Processing Letters, 26(2), 247–251. https://doi.org/10.1109/LSP.2018.2885919 
• Liu, C., Fang, Y., & Liu, J. Z. (2017). Some new results about sufficient conditions for exact support recovery of sparse signals via orthogonal matching pursuit. IEEE Transactions on Signal Processing, 65(17), 4511–4524. https://doi.org/10.1109/TSP.2017.2711543 
• Livshitz, E. D. (2012). On the efficiency of the orthogonal matching pursuit in compressed sensing. Sbornik Mathematics, 203(2), 33–44. https://doi.org/10.4213/sm 
• Livshitz, E. D., & Temlyakov, V. N. (2014). Sparse approximation and recovery by greedy algorithms. IEEE Transactions on Information Theory, 60(7), 3989–4000. https://doi.org/10.1109/TIT.2014.2320932 
• Mo, Q. (2015). A sharp restricted isometry constant bound of orthogonal matching pursuit. arXiv: 1501.01708 [Online]. Available: http://arxiv.org/pdf/1501.01708v1.pdf. 
• Tropp, J. A., & Gilbert, A. C. (2007). Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 53(12), 4655–4666. https://doi.org/10.1109/TIT.2007.909108
• Wang, J., & Shim, B. (2016). Exact recovery of sparse signals using orthogonal matching pursuit: How many iterations do we need. IEEE Transactions on Signal Processing, 64(16), 4194–4202. https://doi.org/10.1109/TSP.2016.2568162
• Wang, S. G., & Ip, W. -C. (1999). A matrix version of the Wielandt inequality and its application to statistics. Linear Algebra Its Appl, 2, 118–120. https://doi.org/10.1016/S0024-3795(99)00117-2
• Wen, J., Zhang, R., & Yu, W. (2020). Signal-dependent performance analysis of orthogonal matching pursuit for exact sparse recovery. IEEE Transactions on Signal Processing, 68, 5031–5046. https://doi.org/10.1109/TSP.78 
• Wen, J., Zhou, Z., Wang, J., Tang, X., & Mo, Q. (2017). A sharp condition for exact support recovery with orthogonal matching pursuit. IEEE Transactions on Signal Processing, 65(6), 1370–1382. https://doi.org/10.1109/TSP.2016.2634550 
• Wu, R., Huang, W., & Chen, D.-R. (2013). The exact support recovery of sparse signals with noise via orthogonal matching pursuit. IEEE Signal Processing Letters, 20(4), 403–406. https://doi.org/10.1109/LSP.2012.2233734 
• Zhang, T. (2011). Sparse recovery with orthogonal matching pursuit under RIP. IEEE Transactions on Information Theory, 57(9), 6215–6221. https://doi.org/10.1109/TIT.2011.2162263 

To cite this article: Xueping Chen, Jianzhong Liu & Jiandong Chen (2022): A new result on recovery sparse signals using orthogonal matching pursuit, Statistical Theory and Related Fields, DOI: 10.1080/24754269.2022.2048445

To link to this article: https://doi.org/10.1080/24754269.2022.2048445