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

doi:10.1007/s11704-015-3326-8

Front. Comput. Sci.

2015, Vol. 9

Issue (5) : 665-677 https://doi.org/10.1007/s11704-015-3326-8

REVIEW ARTICLE

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

Kezhi LI¹, Shuang CONG²(

)

¹. Automatic Complex Communication Networks, Signal and Systems Center, Royal Institute of Technology (KTH), Stockholm 10044, Sweden
². Department of Automation, University of Science and Technology of China, Hefei 230027, China

Download: PDF(513 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Shuang CONG

Issue Date: 24 September 2015

Cite this article:

Kezhi LI,Shuang CONG. State of the art and prospects of structured sensing matrices in compressed sensing[J]. Front. Comput. Sci., 2015, 9(5): 665-677.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-015-3326-8
https://academic.hep.com.cn/fcs/EN/Y2015/V9/I5/665

1	C Shannon. Communication in the presence of noise. Proceedings of the Institute of Radio Engineers (IRE), 1949, 37(1): 10−21 https://doi.org/10.1109/jrproc.1949.232969
2	H Nyquist. Certain topics in telegraph transmission theory. Transactions of the American Institute of Electrical Engineers, 1928, 47(2): 617−644 https://doi.org/10.1109/T-AIEE.1928.5055024
3	D L Donoho. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(7): 1289−1306 https://doi.org/10.1109/TIT.2006.871582
4	E Candès, J Romberg, T Tao. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory, 2006, 52(2): 489−509 https://doi.org/10.1109/TIT.2005.862083
5	E Candès, T Tao. Near optimal signal recovery from random projections: universal encoding strategies. IEEE Transactions on Information Theory, 2006, 52: 5406−5425 https://doi.org/10.1109/TIT.2006.885507
6	E Candès, M Wakin. An introduction to compressive sampling. IEEE Signal Processing Magazine, 2008, 25(2): 21−30 https://doi.org/10.1109/MSP.2007.914731
7	R Baraniuk. Compressive sensing. IEEE Signal Processing Magazine, 2007, 24(4): 118−121 https://doi.org/10.1109/MSP.2007.4286571
8	E Candès, J Romberg. Practical signal recovery from random projections. Proceedings of Society of Photographic Instrumentation Engineers, 2005, 5674: 76−86
9	J Haupt, R Nowak. Signal reconstruction from noisy random projections. IEEE Transactions on Information Theory, 2006, 52(9): 4036−4048 https://doi.org/10.1109/TIT.2006.880031
10	E Candès, J Romberg. Quantitative robust uncertainty principles and optimally sparse decompositions. Foundations of Computational Mathematics, 2006, 6(8): 227−254 https://doi.org/10.1007/s10208-004-0162-x
11	D Donoho, M Elad, V Temlyakov. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 2006, 52(1): 6−18 https://doi.org/10.1109/TIT.2005.860430
12	J Tropp, A Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 2007, 53(12): 4655−4666 https://doi.org/10.1109/TIT.2007.909108
13	R Calderbank, S Howard, S Jafarpour. 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 https://doi.org/10.1109/JSTSP.2010.2043161
14	D L Donoho, M Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via l 1 minimization. Proceedings of National Academy of Sciences, 2003, 100(5): 2197−2202 https://doi.org/10.1073/pnas.0437847100
15	J Tropp. Greed is good: algorithmic results for sparse approximation. IEEE Transactions on Information Theory, 2004, 50(10): 2231−2242 https://doi.org/10.1109/TIT.2004.834793
16	E Candès, Y Plan. Near-ideal model selection by l 1 minimization. Annals of Statistics, 2009, 37(5): 2145−2177 https://doi.org/10.1214/08-AOS653
17	M Rudelson, R Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics, 2008, 61(8): 1025−1045 https://doi.org/10.1002/cpa.20227
18	M Duarte, Y Eldar. Structured compressed sensing: From theory to applications. IEEE Transactions on Signal Processing, 2011, 59(9): 4053−4085 https://doi.org/10.1109/TSP.2011.2161982
19	E Candès, Y Plan. A probabilistic and RIPless theory of com-pressed sensing. IEEE Transaction on Information Theory, 2011, 57(11): 7235−7254 https://doi.org/10.1109/TIT.2011.2161794
20	E Candès, J Romberg. Sparsity and incoherence in compressive sampling. Inverse Problems, 2007, 23(6): 969−985 https://doi.org/10.1088/0266-5611/23/3/008
21	W U Bajwa, J D Haupt, G M Raz, S J Wright, R D Nowak. Toeplitzstructured compressed sensing matrices. In: Proceedings of IEEE/SP the 14th Workshop on Statistical Signal Processing. 2007, 8: 294−298
22	J Haupt, W Bajwa, G Raz, R Nowak. Toeplitz compressed sensing matrices with applications to sparse channel estimation. IEEE Transactions on Information Theory, 2010, 56(11): 5862−5875 https://doi.org/10.1109/TIT.2010.2070191
23	H Rauhut. Circulant and Toeplitz matrices in compressed sensing. In: Proceedings of Signal Processing with Adaptive Sparse Structured Representations. 2009, 1−6
24	J Tropp, J Laska, M Duarte, J Romberg, R Baraniuk. Beyond Nyquist: Effcient sampling of sparse bandlimited signals. IEEE Transactions on Information Theory, 2010, 56(1): 520−544 https://doi.org/10.1109/TIT.2009.2034811
25	J Romberg. Compressive sensing by random convolution. SIAM Journal on Imaging Scicences, 2009, 2(4): 1098−1128 https://doi.org/10.1137/08072975X
26	J Romberg. Sensing by random convolution. In: Proceedings of the 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2007, 137−140 https://doi.org/10.1109/camsap.2007.4497984
27	T Do, L Gan, N Nguyen, T Tran. Fast and efficient compressive sensing using structurally random matrices. IEEE Transactions on Signal Processing, 2012, 60(1): 139−154 https://doi.org/10.1109/TSP.2011.2170977
28	T Do, T Tran and L Gan. Fast compressive sampling with structurally random matrices. In: Proceedings of IEEE International Conference on Acoustics Speech, Signal Process. 2008, 3369−3372 https://doi.org/10.1109/icassp.2008.4518373
29	H Rauhut, J Romberg, J Tropp. Restricted isometries for partial random circulate matrices. Applied and Computational Harmonic Analysis, 2012, 32(2): 242−254 https://doi.org/10.1016/j.acha.2011.05.001
30	H J Zepernick, A Finger. Pseudo Random Signal Processing: Theory and Application. West Sussex: Wiley, 2005 https://doi.org/10.1002/9780470866597
31	P Z Fan, M Darnell. The synthesis of perfect sequences. Lec-ture notes in Computer Science, 1995, 1025: 63−73 https://doi.org/10.1007/3-540-60693-9_9
32	L Applebaum, S Howard, S Searle, R Calderbank. Chirp sensing codes: deterministic compressed sensing measurements for fast recovery. Applied and Computational Harmonic Analysis, 2009, 26(2): 283−290 https://doi.org/10.1016/j.acha.2008.08.002
33	L Gan, K Li, C Ling. Golay meets hadamard: golay-paired hadamard matrices for fast compressed sensing. In: Proceedings of Information Theory Workshop. 2012, 637−641 https://doi.org/10.1109/itw.2012.6404755
34	K Li, L Gan, C Ling. Convolutional compressed sensing using deterministic sequences. IEEE Transaction on Signal Processing, 2013, 61(3): 740−752 https://doi.org/10.1109/TSP.2012.2229994
35	L Gan, K Li, C Ling. Novel Toeplitz sensing matrices for compressing radar imaging. In: Proceedings of International Workshop on Compressed Sensing Applied to Radar Imaging. 2012, 1−6
36	L Gan. Block compressed sensing of natural images. In: Proceedings of International Conference on Digital Signal Processing. 2007, 403−406
37	F Sebert, Y M Zou, L Ying. Toeplitz block matrices in compressed sensing and their applications in imaging. In: Proceedings of International Conference on Information Technology and Applications. 2008, 47−50 https://doi.org/10.1109/itab.2008.4570587
38	L Gan, T Do, T Tran. Fast compressive imaging using scram-bled block Hadamard ensemble. In: Proceedings of European Signal Processing Conference. 2008, 1−6
39	R A Devore. Deterministic construction of compressed sensing matrices. Journal of Complexity, 2007, 23: 918−925 https://doi.org/10.1016/j.jco.2007.04.002
40	V Saligrama. Deterministic designs with deterministic guarantees: Toeplitz compressed sensing matrices, sequence design and system identfication. IEEE Transactions on Information Theory, 2012, 99 https://doi.org/10.1109/tit.2012.2206951
41	M A Iwen. Simple deterministically constructible RIP matrices with sub-linear Fourier sampling requirements. In: Proceedings of Conference in Information Sciences and Systems. 2008, 870−875
42	H Monajemi, S Jafarpour, M Gavish, L D. Donoho, S Ambikasaran, S Bacallado, D Bharadia, Y Chen, Y Choi, M Chowdhury. 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 https://doi.org/10.1073/pnas.1219540110
43	S Howard, A Calderbank, and S Searle, 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 https://doi.org/10.1109/ciss.2008.4558486
44	N Ailon, E Liberty. Fast dimension reduction using rademacher series on dual BCH codes. In: Proceedings of Annual ACM-SIAM Symposium on Discrete Algorithms. 2008, 1−6
45	R Calderbank, S Howard, S Jafarpour. A sublinear algorithm for sparse reconstruction with l 2/l 2 recovery guarantees. In: Proceedings of the 3rd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. 2009, 209−212
46	N Y Yu. Deterministic compressed sensing matrices from multiplicative character sequences. In: Proceedings of the 45th Annual Conference on Information Sciences and Systems. 2011, 1−5 https://doi.org/10.1109/ciss.2011.5766223
47	W Alltop. Complex sequences with low periodic correlations. IEEE Transaction on Information Theory, 1980, 26(3): 350−354 https://doi.org/10.1109/TIT.1980.1056185
48	T Strohmer, R Heath. Grassmanian frames with applications to coding and communication. Applied and Computational Harmonic Analysis, 2003, 14: 257−275 https://doi.org/10.1016/S1063-5203(03)00023-X
49	W Chen, M Rodrigues, I Wassell. Projection design for statistical compressive sensing: a tight frame based approach. IEEE Transactions on Signal Processing, 2013, 61(8): 2016−2029 https://doi.org/10.1109/TSP.2013.2245661
50	H Rauhut. 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	M Mishali and Y Eldar, 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 https://doi.org/10.1109/JSTSP.2010.2042414
53	K Li, C Ling, L Gan. Deterministic compressed sensing matrices: where Toeplitz meets Golay. In: Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing. 2011, 3748−3751 https://doi.org/10.1109/icassp.2011.5947166
54	K Li, S Gao, C Ling, L Gan. Wynerziv coding for distributed compressive sensing. In: Proceedings of Workshop of Signal Processing with Adaptive Sparse Structured Representations, 2011, 1−6
55	M Lustig, D Donoho, J Santos, J Pauly. Compressed sensing MRI. IEEE Signal Processing Magazine, 2008, 25(2): 72−82 https://doi.org/10.1109/MSP.2007.914728
56	I F Gorodnitsky, J George, B Rao. Neuromagnetic source imaging with FOCUSS: a recursive weighted minimum norm algorithm. Electrocephalography and Clinical Neurophysiology, 1995, 95: 231−251 https://doi.org/10.1016/0013-4694(95)00107-A
57	M Lustig, D Donoho, J M Pauly. Sparse MRI: The application of compressed sensing for rapid MR imaging. Magnetic Resonance in Medicine, 2007, 58(6): 1182−1195 https://doi.org/10.1002/mrm.21391
58	M F Duarte, M A Davenport, D Takhar, J N Laska, T Sun, K F Kelly, R G Baraniuk. Single pixel imaging via compressive sampling. IEEE Signal Processing Magazine, 2008, 83−91 https://doi.org/10.1109/MSP.2007.914730
59	J Sampsell. 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	D Takhar, J Laska, M Wakin, M Duarte, D Baron, S Sarvotham, K Kelly, R Baraniuk. A new compressive imaging camera architecture using optical-domain compression. Computational Imaging IV, 2006, 606: 43−52 https://doi.org/10.1117/12.659602
61	W L Chan, K Charan, D Takhar, K F Kelly, R G Baraniuk, D M Mittleman. A single-pixel terahertz imaging system based on compressive sensing. Applied Physics Letters, 2008, 93(12) https://doi.org/10.1063/1.2989126
62	H Shen, N Newman, L Gan, S Zhong, Y Huang, Y Shen. 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 https://doi.org/10.1109/ICIMW.2010.5612977
63	A Gilbert, P Indyk. Sparse recovery using sparse matrices. Proceedings of the IEEE, 2010, 98(6): 937−947 https://doi.org/10.1109/JPROC.2010.2045092
64	W Xu, B Hassibi. Efficient compressive sensing with deterministic guarantees using expander graphs. In: Proceeding of IEEE Information Theory Workshop. 2007, 414−419 https://doi.org/10.1109/itw.2007.4313110
65	F Krzakala, M Mezard, F Sausset, Y F Sun, L Zdeborova. Statisticalphysics-based reconstruction in compressed sensing. Physical Review X2, 021005, 2012 https://doi.org/10.1103/PhysRevX.2.021005

[1]

Supplementary Material-Highlights in 3-page ppt

Download

[1]	Dantong OUYANG, Mengting LIAO, Yuxin YE. Lightweight axiom pinpointing via replicated driver and customized SAT-solving[J]. Front. Comput. Sci., 2023, 17(2): 172315-.
[2]	Shiguang LIU, Ziqi LIU. Line drawing via saliency map and ETF[J]. Front. Comput. Sci., 2022, 16(5): 165707-.
[3]	Pengfei GAO, Yongjie XU, Fu SONG, Taolue CHEN. Model-based automated testing of JavaScript Web applications via longer test sequences[J]. Front. Comput. Sci., 2022, 16(3): 163204-.
[4]	Di MA, Songcan CHEN. Bayesian compressive principal component analysis[J]. Front. Comput. Sci., 2020, 14(4): 144303-.
[5]	Yuxin YE, Xianji CUI, Dantong OUYANG. Extracting a justification for OWL ontologies by critical axioms[J]. Front. Comput. Sci., 2020, 14(4): 144305-.
[6]	Huiping LIU, Cheqing JIN, Aoying ZHOU. Popular route planning with travel cost estimation from trajectories[J]. Front. Comput. Sci., 2020, 14(1): 191-207.
[7]	Haiyang ZHOU, Yunzhi YU. Applying rotation-invariant star descriptor to deep-sky image registration[J]. Front. Comput. Sci., 2018, 12(5): 1013-1025.
[8]	Xiang FENG, Wanggen WAN, Richard Yi Da XU, Haoyu CHEN, Pengfei LI, J. Alfredo SÁNCHEZ. A perceptual quality metric for 3D triangle meshes based on spatial pooling[J]. Front. Comput. Sci., 2018, 12(4): 798-812.
[9]	Zhilin LI, Wenbo XU, Xiaobo ZHANG, Jiaru LIN. A survey on one-bit compressed sensing: theory and applications[J]. Front. Comput. Sci., 2018, 12(2): 217-230.
[10]	Junge ZHANG, Kaiqi HUANG, Tieniu TAN, Zhaoxiang ZHANG. Local structured representation for generic object detection[J]. Front. Comput. Sci., 2017, 11(4): 632-648.
[11]	Vahid MEHRDAD,Hossein EBRAHIMNEZHAD. 3D object retrieval based on histogram of local orientation using one-shot score support vector machine[J]. Front. Comput. Sci., 2015, 9(6): 990-1005.
[12]	Franco RONCHETTI,Facundo QUIROGA,Laura LANZARINI,Cesar ESTREBOU. Distribution of action movements (DAM): a descriptor for human action recognition[J]. Front. Comput. Sci., 2015, 9(6): 956-965.
[13]	Chuanping HU,Zheng XU,Yunhuai LIU,Lin MEI. Video structural description technology for the new generation video surveillance systems[J]. Front. Comput. Sci., 2015, 9(6): 980-989.
[14]	K C SANTOSH,Laurent WENDLING. Character recognition based on non-linear multi-projection profiles measure[J]. Front. Comput. Sci., 2015, 9(5): 678-690.
[15]	Bojun XIE,Yi LIU,Hui ZHANG,Jian YU. Efficient image representation for object recognition via pivots selection[J]. Front. Comput. Sci., 2015, 9(3): 383-391.

Viewed

Full text

Abstract

Cited

Shared

Discussed