International Journal of Image, Graphics and Signal Processing (IJIGSP)
IJIGSP Vol. 7, No. 10, 8 Sep. 2015
Cover page and Table of Contents: PDF (size: 590KB)
A Survey of Compressive Sensing Based Greedy Pursuit Reconstruction Algorithms
Full Text (PDF, 590KB), PP.1-10
Views: 0 Downloads: 0
Author(s)
Meenakshi
1,*
Sumit Budhiraja
1
Index Terms
Compressive Sensing, Sparsity, Signal Recovery, L1 minimization, Greedy Pursuit algorithms, Orthogonal Matching Pursuit (OMP), Iterative Hard Thresholding (IHT), Generalized OMP (GOMP)
Abstract
Conventional approaches to sampling images use Shannon theorem, which requires signals to be sampled at a rate twice the maximum frequency. This criterion leads to larger storage and bandwidth requirements. Compressive Sensing (CS) is a novel sampling technique that removes the bottleneck imposed by Shannon's theorem. This theory utilizes sparsity present in the images to recover it from fewer observations than the traditional methods. It joins the sampling and compression steps and enables to reconstruct with the only fewer number of observations. This property of compressive Sensing provides evident advantages over Nyquist-Shannon theorem. The image reconstruction algorithms with CS increase the efficiency of the overall algorithm in reconstructing the sparse signal. There are various algorithms available for recovery. These algorithms include convex minimization class, greedy pursuit algorithms. Numerous algorithms come under these classes of recovery techniques. This paper discusses the origin, purpose, scope and implementation of CS in image reconstruction. It also depicts various reconstruction algorithms and compares their complexity, PSNR and running time. It concludes with the discussion of the various versions of these reconstruction algorithms and future direction of CS-based image reconstruction algorithms.
Cite This Paper
Meenakshi, Sumit Budhiraja,"A Survey of Compressive Sensing Based Greedy Pursuit Reconstruction Algorithms", IJIGSP, vol.7, no.10, pp.1-10, 2015. DOI: 10.5815/ijigsp.2015.10.01
Reference
[1]E. Candes, Michael B. Wakin, "An introduction to compressive sampling", IEEE Signal Processing Magazine, pp. 21-30, 2008.
[2]Saad Qaisar, Rana Muhammad Bilal, Wafa Iqbal, Muqaddas Naureen, and Sungoung Lee, "Compressive Sensing: From Theory to Applications, a survey", Journal of Communications and networks, vol. 15, No. 5, pp.-443-456, October 2013.
[3]D. Donoho, "Compressed Sensing, IEEE Transactions on Information Theory", Vol. 52, Issue, pp. 1289-1306, 2006.
[4]E. Candes, T. Tao, "Near optimal Signal recovery from random projections: universal encoding strategies, IEEE Transactions on Information Theory", Vol. 52, Issue 12, pp. 5406-5425, 2006.
[5]F. Santosa and W. Symes, "Linear inversion of band-limited reflection seismograms", SIAM J. Scientific Statistical Comput. , vol. 7, pp-1307, 1986.
[6]L. Rudin, S. Osher, and E. Fatemi, "Nonlinear total variation based noise removal algorithms", Physica D: Nonlinear Phenomena, vol. 60, no. 1-4, pp. 259-268, 1992.
[7]E. Candes and J. Romberg, "Sparsity and incoherence in compressive sampling", Inverse Problems, vol. 23, p. 969, 2007.
[8]Vinay Jeengar, S. N. Omkar, Amarjot Singh, "A Review Comparison of Wavelet and Cosine image Transforms", I. J. Image, Graphics and Signal Processing, vol. 4, no. 11, pp. 16-25, 2012.
[9]M. Wakin, "An introduction to compressive Sensing", IEEE Signal Process, May, 2008.
[10]E. J. Candes, T. Tao, "Decoding by linear programming", IEEE Trans. Inf. Theory, vol. 51, pp. 1074-1077, 2005.
[11]E. Candes, J. Romberg and T. Tao, "Robust uncertainity principles: Exact signal reconstruction from highly incomplete Fourier information", IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489-509, Feb. 2006.
[12]Z. Chen and J. Dongara, "Condition numbers of Gaussian random matrices", SIAM J. Matrix analysis Appl., vol. 27, no. 3, pp. 603-620, 2006.
[13]E. Candes and T. Tao, "Near Optimal signal recovery from random projections: Universal encoding strategies?" IEEE Trans. Inf. Theory, vol. 52, no. 12, pp. 5406-5425, 2006.
[14]E. Candes and B. Rechi, "Exact matrix completion via convex optimization", Foundations Computational Math., vol. 9, no. 6, pp. 717-772, 2009.
[15]S. Chen, D. Donoho, and M. Saunders, "Atomic decomposition by basis pursuit", SIAM Rev., vol. 3, no. 1, pp. 129-159, 2001.
[16]Usham V. Dias, Milind E. Rane, "Block Based Compressive Sensed Thermal Image reconstruction using Greedy Algorithms", I. J. Image, Graphics and Signal Processing, vol. 6, no. 10, pp. 36-42, 2014.
[17]S. Mallat, Z. Zhang, "Matching Pursuit in a time-frequency dictionary, IEEE Trans. Signal Process. 1, pp. 3397-3415, 1993.
[18]J. A. Tropp and A. C. Gilbert, "Signal recovery from random measurements via orthogonal matching pursuit", IEEE Trans. Inform. Theory, Vol. 53, No. 12, pp. 4655-4666, Dec. 2007.
[19]Junxi Zhao, Ronfang Song, Jie Zhao, Wei-Ping Zhu, "New conditions for Uniformly recovering sparse signals via orthogonal matching pursuit", Journal of Signal Processing, vol. 106, pp. 106-113, 2015.
[20]Y. C. Pati, R. Rezaiifar, P. S. Krishna prasad, "Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition", in: Proc. 27th Asilomar Conference on Signals, Systems and Computers, vol.1, Los Alamitos, CA, pp.40–44 1993.
[21]G. Davis, S. Mallat, and M. Avellenda, "Greedy adaptive approximation", Constr. Approx., vol. 5, pp. 57-98, 1997.
[22]T. Tony Cai and Lie Wang, "Orthogonal Matching Pursuit for sparse signal recovery with noise", IEEE Transactions on information theory, vol. 57, pp. 4680-4688, july 2011.
[23]W. Dai, O. Milenkovic, "Subspace pursuit for compressive Sensing signal reconstruction", IEEE Trans. information theory, vol. 55, pp. 2230-2249, 2009.
[24]D. Needell, J.A. Tropp, "CoSaMP: Iterative signal recovery from incomplete and accurate samples", Appl. Comput. Harmon. Anal., vol. 26, pp. 301-321, 2008.
[25]Deanna Needell and Roman Vershynin, "Signal Recovery from incomplete and inaccurate measurements via Regularized Orthogonal Matching Pursuit", IEEE Journal of selected topics in signal processing, vol. 4, pp. 310-316, April 2010.
[26]T. Blumensath and M. E. Davies, "Iterative Thresholding for Sparse Approximations", J. Fourier Anal. Appl., 14 (2008), pp.629–654, 2008.
[27]S. Foucart, "Sparse Recovery Algorithms: Sufficient conditions in terms of restricted isometry constants", Springer Proceedings in Mathematics, vol. 13, pp 65-77, 2012.
[28]Ke Wei, "Fast Iterative Hard Thresholding for Compressed Sensing" IEEE Signal Processing Letters, vol. 22, no. 5, pp. 593-597, May 2015.
[29]Nazim Burak Karahanoglu, Hakan Erdogan, "Forward-Backward Search for compressed signal recovery", 20th European signal processing conference (EUSIPCO 2012), pp. 1429-1433, 2012.
[30]Nazim Burak, Karahanoglu, Hakan Erdogan, "Compressed Sensing signal recovery via forward-backward pursuit", Journal of Digital signal processing, vol. 23, pp. 1539-1548, 2013.
[31]Jian Wang, S. Kwon, B. Shim, "Generalized Orthogonal Matching Pursuit", IEEE Transactions on signal processing, vol. 60, pp. 6202-6216, 2012.
[32]Hui Sun, Lin Ni, "Compressed Sensing data reconstruction using adaptive Generalized orthogonal matching pursuit algorithm", International conference on computer science and network technology, pp. 1102-1106, 2013.