DOI: 10.3724/SP.J.1146.2009.00497

Journal of Electronics & Information Technology (电子与信息学报) 2010/32:2 PP.470-475

An Introduction to Compressive Sampling and Its Applications

The problems of how to reduce the sampling rate in the broadband analog signal digitization and how to compress effectively the large amount of data for storage are always concerned by researchers. The recent proposed Compressive Sampling or Compressive Sensing method to solve the said problems is introduced in this paper. The method, which employs non-adaptive linear projections that preserve the structure of the signal, can capture and represent the compressible signal at a rate significantly below Nyquist rate. This paper not only presents the key procedures of this theory but also lists a variety of applications and points out the questions to be studied.

Key words:Compressive Sampling (CS),Sparsity,Measurement matrix,Signal reconstruction

ReleaseDate:2014-07-21 15:11:22

[1] Donoho D L. Compressed sensing.IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

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

[3] Candes E. Compressive sampling. Int. Congress of Mathematics, Madrid, Spain, 2006, 3: 1433-1452.

[4] Baraniuk R G. Compressive sensing. IEEE Signal Processing Magazine, 2007, 24(4): 118-124.

[5] 方红, 章权兵, 韦穗. 基于非常稀疏随机投影的图像重建方法. 计算机工程与应用, 2007, 43(22): 25-27. Fang H, Zhang Q, and W Sui. Method of image reconstruction based on very sparse random projection, Computer Engineering and Application, 2007, 43(22): 25-27.

[6] 傅迎华. 可压缩传感重构算法与近似QR分解. 计算机应用, 2008, 28(9): 2300-2302. Fu Y. Reconstruction of compressive sensing and semi-QR factorization. Journal of Computer Application, 2008, 28(9): 2300-2302.

[7] Brandenburg K. MP3 and AAC explained. AES 17th international conference on High-Quality Audio coding, Erlangen, Germany, Sept. 1999: 1-12.

[8] Pennebaker W and Mitchell J. JPEG: Still image data compression standard. Van Nostrand Reinhold, 1993.

[9] Candes E and Romberg J. Sparsity and incoherence in compressive sampling. Inverse Problems, 2007, 23(3): 969-985.

[10] Candes E and Tao T. Near-optimal signal recovery from random projections and universal encoding strategies. IEEE Transactions on Information Theory, 2006, 52(12): 5406-5425.

[11] Candes E and Tao T. Decoding by linear programming. IEEE Transactions on Information Theory, 2005, 51(12): 4203-4215.

[12] Haupt J and Nowak R. A generalized restricted isometry property. University of Wisconsin Madison Technical Report ECE-07-1, May 2007.

[13] Tibshirani R. Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society, Series B., 1996, 58(1): 267-288.

[14] Candes E and Romberg J. l1-magic: A collection of MATLAB routines for solving the convex optimization programs central to compressive sampling. 2006, www.acm.caltech. edu/ l1magic/.

[15] Johnson C, Seidel J, and Sofer A. Interior point methodology for 3-D PET reconstruction. IEEE Transactions on Medical Imaging, 2000, 19(4): 271-285.

[16] Efron B and Hastie T, et al. Least angle regression. The Annals of Statistics, 2004, 32(2): 407-499.

[17] Figueiredo M, Nowak R, and Wright S. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE Selected Topics in Signal Processing, 2007, Vol.1: 586-598.

[18] Gorodnitsky I F, George J, and Rao B D. Neuromagnetic source imaging with FOCUSS: A recursive weighted minimum norm algorithm. Electrocephalography and Clinical Neurophysiology, 1995, 95(4): 231-251.

[19] Rich C and Yin W. Iteratively reweighted algorithms for compressive sensing. ICASSP, Las Vegas, 2008: 3869-3872.

[20] Gu Y, Jin J, and Mei S. l0 Norm Constraint LMS for Sparse System Identification. IEEE Signal Processing Letters, 2009, 16(9): 774-777.

[21] Jin J, Gu Y, and Mei S. A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework. IEEE Special Issue on Compressive Sensing, under second round review, 2009.

[22] Tropp J and Gilbert A. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666.

[23] Donoho D L, Tsaig Y, and Starck Jean-Luc. Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. Technical report, Stanford University, Mar. 2006.

[24] Needell D and Vershynin R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. Submitted, Dec. 2007, PS_cache/arxiv/pdf/0712/0712.1360v1.pdf.

[25] Dai W and Milenkovic O. Subspace pursuit for compressive sensing: Closing the gap between performance and complexity. Preprint, Mar. 2008, SubspacePursuit.pdf.

[26] Valenzise G, Prandi G, and Tagliasacchi M, et al. Identification of sparse audio tampering using distributed source coding and compressive sensing techniques. DAFX 2008.

[27] Kirolos S, Laska J, and Wakin M, et al. Analog-to- information conversion via random demodulation. Proc. IEEE Dallas Circuits and Systems Conference, 2006: 1-4.

[28] Takhar D, Bansal V, and Wakin M, et al. A compressive sensing camera: New theory and an implementation using digital micromirrors. Proc. Compute Imaging IV SPIE Electronic Imaging, San Jose, 2006: 1-10.

[29] Lustig M, Donoho D L, and Pauly J M. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 2007, 58(6): 1182-1195.

[30] Lustig M, Santos J M, Donoho D L, and J M. Pauly. k-t SPARSE: High frame rate dynamic MRI exploiting spatio-temporal sparsity. ISMRM, Seattle, Washington, 2006: 2420-2420.

[31] Potter L, Schniter P, and Ziniel J. Sparse reconstruction for RADAR. SPIE Algorithms for SAR Imagery XV, 2008, Vol. 6970: 1-15.

[32] Mairal J and Bach F, et al. Discriminative learned dictionaries for local image analysis. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), Anchorage, Alaska, June 2008: 1-8.

[33] Cevher V, Sankaranarayanan A, and Duarte M F, et al. Compressive sensing for background subtraction. European Conf. on Computer Vision (ECCV) , Marseille, France, 2008, Vol. 5303: 155-168.

[34] Saralees N. A generalized normal distribution. Journal of Applied Statistics, 2005, 32(7): 685-694.

[35] Candes E and Tao T. Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 2006, 52(12): 5406-5425.

[36] Boufounos P, Romberg J, and Baraniuk R. Compressive sensing-Theory and applications. April 2008, http://www.