Survey on construction of measurement matrices in compressive sensing

doi:10.11772/j.issn.1001-9081.2017.01.0188

Abstract

Abstract: The construction of measurement matrix in compressive sensing varies widely and is on the development constantly. In order to sort out the research results and acquire the development trend of measurement matrix, the process of measurement matrix construction was introduced systematically. Firstly, compared with the traditional signal acquisition theory, the advantages of high resource utilization and small storage space were expounded. Secondly, on the basis of the framework of compressive sensing and focusing on four aspects:the construction principle, the generation method, the structure design of measurement matrix and the optimal method, the construction of measurement matrix in compressive sensing was summarized, and advantages of different principles, generations and structures were introduced in detail. Finally, based on the research results, the development directions of measurement matrix were prospected.

Key words: Compressive Sensing (CS), measurement matrix, Restricted Isometry Property (RIP), signal reconstruction, signal acquisition

摘要： 压缩感知测量矩阵构造方式多样并不断发展，为梳理现有研究成果，掌握测量矩阵发展动态，对压缩感知测量矩阵构造进行系统介绍。首先，针对传统信号采集理论存在的信息冗余问题，阐述了压缩感知理论在信号采集过程中资源利用率高、存储空间小的优势；其次，以压缩感知理论框架为基础，从测量矩阵构造原则、测量矩阵产生方法、测量矩阵结构设计、测量矩阵优化方法四个方面，对压缩感知测量矩阵构造进行分析，讨论了测量矩阵构造过程中不同原则、结构、方法的优势；最后，在总结现有研究成果的基础上，对测量矩阵的发展方向进行了展望。

关键词: 压缩感知, 测量矩阵, 有限等距性质, 信号重构, 信号采集

CLC Number:

TP301.6

WANG Qiang, ZHANG Peilin, WANG Huaiguang, YANG Wangcan, CHEN Yanlong. Survey on construction of measurement matrices in compressive sensing[J]. Journal of Computer Applications, 2017, 37(1): 188-196.

王强, 张培林, 王怀光, 杨望灿, 陈彦龙. 压缩感知中测量矩阵构造综述[J]. 计算机应用, 2017, 37(1): 188-196.

References

[1] CANDES E J, ROMBERG J. Quantitative robust uncertainty principles and optimally sparse decompositions[J]. Foundation of Computational Mathematics, 2006, 6(2):227-254.
[2] CANDES E J, ROMBERG J K, TAO T. Robust uncertainty principles:exact signal reconstruction from high incomplete frequency information[J]. IEEE Transactions on Information Theory, 2006, 52(2):489-509.
[3] CANDES E J, ROMBERG J K, TAO T. Stable signal recovery from incomplete and inaccurate measurements[J]. Communications on Pure and Applied Mathematics, 2006, 59(8):1207-1223.
[4] BOUCHHIMA B, AMARA R, ALOUANE T H. Design of optimal matrices for compressive sensing:application to environmental sounds[C]//Proceedings of the 2015 Signal Processing Conference. Piscataway, NJ:IEEE, 2015:130-134.
[5] DONOHO D L. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4):1289-1306.
[6] 王强,李佳,沈毅.压缩感知中确定性测量矩阵构造算法综述[J].电子学报,2013,41(10):2041-2050.(WANG Q, LI J, SHEN Y. A survey on deterministic measurement matrix construction algorithms in compressive sensing[J]. Acta Electronica Sinica, 2013, 41(10):2041-2050.)
[7] 焦李成,杨淑媛,刘芳,等.压缩感知回顾与展望[J].电子学报,2011,39(7):1651-1662.(JIAO L C, YANG S Y, LIU F, et al. Development and prospect of compressive sensing[J]. Acta Electronica Sinica, 2011, 39(7):1651-1662.)
[8] ELAD M, AHARON M. Image denoising via sparse and redundant representations over learned dictionaries[J]. IEEE Transactions on Information Theory, 2006, 15(12):3736-3745.
[9] AHARON M, ELAD M, BRUCKSTEIN A M. The K-SVD:an algorithm for designing of overcomplete dictionaries for sparse representations[J]. IEEE Transactions on Image Processing, 2006, 54(11):4311-4322.
[10] CANDES E J, TAO T. Decoding by linear programming[J]. IEEE Transactions on Information Theory, 2005, 51(12):4203-4215.
[11] CANDES E J. The restricted isometry property and its implication for compressed sensing[J]. Comtes Rendus Mathematique, 2008, 346(9/10):589-592.
[12] MALLAT S, ZHANG Z F. Matching pursuits with time frequency dictionaries[J]. IEEE Transactions on Signal Processing, 1993, 41(12):3397-3415.
[13] TROPP J A, GILBERT A C. Signal recovery from random measurement via orthogonal matching pursuit[J]. IEEE Transactions on Information Theory, 2007, 53(12):4655-4666.
[14] NEEDELL D, TROPP J A. CoSaMP:iterative signal recovery from incomplete and inaccurate samples[J]. Applied and Computational Harmonic Analysis, 2008, 26(3):301-321.
[15] CHEN S B, DONOHO D L, SAUNDERS M A. Atomic decomposition by basis pursuit[J]. SIAM Journal on Scientific Computing, 1998, 20(1):33-61.
[16] APPLEBAUM L, HOWARD S, SEARLE S, et al. Chirp sensing codes:deterministic compressed sensing measurements for fast recovery[J]. Applied and Computational Harmonic Analysis, 2009, 26(2):283-290.
[17] ROMBERG J. Compressive sensing by random convolution[J]. SIAM Journal on Imaging Sciences, 2009, 2(4):1098-1128.
[18] CANDES E J, TAO T. Near-optimal signal recovery from random projections:universal encoding strategies?[J]. IEEE Transactions on Information Theory, 2006, 52(12):5406-5425.
[19] ARMIN E, LUN Y H, CHRISTOPHER J R, et al. The restricted isometry property for random block diagonal matrices[J]. Applied & Computational Harmonic Analysis, 2015, 38(1):1-31.
[20] BARANIUK R, DAVENPORT M, DEVORE R, et al. A simple proof of the restricted isometry property for random matrices[J]. Constructive Approximation, 2008, 28(3):253-263.
[21] JOHNSON W, LINDENSTRAUSS J. Extensions of Lipschitz maps into a Hilbert space[J]. Contemporary Mathematics, 1984, 26:189-206.(无期)
[22] XU W, HASSIBI B. Efficient compressive sensing with deterministic guarantees using expander graphs[C]//ITW'07:Proceedings of the 2007 Information Theory Workshop. Piscataway, NJ:IEEE, 2007:414-419.
[23] BERINDE R, GILBERT A C, INDYK P, et al. Combining geometry and combinatorics:a unified approach to sparse signal[EB/OL].[2016-05-15] . https://arxiv.org/abs/0804.4666.
[24] CALDERBANK R, HOWARD S, JAFARPOUR S. Construction of a large class of deterministic sensing matrices that satisfy a statistical isometry property[J]. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):358-374.
[25] RAGINSKY M, JAFARPOUR S, HARMANY Z T, et al. Performance bounds for expander-based compressed sensing in Poisson noise[J]. IEEE Transactions on Signal Processing, 2011, 59(9):4139-4153.
[26] DONOHO D L, ELAD M. Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization[J]. Proceedings of the National Academy of Sciences, 2003, 100(5):2197-2202.ELAD M. Optimized projections for compressed sensing[J]. IEEE Transactions on Signal Processing, 2007, 55(12):5695-5702.文献26与49是同一个文献,是删除其中一个,还是替换其中一个?若删除,相应地正文中的引用顺序和后面的文献列表编号要相应调整。若替换为另一个,则最为简单,建议替换,注意,替换的文献不要与其他的文献再重复了。回复:建议将文献26进行替换,替换为:DONOHO D L,ELAD M. Optimally sparse representation in general(nonorthogonal) dictionaries via l1 minimization[J]. Proceedings of the National Academy of Sciences, 2003, 100(5):2197-202.
[27] TROPP J A. Greed is good:algorithmic results for sparse approximation[J]. IEEE Transactions on Information Theory, 2004, 50(10):2231-2242.
[28] RAUHUT H, SCHNASS K, VANDERGHEYNST P. Compressed sensing and redundant dictionaries[J]. IEEE Transactions on Information Theory, 2008, 54(5):2210-2219.
[29] ELAD M, BRUCKSTEIN A M. A generalized uncertainty principle and sparse representation in pairs bases[J]. IEEE Transactions on Information Theory, 2002, 48(9):2558-2567.
[30] KASHIN B S, TEMLYAKOV V N. A remark on compressed sensing[J]. Mathematics and Statistics, 2007, 42(5/6):748-755.
[31] ZHANG G, JIAO S, XU X, et al. Compressed sensing and reconstruction with Bernoulli matrices[C]//Proceedings of the 2010 International Conference on Information and Automation. Piscataway, NJ:IEEE, 2010:455-460
[32] GILBERT A C, GUHA S, INDYK P. Near-optimal sparse Fourier representation via sampling[C]//Proceedings on the 34th Annual ACM Symposium on Theory of Computing. New York:ACM, 2006:152-161.
[33] BERINDE R, INDYK P. Sparse recovery using sparse random matrices[C]//LATIN 2010:Proceedings of the 9th Latin American Symposium on Theoretical Informatics, LNCS 6034. Berlin:Springer, 2010:157-157.
[34] ZENG L, ZHANG X, CHEN L, et al. Deterministic construction of Toeplitzed structurally chaotic matrix for compressed sensing[J]. Circuits, Systems, and Signal Processing, 2015, 34(3):797-813.DEVORE R A. Deterministic constructions of compressed sensing matrices[J]. Journal of Complexity, 2007, 23(4/5/6):918-925.文献34与35是同一个文献,是删除其中一个,还是替换其中一个?若删除,相应地正文中的引用顺序和后面的文献列表编号要相应调整。若替换为另一个,则最为简单,建议替换,注意,替换的文献不要与其他的文献再重复了。回复:文献34替换为:ZENG L, ZHANG X, CHEN L, et al. Deterministic Construction of Toeplitzed Structurally Chaotic Matrix for Compressed Sensing[J]. Circuits, Systems, and Signal Processing, 2015, 34(3):797-813.
[35] DEVORE R A. Deterministic construction of compressed sensing[J]. Journal of Complexity, 2007, 23(4/5/6):918-925.
[36] NAM Y Y, NA Z. Deterministic construction of real-valued ternary sensing matrices using optical orthogonal codes[J]. IEEE Signal Processing Letters, 2013, 20(11):1106-1109.
[37] BRICKELL E F, WEI V K. Optical orthogonal codes and cyclic block designs[J].Congr NumerCongressus Numerantium补充全称, 1987, 58:175-192.
[38] AMINI A, MONTAZERHODJAT V, MARVASTI F. Matrices with small coherence using parry block codes[J]. IEEE Transactions on Signal Processing, 2012, 60(1):172-181.
[39] LI S X, GAO F, GE G N, et al. Deterministic construction of compressed sensing matrices via algebraic curves[J]. IEEE Transactions on Information Theory, 2012, 58(8):5035-5041.
[40] GE X, XIA S T. LDPC codes based on Berlekamp-Justesen codes with large stopping distances[C]//ITW'06:Proceedings of the 2006 IEEE Information Theory Workshop. Piscataway, NJ:IEEE, 2006:214-218.
[41] DIMAKIS A G, SMARANDACHE R, VONTOBEL P O. LDPC codes for compressed sensing[J]. IEEE Transactions on Information Theory, 2010, 58(5):3093-3114.
[42] DO T T, TRAN T D, LU G. Fast compressive sampling with structurally random matrices[C]//Proceedings of the 2008 IEEE International Conference on Acoustics. Piscataway, NJ:IEEE, 2008:3369-3372.
[43] 李浩.用于压缩感知的确定性测量矩阵研究[D].北京:北京交通大学,2011:26-38.(LI H. Research on deterministic measurement matrix for compressed sensing[D]. Beijing:Beijing Jiaotong University, 2011:26-38.)
[44] BAJWA W U, HAUPT J D, RAZ G M, et al. Toeplitz-structured compressed sensing matrices[C]//SSP' 07:Proceedings of the 2007 IEEE/SP 14th Workshop on Statistical Signal Processing. Washington, DC:IEEE Computer Society, 2007:294-298.
[45] SALIGRAMA V. Deterministic designs with deterministic guarantees:Toeplitz compressed sensing matrices, sequence design and system ID[J]. IEEE Transactions on Information Theory, 2012, 99(PP):1-1.
[46] SEBERT F, ZOU Y M, YING L. Toeplitz block matrices in compressed sensing and their applications in imagine[C]//Proceedings of the 2008 International Conference on Information Technology and Applications in Biomedicine, Piscataway, NJ:IEEE, 2008:47-50.
[47] SUN J M, WANG S, DONG Y. Sparse block circulant matrices for compressed sensing[J]. IET Communications, 2013, 7(13):1412-1418.
[48] 夏树涛,刘璐,刘鑫吉.基于Berlekamp-Justesen码的压缩感知确定性测量矩阵的构造[J].电子与信息学报,2015,37(4):763-769.(XIA S T, LIU L, LIU X J. Deterministic constructions of compressive sensing matrices based on Berlekamp-Justesen codes[J]. Journal of Electronics & Information Technology, 2015, 37(4):763-769.
[49] ELAD M. Optimized projections for compressed sensing[J]. IEEE Transactions on Signal Processing, 2007, 55(12):5695-5702.
[50] 张劲东,张弓,潘汇,等.基于滤波器结构的压缩感知雷达感知矩阵优化[J].航空学报,2013,34(4):866-868.(ZHANG J D, ZHANG G, PAN H, et al. Optimized sensing matrix design of filter structure based compressed sensing radar[J]. Acta Aeeronautica et Astronautica Sinica, 2013, 34(4):866-868.)
[51] LI B, SHEN Y, LI J. Dictionaries construction using alternating projection method in compressive sensing[J]. IEEE Signal Processing Letters, 2011, 18(11):662-666.
[52] 赵瑞珍,秦周,胡绍海,等.一种特征值分解的测量矩阵优化方法[J].信号处理,2012,38(5):654-656.(ZHAO R Z, QIN Z, HU S H, et al. An optimization method for measurement matrix based on eigenvalue decomposition[J]. Signal Processing, 2012, 38(5):654-656.)
[53] DUARTE-CARVAJALINO J M, SAPIRO G. Learning to sense sparse signal:simultaneous sensing matrix and sparsifying dictionary optimization[J]. IEEE Transactions on Imagine Processing, 2009, 18(7):1395-1408.
[54] ABOLGHASEMI V, SAIDEH F, BAHADOR M. On optimization of the measurement matrix for compressive sensing[C]//EUSIPCO 2010:Proceedings of the 18th European Signal Processing Conference, 2010:23-27.
[55] ZHANG J D, ZHU D Y, ZHANG G. Adaptive compressed sensing radar oriented towards cognitive detection in dynamic sparse target scene[J]. IEEE Transactions on Signal Processing, 2012, 60(4):1718-1729.