×

Splitting matching pursuit method for reconstructing sparse signal in compressed sensing. (English) Zbl 1266.94009

Summary: In this paper, a novel method named splitting matching pursuit (SMP) is proposed to reconstruct \(K\)-sparse signals in compressed sensing. The proposed method selects \(Fl\) (\(Fl > 2K\)) largest components of the correlation vector \(c\), which are divided into \(F\) split sets with equal length \(l\). The searching area is thus expanded to incorporate more candidate components, which increases the probability of finding the true components at one iteration. The proposed method does not require the sparsity level \(K\) to be known in prior. The merging, estimation and pruning steps are carried out for each split set independently, which makes it especially suitable for parallel computation. The proposed SMP method is then extended to more practical condition, e.g. the direction of arrival (DOA) estimation problem in phased array radar system using compressed sensing. Numerical simulations show that the proposed method succeeds in identifying multiple targets in a sparse radar scene, outperforming other OMP-type methods. The proposed method also obtains more precise estimation of DOA angle using one snapshot compared with the traditional estimation methods such as Capon, APES (amplitude and phase estimation) and GLRT (generalized likelihood ratio test) based on hundreds of snapshots.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

Software:

CoSaMP; PDCO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 33-61, 1998. · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[2] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1058.90049
[3] J. A. Tropp and S. J. Wright, “Computational methods for sparse solution of linear inverse problems,” Proceedings of the IEEE, vol. 98, no. 6, pp. 948-958, 2010. · doi:10.1109/JPROC.2010.2044010
[4] S. G. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries,” IEEE Transactions on Signal Processing, vol. 41, no. 12, pp. 3397-3415, 1993. · Zbl 0842.94004 · doi:10.1109/78.258082
[5] J. A. Tropp, “Greed is good: algorithmic results for sparse approximation,” IEEE Transactions on Information Theory, vol. 50, no. 10, pp. 2231-2242, 2004. · Zbl 1288.94019 · doi:10.1109/TIT.2004.834793
[6] D. Needell and R. Vershynin, “Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit,” Foundations of Computational Mathematics, vol. 9, no. 3, pp. 317-334, 2009. · Zbl 1183.68739 · doi:10.1007/s10208-008-9031-3
[7] W. Dai and O. Milenkovic, “Subspace pursuit for compressive sensing signal reconstruction,” IEEE Transactions on Information Theory, vol. 55, no. 5, pp. 2230-2249, 2009. · Zbl 1367.94082 · doi:10.1109/TIT.2009.2016006
[8] D. Needell and J. A. Tropp, “CoSaMP: iterative signal recovery from incomplete and inaccurate samples,” Applied and Computational Harmonic Analysis, vol. 26, no. 3, pp. 301-321, 2009. · Zbl 1163.94003 · doi:10.1016/j.acha.2008.07.002
[9] H. Huang and A. Makur, “Backtracking-based matching pursuit method for sparse signal reconstruction,” IEEE Signal Processing Letters, vol. 18, no. 7, pp. 391-394, 2011. · doi:10.1109/LSP.2011.2147313
[10] J. Capon, “High resolution frequency-wave number spectrum analysis,” Proceedings of the IEEE, vol. 57, no. 8, pp. 1408-1418, 1969.
[11] J. Li and P. Stoica, “An adaptive filtering approach to spectral estimation and SAR imaging,” IEEE Transactions on Signal Processing, vol. 44, no. 6, pp. 1469-1484, 1996.
[12] E. J. Kelly, “An adaptive detection algorithm,” IEEE Transactions on Aerospace and Electronic Systems, vol. 22, no. 2, pp. 115-127, 1986.
[13] SparseLab, http://dsp.rice.edu/cs.
[14] A. C. Gürbüz, J. H. McClellan, and V. Cevher, “A compressive beamforming method,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP ’08), pp. 2617-2620, Las Vegas, Nev, USA, April 2008. · doi:10.1109/ICASSP.2008.4518185
[15] I. Stojanovic, W. C. Karl, and M. Cetin, “Compressed sensing of mono-static and multi-static SAR,” in Algorithms for Synthetic Aperture Radar Imagery XVI, Proceedings of SPIE, Orlando, Fla, USA, April 2009. · doi:10.1117/12.818808
[16] J. H. G. Ender, “On compressive sensing applied to radar,” Signal Processing, vol. 90, no. 5, pp. 1402-1414, 2010. · Zbl 1194.94084 · doi:10.1016/j.sigpro.2009.11.009
[17] Y. Yu, A. P. Petropulu, and H. V. Poor, “Measurement matrix design for compressive sensing-based MIMO radar,” IEEE Transactions on Signal Processing, vol. 59, no. 11, pp. 5338-5352, 2011. · Zbl 1393.94510 · doi:10.1109/TSP.2011.2162328
[18] J. Zhang, D. Zhu, and G. Zhang, “Adaptive compressed sensing radar oriented toward cognitive detection in dynamic sparse target scene,” IEEE Transactions on Signal Processing, vol. 60, no. 4, pp. 1718-1729, 2012. · Zbl 1393.94732 · doi:10.1109/TSP.2012.2183127
[19] Y. Chi, L. L. Scharf, A. Pezeshki, and A. R. Calderbank, “Sensitivity to basis mismatch in compressed sensing,” IEEE Transactions on Signal Processing, vol. 59, no. 5, pp. 2182-2195, 2011. · Zbl 1392.94144 · doi:10.1109/TSP.2011.2112650
[20] Y. Bar-Shalom and T. E. Fortmann, Tracking and Data Association, Academic Press, Orlando, Fla, USA, 1988. · Zbl 0634.93001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.