Sparse signals recovery from noisy measurements by orthogonal matching pursuit

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

February 2015, 9(1): 231-238. doi: 10.3934/ipi.2015.9.231

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, China
2.	Department of Mathematics, Zhejiang University, Hangzhou, 310027

Received June 2011 Revised July 2013 Published January 2015

Abstract
Related Papers

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: orthogonal matching pursuit, Compressed sensing, noisy measurements., restricted isometry property, support recovery.

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

Citation: Yi Shen, Song Li. Sparse signals recovery from noisy measurements by orthogonal matching pursuit. Inverse Problems and Imaging, 2015, 9 (1) : 231-238. doi: 10.3934/ipi.2015.9.231

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.

show all references

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.

[1]	Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1519-1526. doi: 10.3934/jimo.2019014
[2]	Steven L. Brunton, Joshua L. Proctor, Jonathan H. Tu, J. Nathan Kutz. Compressed sensing and dynamic mode decomposition. Journal of Computational Dynamics, 2015, 2 (2) : 165-191. doi: 10.3934/jcd.2015002
[3]	Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021191
[4]	Amin Boumenir, Vu Kim Tuan. Recovery of the heat coefficient by two measurements. Inverse Problems and Imaging, 2011, 5 (4) : 775-791. doi: 10.3934/ipi.2011.5.775
[5]	Amin Boumenir, Vu Kim Tuan, Nguyen Hoang. The recovery of a parabolic equation from measurements at a single point. Evolution Equations and Control Theory, 2018, 7 (2) : 197-216. doi: 10.3934/eect.2018010
[6]	Björn Popilka, Simon Setzer, Gabriele Steidl. Signal recovery from incomplete measurements in the presence of outliers. Inverse Problems and Imaging, 2007, 1 (4) : 661-672. doi: 10.3934/ipi.2007.1.661
[7]	Yingying Li, Stanley Osher. Coordinate descent optimization for l¹ minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487
[8]	Song Li, Junhong Lin. Compressed sensing with coherent tight frames via $l_q$-minimization for $0 < q \leq 1$. Inverse Problems and Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[9]	Ting Chen, Fusheng Lv, Wenchang Sun. Uniform Approximation Property of Frames with Applications to Erasure Recovery. Communications on Pure and Applied Analysis, 2022, 21 (3) : 1093-1107. doi: 10.3934/cpaa.2022011
[10]	Xiaoping Fang, Youjun Deng, Wing-Yan Tsui, Zaiyun Zhang. On simultaneous recovery of sources/obstacles and surrounding mediums by boundary measurements. Electronic Research Archive, 2020, 28 (3) : 1239-1255. doi: 10.3934/era.2020068
[11]	Youjun Deng, Hongyu Liu, Xianchao Wang, Dong Wei, Liyan Zhu. Simultaneous recovery of surface heat flux and thickness of a solid structure by ultrasonic measurements. Electronic Research Archive, 2021, 29 (5) : 3081-3096. doi: 10.3934/era.2021027
[12]	Platon Surkov. Dynamical estimation of a noisy input in a system with a Caputo fractional derivative. The case of continuous measurements of a part of phase coordinates. Mathematical Control and Related Fields, 2022 doi: 10.3934/mcrf.2022020
[13]	Meixin Xiong, Liuhong Chen, Ju Ming, Jaemin Shin. Accelerating the Bayesian inference of inverse problems by using data-driven compressive sensing method based on proper orthogonal decomposition. Electronic Research Archive, 2021, 29 (5) : 3383-3403. doi: 10.3934/era.2021044
[14]	Anna-Lena Trautmann. Isometry and automorphisms of constant dimension codes. Advances in Mathematics of Communications, 2013, 7 (2) : 147-160. doi: 10.3934/amc.2013.7.147
[15]	John A. Morgan. Interception in differential pursuit/evasion games. Journal of Dynamics and Games, 2016, 3 (4) : 335-354. doi: 10.3934/jdg.2016018
[16]	Dor Elimelech. Permutations with restricted movement. Discrete and Continuous Dynamical Systems, 2021, 41 (9) : 4319-4349. doi: 10.3934/dcds.2021038
[17]	Thomas Feulner. The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes. Advances in Mathematics of Communications, 2009, 3 (4) : 363-383. doi: 10.3934/amc.2009.3.363
[18]	Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems and Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901
[19]	Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017
[20]	Guangzhou Chen, Xiaotong Zhang. Constructions of irredundant orthogonal arrays. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021051

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Yi Shen Song Li
on Google Scholar
Yi Shen Song Li

[Back to Top]