American Institute of Mathematical Sciences

Advanced
  • 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

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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

G. Davis, S. Mallat and M. Avellaneda, Adaptive greedy approximation, J. Constr. Approx., 13 (1997), 57-98. doi: 10.1007/BF02678430.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[19]

J. A. Tropp, Computational methods for sparse solution of linear inverse Problems, Proc. IEEE, 98 (2010), 948-958. Google Scholar

[20]

M. R. Yang and F. de Hoog, Coherence and RIP Analysis for Greedy Algorithms in Compressive Sensing, preprint, 2013, arXiv:1307.1949 Google Scholar

[21]

T. Zhang, On the consistency of feature selection using greedy least squares regression, J. Machine Learning Research, 10 (2009), 555-568.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

G. Davis, S. Mallat and M. Avellaneda, Adaptive greedy approximation, J. Constr. Approx., 13 (1997), 57-98. doi: 10.1007/BF02678430.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[19]

J. A. Tropp, Computational methods for sparse solution of linear inverse Problems, Proc. IEEE, 98 (2010), 948-958. Google Scholar

[20]

M. R. Yang and F. de Hoog, Coherence and RIP Analysis for Greedy Algorithms in Compressive Sensing, preprint, 2013, arXiv:1307.1949 Google Scholar

[21]

T. Zhang, On the consistency of feature selection using greedy least squares regression, J. Machine Learning Research, 10 (2009), 555-568.  Google Scholar

[1]

Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & 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]

Amin Boumenir, Vu Kim Tuan. Recovery of the heat coefficient by two measurements. Inverse Problems & Imaging, 2011, 5 (4) : 775-791. doi: 10.3934/ipi.2011.5.775
[4]

Zohre Aminifard, Saman Babaie-Kafaki. Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021191
[5]

Amin Boumenir, Vu Kim Tuan, Nguyen Hoang. The recovery of a parabolic equation from measurements at a single point. Evolution Equations & 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 & Imaging, 2007, 1 (4) : 661-672. doi: 10.3934/ipi.2007.1.661
[7]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & 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 & Imaging, 2014, 8 (3) : 761-777. doi: 10.3934/ipi.2014.8.761
[9]

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
[10]

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
[11]

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
[12]

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
[13]

John A. Morgan. Interception in differential pursuit/evasion games. Journal of Dynamics & Games, 2016, 3 (4) : 335-354. doi: 10.3934/jdg.2016018
[14]

Dor Elimelech. Permutations with restricted movement. Discrete & Continuous Dynamical Systems, 2021, 41 (9) : 4319-4349. doi: 10.3934/dcds.2021038
[15]

Yangyang Xu, Wotao Yin, Stanley Osher. Learning circulant sensing kernels. Inverse Problems & Imaging, 2014, 8 (3) : 901-923. doi: 10.3934/ipi.2014.8.901
[16]

Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017
[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]

Miroslava Růžičková, Irada Dzhalladova, Jitka Laitochová, Josef Diblík. Solution to a stochastic pursuit model using moment equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (1) : 473-485. doi: 10.3934/dcdsb.2018032
[19]

Guangzhou Chen, Xiaotong Zhang. Constructions of irredundant orthogonal arrays. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021051
[20]

Mohar Guha, Keith Promislow. Front propagation in a noisy, nonsmooth, excitable medium. Discrete & Continuous Dynamical Systems, 2009, 23 (3) : 617-638. doi: 10.3934/dcds.2009.23.617

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (154)
  • HTML views (0)
  • Cited by (16)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy