• 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

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.
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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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). 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. 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. 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. 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, (1993), 40. Google Scholar

[16]

H. Rauhut, Compressive sensing and structured random matrices,, Theoretical foundations and numerical methods for sparse recovery, 9 (2010), 1. 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. Google Scholar

[18]

J. A. Tropp, Greed is good: Algorithmic results for sparse approximation,, IEEE Trans. Inform. Theory, 50 (2004), 2231. 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. Google Scholar

[20]

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

[21]

T. Zhang, On the consistency of feature selection using greedy least squares regression,, J. Machine Learning Research, 10 (2009), 555. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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). 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. 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. 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. 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, (1993), 40. Google Scholar

[16]

H. Rauhut, Compressive sensing and structured random matrices,, Theoretical foundations and numerical methods for sparse recovery, 9 (2010), 1. 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. Google Scholar

[18]

J. A. Tropp, Greed is good: Algorithmic results for sparse approximation,, IEEE Trans. Inform. Theory, 50 (2004), 2231. 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. Google Scholar

[20]

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

[21]

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

[1]

Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-8. 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]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017

[13]

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

[14]

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

[15]

Alfred K. Louis. Diffusion reconstruction from very noisy tomographic data. Inverse Problems & Imaging, 2010, 4 (4) : 675-683. doi: 10.3934/ipi.2010.4.675

[16]

Elena Braverman, Alexandra Rodkina. Stabilization of difference equations with noisy proportional feedback control. Discrete & Continuous Dynamical Systems - B, 2017, 22 (6) : 2067-2088. doi: 10.3934/dcdsb.2017085

[17]

Dana Paquin, Doron Levy, Lei Xing. Multiscale deformable registration of noisy medical images. Mathematical Biosciences & Engineering, 2008, 5 (1) : 125-144. doi: 10.3934/mbe.2008.5.125

[18]

Jianzhong Wang. Wavelet approach to numerical differentiation of noisy functions. Communications on Pure & Applied Analysis, 2007, 6 (3) : 873-897. doi: 10.3934/cpaa.2007.6.873

[19]

Bruno Sixou, Cyril Mory. Kullback-Leibler residual and regularization for inverse problems with noisy data and noisy operator. Inverse Problems & Imaging, 2019, 13 (5) : 1113-1137. doi: 10.3934/ipi.2019050

[20]

Danilo Coelho, David Pérez-Castrillo. On Marilda Sotomayor's extraordinary contribution to matching theory. Journal of Dynamics & Games, 2015, 2 (3&4) : 201-206. doi: 10.3934/jdg.2015001

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]