State of the art and prospects of structured sensing matrices in compressed sensing

Abstract

Compressed sensing (CS) enables people to acquire the compressed measurements directly and recover sparse or compressible signals faithfully even when the sampling rate is much lower than the Nyquist rate. However, the pure random sensing matrices usually require huge memory for storage and high computational cost for signal reconstruction. Many structured sensing matrices have been proposed recently to simplify the sensing scheme and the hardware implementation in practice. Based on the restricted isometry property and coherence, couples of existing structured sensing matrices are reviewed in this paper, which have special structures, high recovery performance, and many advantages such as the simple construction, fast calculation and easy hardware implementation. The number of measurements and the universality of different structure matrices are compared.

Keywords

compressed sensing / structured sensing matrices / RIP / coherence

References

[1] Shannon C. Communication in the presence of noise. Proceedings of the Institute of Radio Engineers (IRE), 1949, 37(1): 10−21

[2] Nyquist H. Certain topics in telegraph transmission theory. Transactions of the American Institute of Electrical Engineers, 1928, 47(2): 617−644

[3] Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(7): 1289−1306

[4] Candès E, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 2006, 52(2): 489−509

[5] Candès E, Tao T. Near optimal signal recovery from random projections: universal encoding strategies. IEEE Transactions on Information Theory, 2006, 52: 5406−5425

[6] Candès E, Wakin M. An introduction to compressive sampling. IEEE Signal Processing Magazine, 2008, 25(2): 21−30

[7] Baraniuk R. Compressive sensing. IEEE Signal Processing Magazine, 2007, 24(4): 118−121

[8] Candès E, Romberg J. Practical signal recovery from random projections. Proceedings of Society of Photographic Instrumentation Engineers, 2005, 5674: 76−86

[9] Haupt J, Nowak R. Signal reconstruction from noisy random projections. IEEE Transactions on Information Theory, 2006, 52(9): 4036−4048

[10] Candès E, Romberg J. Quantitative robust uncertainty principles and optimally sparse decompositions. Foundations of Computational Mathematics, 2006, 6(8): 227−254

[11] Donoho D, Elad M, Temlyakov V. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 2006, 52(1): 6−18

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

[13] Calderbank R, Howard S, Jafarpour S. Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 358−374

[14] Donoho D L, Elad M. Optimally sparse representation in general (nonorthogonal) dictionaries via l ₁ minimization. Proceedings of National Academy of Sciences, 2003, 100(5): 2197−2202

[15] Tropp J. Greed is good: algorithmic results for sparse approximation. IEEE Transactions on Information Theory, 2004, 50(10): 2231−2242

[16] Candès E, Plan Y. Near-ideal model selection by l ₁ minimization. Annals of Statistics, 2009, 37(5): 2145−2177

[17] Rudelson M, Vershynin R. On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics, 2008, 61(8): 1025−1045

[18] Duarte M, Eldar Y. Structured compressed sensing: From theory to applications. IEEE Transactions on Signal Processing, 2011, 59(9): 4053−4085

[19] Candès E, Plan Y. A probabilistic and RIPless theory of com-pressed sensing. IEEE Transaction on Information Theory, 2011, 57(11): 7235−7254

[20] Candès E, Romberg J. Sparsity and incoherence in compressive sampling. Inverse Problems, 2007, 23(6): 969−985

[21] Bajwa W U, Haupt J D, Raz G M, Wright S J, Nowak R D. Toeplitzstructured compressed sensing matrices. In: Proceedings of IEEE/SP the 14th Workshop on Statistical Signal Processing. 2007, 8: 294−298

[22] Haupt J, Bajwa W, Raz G, Nowak R. Toeplitz compressed sensing matrices with applications to sparse channel estimation. IEEE Transactions on Information Theory, 2010, 56(11): 5862−5875

[23] Rauhut H. Circulant and Toeplitz matrices in compressed sensing. In: Proceedings of Signal Processing with Adaptive Sparse Structured Representations. 2009, 1−6

[24] Tropp J, Laska J, Duarte M, Romberg J, Baraniuk R. Beyond Nyquist: Effcient sampling of sparse bandlimited signals. IEEE Transactions on Information Theory, 2010, 56(1): 520−544

[25] Romberg J. Compressive sensing by random convolution. SIAM Journal on Imaging Scicences, 2009, 2(4): 1098−1128

[26] Romberg J. Sensing by random convolution. In: Proceedings of the 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2007, 137−140

[27] Do T, Gan L, Nguyen N, Tran T. Fast and efficient compressive sensing using structurally random matrices. IEEE Transactions on Signal Processing, 2012, 60(1): 139−154

[28] Do T, Tran T and Gan L. Fast compressive sampling with structurally random matrices. In: Proceedings of IEEE International Conference on Acoustics Speech, Signal Process. 2008, 3369−3372

[29] Rauhut H, Romberg J, Tropp J. Restricted isometries for partial random circulate matrices. Applied and Computational Harmonic Analysis, 2012, 32(2): 242−254

[30] Zepernick H J, Finger A. Pseudo Random Signal Processing: Theory and Application. West Sussex: Wiley, 2005

[31] Fan P Z, Darnell M. The synthesis of perfect sequences. Lec-ture notes in Computer Science, 1995, 1025: 63−73

[32] Applebaum L, Howard S, Searle S, Calderbank R. Chirp sensing codes: deterministic compressed sensing measurements for fast recovery. Applied and Computational Harmonic Analysis, 2009, 26(2): 283−290

[33] Gan L, Li K, Ling C. Golay meets hadamard: golay-paired hadamard matrices for fast compressed sensing. In: Proceedings of Information Theory Workshop. 2012, 637−641

[34] Li K, Gan L, Ling C. Convolutional compressed sensing using deterministic sequences. IEEE Transaction on Signal Processing, 2013, 61(3): 740−752

[35] Gan L, Li K, Ling C. Novel Toeplitz sensing matrices for compressing radar imaging. In: Proceedings of International Workshop on Compressed Sensing Applied to Radar Imaging. 2012, 1−6

[36] Gan L. Block compressed sensing of natural images. In: Proceedings of International Conference on Digital Signal Processing. 2007, 403−406

[37] Sebert F, Zou Y M, Ying L. Toeplitz block matrices in compressed sensing and their applications in imaging. In: Proceedings of International Conference on Information Technology and Applications. 2008, 47−50

[38] Gan L, Do T, Tran T. Fast compressive imaging using scram-bled block Hadamard ensemble. In: Proceedings of European Signal Processing Conference. 2008, 1−6

[39] Devore R A. Deterministic construction of compressed sensing matrices. Journal of Complexity, 2007, 23: 918−925

[40] Saligrama V. Deterministic designs with deterministic guarantees: Toeplitz compressed sensing matrices, sequence design and system identfication. IEEE Transactions on Information Theory, 2012, 99

[41] Iwen M A. Simple deterministically constructible RIP matrices with sub-linear Fourier sampling requirements. In: Proceedings of Conference in Information Sciences and Systems. 2008, 870−875

[42] Monajemi H, Jafarpour S, Gavish M, D. Donoho L, Ambikasaran S, Bacallado S, Bharadia D, Chen Y, Choi Y, Chowdhury M. Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices. In: Proceedings of the National Academy of Sciences, 2013, 110(4): 1181−1186

[43] Howard S, Calderbank A, and Searle S, A fast reconstruction algorithm for deterministic compressive sensing using second order reed muller codes. In: Proceedings of the 42nd Annual Conference on Information Sciences and Systems. 2008, 11−15

[44] Ailon N, Liberty E. Fast dimension reduction using rademacher series on dual BCH codes. In: Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms. 2008, 1−6

[45] Calderbank R, Howard S, Jafarpour S. A sublinear algorithm for sparse reconstruction with l ₂/l ₂ recovery guarantees. In: Proceedings of the 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2009, 209−212

[46] Yu N Y. Deterministic compressed sensing matrices from multiplicative character sequences. In: Proceedings of the 45th Annual Conference on Information Sciences and Systems. 2011, 1−5

[47] Alltop W. Complex sequences with low periodic correlations. IEEE Transaction on Information Theory, 1980, 26(3): 350−354

[48] Strohmer T, Heath R. Grassmanian frames with applications to coding and communication. Applied and Computational Harmonic Analysis, 2003, 14: 257−275

[49] Chen W, Rodrigues M, Wassell I. Projection design for statistical compressive sensing: a tight frame based approach. IEEE Transactions on Signal Processing, 2013, 61(8): 2016−2029

[50] Rauhut H. Compressive sensing and structured random matrices. In: Radon Series Computational and Applied Mathematics, Theoretical Foundations and Numerical Methods for Sparse Recovery. New York: DeGruyter, 2010, 9: 1−92

[51] Compressive sensing resources.

[52] Mishali M and Eldar Y, From theory to practice: sub-nyquist sampling of sparse wideband analog signals. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2): 375−391

[53] Li K, Ling C, Gan L. Deterministic compressed sensing matrices: where Toeplitz meets Golay. In: Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing. 2011, 3748−3751

[54] Li K, Gao S, Ling C, Gan L. Wynerziv coding for distributed compressive sensing. In: Proceedings of Workshop of Signal Processing with Adaptive Sparse Structured Representations, 2011, 1−6

[55] Lustig M, Donoho D, Santos J, Pauly J. Compressed sensing MRI. IEEE Signal Processing Magazine, 2008, 25(2): 72−82

[56] Gorodnitsky I F, George J, Rao B. Neuromagnetic source imaging with FOCUSS: a recursive weighted minimum norm algorithm. Electrocephalography and Clinical Neurophysiology, 1995, 95: 231−251

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

[58] Duarte M F, Davenport M A, Takhar D, Laska J N, Sun T, Kelly K F, Baraniuk R G. Single pixel imaging via compressive sampling. IEEE Signal Processing Magazine, 2008, 83−91

[59] Sampsell J. An overview of the digital micromirror device (DMD) and its application to projection displays. In: Proceedings of International Symposium Digest Technical Papers, 1993, 24: 1012−1015

[60] Takhar D, Laska J, Wakin M, Duarte M, Baron D, Sarvotham S, Kelly K, Baraniuk R. A new compressive imaging camera architecture using optical-domain compression. Computational Imaging IV, 2006, 606: 43−52

[61] Chan W L, Charan K, Takhar D, Kelly K F, Baraniuk R G, Mittleman D M. A single-pixel terahertz imaging system based on compressive sensing. Applied Physics Letters, 2008, 93(12)

[62] Shen H, Newman N, Gan L, Zhong S, Huang Y, Shen Y. Com-pressed terahertz imaging system using a spin disk. In: Proceedings of the 35th International Conference on Infrared, Millimeter and Terahertz Waves. 2010, 1−2

[63] Gilbert A, Indyk P. Sparse recovery using sparse matrices. Proceedings of the IEEE, 2010, 98(6): 937−947

[64] Xu W, Hassibi B. Efficient compressive sensing with deterministic guarantees using expander graphs. In: Proceeding of IEEE Information Theory Workshop. 2007, 414−419

[65] Krzakala F, Mezard M, Sausset F, Sun Y F, Zdeborova L. Statisticalphysics-based reconstruction in compressed sensing. Physical Review X2, 021005, 2012

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg