Sparse signals recovery from noisy measurements by orthogonal matching pursuit

Yi Shen; Song Li

doi:10.3934/ipi.2015.9.231

Article Contents

2015, Volume 9, Issue 1: 231-238. Doi: 10.3934/ipi.2015.9.231

This issue Previous Article Estimation of conductivity changes in a region of interest with electrical impedance tomography Next Article On the missing bound state data of inverse spectral-scattering problems on the half-line

Sparse signals recovery from noisy measurements by orthogonal matching pursuit

Yi Shen^1, and
Song Li^2,

1.
Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, 310018
2.
Department of Mathematics, Zhejiang University, Hangzhou, 310027

Received: June 2011

Revised: July 2013

Published: February 2015

Abstract / Introduction Related Papers Cited by

Abstract

Recently, many practical algorithms have been proposed to recover the sparse signal from fewer measurements. Orthogonal matching pursuit (OMP) is one of the most effective algorithm. In this paper, we use the restricted isometry property to analysis OMP. We show that, under certain conditions based on the restricted isometry property and the signals, OMP will recover the support of the sparse signal when measurements are corrupted by additive noise.

Keywords:

Mathematics Subject Classification: 41A46, 68Q25, 68W20, 90C27.

Citation:

Related Papers

Cited by

References

[1]	R. Baraniuk, M. Davenport, R. DeVore and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28 (2008), 253-263.doi: 10.1007/s00365-007-9003-x.
[2]	T. Cai, L. Wang and G. Xu, New bounds for restricted isometry constants, IEEE Trans. Inf. Theory, 56 (2010), 4388-4394.doi: 10.1109/TIT.2010.2054730.
[3]	T. Cai and L. Wang, Orthogonal matching pursuit for sparse signal recovery with noise, IEEE Trans. Inf. Theory, 57 (2011), 4680-4688.doi: 10.1109/TIT.2011.2146090.
[4]	T. Cai and A. Zhang, Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-rank Matrices, IEEE Trans. Inf. Theory, 60 (2014), 122-132.doi: 10.1109/TIT.2013.2288639.
[5]	E. J. Candès, The restricted isometry property and its implications for compressed sensing, Comptes Rendus Mathematique, 346 (2008), 589-592.doi: 10.1016/j.crma.2008.03.014.
[6]	E. J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, 51 (2005), 4203-4215.doi: 10.1109/TIT.2005.858979.
[7]	M. A. Davenport and M. B. Wakin, Analysis of orthogonal matching pursuit using the restricted isometry property, IEEE Trans. Inf. Theory, 56 (2010), 4395-4401.doi: 10.1109/TIT.2010.2054653.
[8]	G. Davis, S. Mallat and M. Avellaneda, Adaptive greedy approximation, J. Constr. Approx., 13 (1997), 57-98.doi: 10.1007/BF02678430.
[9]	D. L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inf. Theory, 47 (2001), 2845-2862.doi: 10.1109/18.959265.
[10]	Z. B. Haim, Y. C. Eldar and M. Elad, Coherence-based performance guarantees for estimating a sparse vector under random noise, IEEE Trans. Signal Process., 58 (2010), 5030-5043.doi: 10.1109/TSP.2010.2052460.
[11]	S. S. Huang and J. B. Zhu, Recovery of sparse signals using OMP and its variants: Convergence analysis based on RIP, Inverse Problems, 27 (2011), 035003, 14pp.doi: 10.1088/0266-5611/27/3/035003.
[12]	E. T. Liu and N. Vladimir, The orthogonal super greedy algorithm and applications in compressed sensing, IEEE Trans. Inf. Theory, 58 (2012), 2040-2047.doi: 10.1109/TIT.2011.2177632.
[13]	Q. Mo and Y. Shen, A remark on the restricted isometry property in orthogonal matching pursuit, IEEE Trans. Inf. Theory, 58 (2012), 3654-3656.doi: 10.1109/TIT.2012.2185923.
[14]	D. Needell and J. A. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, Appl. Comp. Harmonic Anal., 26 (2009), 301-321.doi: 10.1016/j.acha.2008.07.002.
[15]	Y. C. Pati, R. Rezaiifar and P. S. Krishnaprasad, Orthogonal Matching Pursuit: Recursive function approximation with applications to wavelet decomposition, Proc. 27th Ann. Asilomar Conf. on Signals, Systems and Computers, (1993), 40-44.
[16]	H. Rauhut, Compressive sensing and structured random matrices, Theoretical foundations and numerical methods for sparse recovery, 9 (2010), 1-92.doi: 10.1515/9783110226157.1.
[17]	W. Rui, W. Huang and D. R. Chen, The Exact Support Recovery of Sparse Signals With Noise via Orthogonal Matching Pursuit, IEEE Signal Process. Lett., 20 (2013), 403-406.
[18]	J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inform. Theory, 50 (2004), 2231-2242.doi: 10.1109/TIT.2004.834793.
[19]	J. A. Tropp, Computational methods for sparse solution of linear inverse Problems, Proc. IEEE, 98 (2010), 948-958.
[20]	M. R. Yang and F. de Hoog, Coherence and RIP Analysis for Greedy Algorithms in Compressive Sensing, preprint, 2013, arXiv:1307.1949
[21]	T. Zhang, On the consistency of feature selection using greedy least squares regression, J. Machine Learning Research, 10 (2009), 555-568.