Bisection Subspace Pursuit Algorithm for Compressive Sensing

Abstract:

A novel greedy algorithm for blind CS recovery without prior knowledge of sparsity, called the Bisection Subspace Pursuit (BiSP) is introduced. The most outstanding feature of the BiSP is that it adopts the bisection method to adaptively estimate the sparsity of target signal, which means that no prior knowledge of sparsity is needed. Simulation results demonstrate that the BiSP not only retains comparable recovery accuracy with CoSaMP, SP and SAMP, but also outperforms the SAMP in terms of complexity when sparsity of signal is large. This makes the BiSP a competitive candidate for many practical situations.

• Periodical: Applied Mechanics and Materials (Volumes 713-715)
• Pages: 1256-1260
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.713-715.1256
• Online since: January 2015
• Authors: Lei Zhou*, Kai Liang Zhang, Dong Mei Li, Fang Wang, Xiao Jing Li, Sheng Fa Liang
• Keywords: Bisection Method, Blind Recovery, Compressive Sensing, Reconstruction Algorithms, Subspace Pursuit

References

[1] E. J. Candes, J. Romberg, and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 2006, 52(2): 489-509.

DOI: 10.1109/tit.2005.862083

[2] D. Donoho and J. Tanner, Precise undersampling theorems, Proceeding of the IEEE, 2010, 98(6): 913-924.

DOI: 10.1109/jproc.2010.2045630

[3] D. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization, Proc. Natl. Acad. Sci. USA, 2003, 100(5): 2197-(2002).

DOI: 10.1073/pnas.0437847100

[4] T. Zhang, Sparse recovery with orthogonal matching pursuit under RIP, IEEE Trans. Inf. Theory, 2011, 57(9): 6215-6221.

DOI: 10.1109/tit.2011.2162263

[5] D. Needell and R. Vershynin, Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, IEEE J. Sel. Topics Signal Process. 2010, 4(2): 310-316.

DOI: 10.1109/jstsp.2010.2042412

[6] D. Donoho, Y. Tsaig, I. Drori, and J. L. Strack, Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, IEEE Trans. Inf. Theory, 2012, 58 (2): 1094-1121.

DOI: 10.1109/tit.2011.2173241

[7] D. Needell, J. A. Tropp, CoSaMP: Iterative Signal Recovery from Incomplete and Inaccurate Samples, Appl. and Comp. Harm Anal., 2009, 26(3): 301-321.

DOI: 10.1016/j.acha.2008.07.002

[8] W. Dai, O. Milenkovic, Subspace Pursuit for Compressive Sensing Signal Reconstruction, IEEE Trans. Inf. Theory, 2009, 55(5): 2230-2249.

DOI: 10.1109/tit.2009.2016006

[9] Thong T. Do, Lu Gan, Nam Nguyen, etc., Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing, Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, Califormia, 2008, 10: 581-587.

DOI: 10.1109/acssc.2008.5074472

[10] E. J. Cadence and T. Tao, Near-optimal signal recovery from random projections: Universal encoding strategies? , IEEE Trans. Inf. Theory, 2006, 52(12): 5406-5425.

DOI: 10.1109/tit.2006.885507