SCIENCE CHINA Information Sciences, Volume 61, Issue 10: 102303(2018) https://doi.org/10.1007/s11432-017-9289-2

Improved RIP-based performance guarantees for multipath matching pursuit

Juan ZHAO1,2, Xia BAI1,2,*, Ran TAO1,2
More info
  • ReceivedJul 10, 2017
  • AcceptedOct 20, 2017
  • PublishedMay 22, 2018


The multipath matching pursuit (MMP) is a generalization of the orthogonal matching pursuit (OMP), which generates multiple child paths for every candidate in each iteration and selects the candidate having the minimal residual as the final support set when iteration ends. In this paper we analyze its performance in both noiseless and noisy cases. The restricted isometry property (RIP)-based condition of MMP that ensures accurate recovery of sparse signals in the noiseless case is derived by using a simple technique. The performance guarantees of the MMP for support recovery in noisy cases are also discussed. It is shown that under certain conditions on the RIP and minimum magnitude of nonzero components of the sparse signal, the MMP will exactly recover the true support of the sparse signal in cases of bounded noises and recover the true support with a high probability in the case of Gaussian noise. Our bounds on the RIP improve the existing results.


[1] Candes E J, Wakin M B. An introduction to compressive sampling. IEEE Signal Process Mag, 2008, 25: 21-30 CrossRef ADS Google Scholar

[2] Bu H X, Bai X, Tao R. Compressed sensing SAR imaging based on sparse representation in fractional Fourier domain. Sci China Inf Sci, 2012, 55: 1789-1800 CrossRef Google Scholar

[3] Zhang B C, Zhang Z, Jiang C L. System design and first airborne experiment of sparse microwave imaging radar: initial results. Sci China Inf Sci, 2015, 58: 062306 CrossRef Google Scholar

[4] Hou Q K, Liu Y, Fan L J. Compressed sensing digital receiver and orthogonal reconstructing algorithm for wideband ISAR radar. Sci China Inf Sci, 2015, 58: 020302 CrossRef Google Scholar

[5] Yu H, Shu F, You Y. Compressed sensing-based time-domain channel estimator for full-duplex OFDM systems with IQ-imbalances. Sci China Inf Sci, 2017, 60: 082303 CrossRef Google Scholar

[6] Candes E J, Tao T. Decoding by linear programming. IEEE Trans Inf Theory, 2005, 51: 4203-4215 CrossRef Google Scholar

[7] Tropp J A, Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans Inf Theory, 2007, 53: 4655-4666 CrossRef Google Scholar

[8] Wang J, Shim B. On the recovery limit of sparse signals using orthogonal matching pursuit. IEEE Trans Signal Process, 2012, 60: 4973-4976 CrossRef ADS Google Scholar

[9] Wen J M, Zhou Z C, Wang J. A sharp condition for exact support recovery with orthogonal matching pursuit. IEEE Trans Signal Process, 2017, 65: 1370-1382 CrossRef ADS arXiv Google Scholar

[10] Needell D, Vershynin R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE J Sel Top Signal Process, 2010, 4: 310-316 CrossRef ADS Google Scholar

[11] Donoho D L, Tsaig Y, Drori I. Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit. IEEE Trans Inf Theory, 2012, 58: 1094-1121 CrossRef Google Scholar

[12] Needell D, Tropp J A. CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl Comput Harmonic Anal, 2009, 26: 301-321 CrossRef Google Scholar

[13] Dai W, Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans Inf Theory, 2009, 55: 2230-2249 CrossRef Google Scholar

[14] Wang J, Kwon S K, Shim B. Generalized orthogonal matching pursuit. IEEE Trans Signal Process, 2012, 60: 6202-6216 CrossRef ADS arXiv Google Scholar

[15] Satpathi S, Das R L, Chakraborty M. Improving the bound on the RIP constant in generalized orthogonal matching pursuit. IEEE Signal Process Lett, 2013, 20: 1074-1077 CrossRef ADS arXiv Google Scholar

[16] Shen Y, Pan W L, Li J. Analysis of generalised orthogonal matching pursuit using restricted isometry constant. Electron Lett, 2014, 50: 1020-1022 CrossRef Google Scholar

[17] Rui G, Tian W. Blind sparsity weak subspace pursuit for compressed sensing. Electron Lett, 2013, 49: 369-370 CrossRef Google Scholar

[18] Cotter S F, Rao B D. Application of tree-based searches to matching pursuit. In: Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Salt Lake City, 2001. 3933--3936. Google Scholar

[19] Karabulut G Z, Moura L, Panario D. Integrating flexible tree searches to orthogonal matching pursuit algorithm. IEE Proc Vis Image Process, 2006, 153: 538-548 CrossRef Google Scholar

[20] Karahanoglu N B, Erdogan H. A* orthogonal matching pursuit: best-first search for compressed sensing signal recovery. Digit Signal Process, 2012, 22: 555-568 CrossRef Google Scholar

[21] Kwon S, Wang J, Shim B. Multipath matching pursuit. IEEE Trans Inf Theory, 2014, 60: 2986-3001 CrossRef Google Scholar

[22] Shim B, Kwon S, Song B. Sparse detection with integer constraint using multipath matching pursuit. IEEE Commun Lett, 2014, 18: 1851-1854 CrossRef Google Scholar

[23] Sah A K, Chaturvedi A K. An MMP-based approach for detection in large MIMO systems using sphere decoding. IEEE Wirel Commun Lett, 2017, 6: 158-161 CrossRef Google Scholar

[24] Candès E J. The restricted isometry property and its implications for compressed sensing. Comput Rendus Math, 2008, 346: 589-592 CrossRef Google Scholar

[25] Wu R, Huang W, Chen D R. The exact support recovery of sparse signals with noise via orthogonal matching pursuit. IEEE Signal Process Lett, 2013, 20: 403-406 CrossRef ADS Google Scholar

[26] Cai T T, Wang L. Orthogonal matching pursuit for sparse signal recovery with noise. IEEE Trans Inf Theory, 2011, 57: 4680-4688 CrossRef Google Scholar

  • Figure 1

    Relationship between the candidates in different iterations of the MMP.


    Algorithm 1 MMP algorithm [21]

    Require:measurement ${\boldsymbol~y}$, sensing matrix $~\mathbf{\Phi~}$, sparsity $K$, number of path $L$;

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号