Compressive Sensing Algorithms for Signal Processing Applications: A Survey

Mohammed M. Abo-Zahhad¹, Aziza I. Hussein², Abdelfatah M. Mohamed¹

¹Department of Electrical and Electronics Engineering, Faculty of Engineering, Assiut University, Assiut, Egypt.
²Department of Computer and Systems Engineering, Faculty of Engineering, Minia University, Egypt.

DOI: 10.4236/ijcns.2015.86021                

Abstract

In digital signal processing (DSP), Nyquistrate sampling completely describes a signal by exploiting its bandlimitedness. Compressed Sensing (CS), also known as compressive sampling, is a DSP technique efficiently acquiring and reconstructing a signal completely from reduced number of measurements, by exploiting its compressibility. The measurements are not point samples but more general linear functions of the signal. CS can capture and represent sparse signals at a rate significantly lower than ordinarily used in the Shannon’s sampling theorem. It is interesting to notice that most signals in reality are sparse; especially when they are represented in some domain (such as the wavelet domain) where many coefficients are close to or equal to zero. A signal is called K-sparse, if it can be exactly represented by a basis, , and a set of coefficients , where only K coefficients are nonzero. A signal is called approximately K-sparse, if it can be represented up to a certain accuracy using K non-zero coefficients. As an example, a K-sparse signal is the class of signals that are the sum of K sinusoids chosen from the N harmonics of the observed time interval. Taking the DFT of any such signal would render only K non-zero values . An example of approximately sparse signals is when the coefficients , sorted by magnitude, decrease following a power law. In this case the sparse approximation constructed by choosing the K largest coefficients is guaranteed to have an approximation error that decreases with the same power law as the coefficients. The main limitation of CS-based systems is that they are employing iterative algorithms to recover the signal. The sealgorithms are slow and the hardware solution has become crucial for higher performance and speed. This technique enables fewer data samples than traditionally required when capturing a signal with relatively high bandwidth, but a low information rate. As a main feature of CS, efficient algorithms such as -minimization can be used for recovery. This paper gives a survey of both theoretical and numerical aspects of compressive sensing technique and its applications. The theory of CS has many potential applications in signal processing, wireless communication, cognitive radio and medical imaging.

Keywords

Compressive Sensing, Shannon Sampling Theory, Sensing Matrices, Sparsity, Coherence

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Bajwa, W., Haupt, J., Raz, G., Wright, S. and Nowak, R. (2007) Toeplitz-Structured Compressed Sensing Matrices. Proceedings of IEEE Workshop on Statistical Signal Processing, Madison, 26-29 August 2007, 294-298.
[2]	Candes, E.J. and Tao, T. (2005) Decoding by Linear Programming. IEEE Transactions on Information Theory, 51, 4203-4215. http://dx.doi.org/10.1109/TIT.2005.858979
[3]	Donoho, D.L. (2006) Compressed Sensing. IEEE Transactions on Information Theory, 52, 1289-1306. http://dx.doi.org/10.1109/TIT.2006.871582
[4]	Candes, E.J. and Tao, T. (2006) Near-Optimal Signal Recovery from Random Projections: Universal Encoding Strategies? IEEE Transactions on Information Theory, 52, 5406-5425. http://dx.doi.org/10.1109/TIT.2006.885507
[5]	Shannon, C.E. (1949) Communication in the Presence of Noise. Proceedings of the IRE, 37, 10-21. http://dx.doi.org/10.1109/JRPROC.1949.232969
[6]	Candès, E.J. and Romberg, J. (2007) Sparsity and Incoherence in Compressive Sampling. Inverse Problems, 23, 969. http://dx.doi.org/10.1088/0266-5611/23/3/008
[7]	Davenport, M., Boufounos, P., Wakin, M. and Baraniuk, R. (2010) Signal Processing with Compressive Measurements. IEEE Journal of Selected Topics in Signal Processing, 4, 445-460. http://dx.doi.org/10.1109/JSTSP.2009.2039178
[8]	Taubman, D. and Marcellin, M. (2001) JPEG 2000: Image Compression Fundamentals, Standards and Practice. Kluwer Academic Publishers, Norwell.
[9]	Donoho, D.L. (1995) Denoising by Soft-Thresholding. IEEE Transactions on Information Theory, 41, 613-627.
[10]	Mallat, S. (1999) A Wavelet Tour of Signal Processing. Academic Press, San Diego.
[11]	Carron, I. “Nuit Blanche” Blog. http://nuit-blanche.blogspot.com/
[12]	Needell, D. and Vershynin, R. (2009) Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit. Foundations of Computational Mathematics, 9, 317-334. http://dx.doi.org/10.1007/s10208-008-9031-3
[13]	Baraniuk, R. (2007) Compressive Sensing. IEEE Signal Processing Magazine, 24, 118-121.
[14]	Amini, A., Montazerhodjat, V. and Marvasti, F. (2012) Matrices with Small Coherence Using p-Ary Block Codes. IEEE Transactions on Signal Processing, 60, 172-181. http://dx.doi.org/10.1109/TSP.2011.2169249
[15]	Calderbank, R., Howard, S. and Jafarpour, S. (2010) Construction of a Large Class of Deterministic Sensing Matrices that Satisfy a Statistical Isometry Property. IEEE Journal of Selected Topics in Signal Processing, 4, 358-374. http://dx.doi.org/10.1109/JSTSP.2010.2043161
[16]	Nguyen, T.L.N. and Shin, Y. (2013) Deterministic Sensing Matrices in Compressive Sensing: A Survey. The Scientific World Journal, 2013, Article ID: 192795. http://dx.doi.org/10.1155/2013/192795
[17]	Candes, E.J., Tao, T. and Romberg, J. (2006) Robust Uncertainty Principles: Exact Signal Recon-struction from Highly Incomplete Frequency Information. IEEE Transactions on Information Theory, 52, 489-509. http://dx.doi.org/10.1109/TIT.2005.862083
[18]	Strohmer, T. and Hermann, M. (2008) Compressed Sensing Radar. IEEE Proceedings of International Conference on Acoustic, Speech, and Signal Processing, Las Vegas, 30 March-4 April 2008, 1509-1512.
[19]	Bobin, J., Starck, J.L. and Ottensamer, R. (2008) Compressed Sensing in Astronomy. IEEE Journal of Selected Topics in Signal Processing, 2, 718-726. http://dx.doi.org/10.1109/JSTSP.2008.2005337
[20]	Tropp, J.A., Laska, J.N., Duarte, M.F., Romberg, J.K. and Baraniuk, R.G. (2010) Beyond Nyquist: Efficient Sampling of Sparse Band Limited Signals. IEEE Transactions on Information Theory, 56, 520-544. http://dx.doi.org/10.1109/TIT.2009.2034811
[21]	Duarte, M., Davenport, M., Takhar, D., Laska, J., Sun, T., Kelly, K. and Baraniuk, R. (2008) Single-Pixel Imaging via Compressive Sampling. IEEE Signal Processing Magazine, 25, 83-91. http://dx.doi.org/10.1109/MSP.2007.914730
[22]	Wen, J., Chen, Z., Han, Y., Villasenor, J. and Yang, S. (2010) A Compressive Sensing Image Compression Algorithm Using Quantized DCT and Noiselet Information. Proceedings IEEE ICASSP 2010, 1294-1297.
[23]	Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002) Wireless Sensor Networks: A Survey. Computer Networks, 38, 393-422. http://dx.doi.org/10.1016/S1389-1286(01)00302-4
[24]	Barr, K.C. and Asanovic, K. (2006) Energy-Aware Lossless Data Compression. ACM Transactions on Computer Systems, 24, 250-291. http://dx.doi.org/10.1145/1151690.1151692
[25]	Heinzelman, W.R., Chandrakasan, A. and Balakrishnan, H. (2000) Energy-Efficient Communication Protocol for Wireless Microsensor Networks. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, Maui, 4-7 January 2000, 3005-3014. http://dx.doi.org/10.1109/HICSS.2000.926982
[26]	Razzaque, M.A., Bleakley, C. and Dobson, S. (2013) Compression in Wireless Sensor Networks: A Survey and Comparative Evaluation. ACM Transactions on Sensor Networks, 10, 5:1-5:44.
[27]	Alippi, C., Anastasi, G., Di Francesco, M. and Roveri, M. (2009) Energy Management in Wireless Sensor Networks with Energy-Hungry Sensors. IEEE Instrumentation & Measurement Magazine, 12, 16-23. http://dx.doi.org/10.1109/MIM.2009.4811133
[28]	Razzaque, M.A. and Dobson, S. (2014) Energy-Efficient Sensing in Wireless Sensor Networks Using Compressed Sensing. Sensors, 14, 2822-2859. http://dx.doi.org/10.3390/s140202822
[29]	Takhar, D., Bansal, V., Wakin, M., Duarte, M., Baron, D., Laska, J., Kelly, K.F. and Baraniuk, R.G. (2006) A Compressed Sensing Camera: New Theory and an Implementation Using Digital Micromirrors. Proceedings of Computational Imaging IV at SPIE Electronic Imaging, San Jose, January 2006, 1-10.
[30]	Foucart, S. and Rauhut, H. (2013) A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis, Springer Science+Business Media, New York.
[31]	Fornasier, M. (2010) Numerical Methods for Sparse Recovery. In: Theoretical Foundations and Numerical Methods for Sparse Recovery, Radon Series on Computational and Applied Mathematics, de Gruyter, Berlin, 1-110.
[32]	Rauhut, H. (2010) Compressive Sensing and Structured Random Matrices. In: Theoretical Foundations and Numerical Methods for Sparse Recovery, Radon Series on Computational and Applied Mathematics, de Gruyter, Berlin, 1-94.
[33]	Candès, E.J. (2006) Compressive Sampling. Proceedings of the International Congress of Mathematicians, Madrid, 22-30 August 2006, 1-20.
[34]	Candès, E. and Wakin, M. (2008) An Introduction to Compressive Sampling. IEEE Signal Processing Magazine, 25, 21-30. http://dx.doi.org/10.1109/MSP.2007.914731
[35]	Romberg, J. (2008) Imaging via Compressive Sampling. IEEE Signal Processing Magazine, 25, 14-20. http://dx.doi.org/10.1109/MSP.2007.914729
[36]	Fornasier, M. and Rauhut, H. (2011) Compressive Sensing. In: Scherzer, O., Ed., Handbook of Mathematical Methods in Imaging, Chapter in Part 2, Springer, Berlin, 1-49.
[37]	Baraniuk, R., et al. Compressive Sensing Resources. http://www-dsp.rice.edu/cs
[38]	Tao, T. “What’s New” Blog. http://terrytao.wordpress.com
[39]	http://www.acm.caltech.edu/l1magic