压缩感知中确定性测量矩阵构造算法综述

doi:10.3969/j.issn.0372-2112.2013.10.027

电子学报 ›› 2013, Vol. 41 ›› Issue (10): 2041-2050.DOI: 10.3969/j.issn.0372-2112.2013.10.027

压缩感知中确定性测量矩阵构造算法综述

王强, 李佳, 沈毅

哈尔滨工业大学控制科学与工程系, 黑龙江哈尔滨 150001

收稿日期:2012-10-30 修回日期:2013-02-08 出版日期:2013-10-25
- 作者简介:
- 王强 男,1975年出生于辽宁沈阳.哈尔滨工业大学控制科学与工程系教授、博士生导师.主要研究方向为多传感器数据融合,图像处理,智能检测技术等. E-mail:wangqiang@hit.edu.cn 李佳 男,1986年出生于河北衡水.2010年、2012年获得哈尔滨工业大学理学学士和工学硕士学位,现为哈尔滨工业大学博士研究生.研究方向为压缩感知、图像处理、无线传感器网络等. E-mail:hitsalijia@163.com沈毅男,1965年出生于吉林扶余.哈尔滨工业大学控制科学与工程系教授、博士生导师.主要研究方向为导航、制导与控制,故障诊断和数字超声成像技术.
- 基金资助:
- 国家自然科学基金 (No.61174016,No.61171197)

A Survey on Deterministic Measurement Matrix Construction Algorithms in Compressive Sensing

WANG Qiang, LI Jia, SHEN Yi

Department of Control Science and Engineering, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China

Received:2012-10-30 Revised:2013-02-08 Online:2013-10-25 Published:2013-10-25
- Supported by:
- National Natural Science Foundation of China (No.61174016, No.61171197)

摘要/Abstract

摘要： 测量矩阵在压缩感知中起着关键性的作用,其性能会影响原始信号的压缩与重构.现有的测量矩阵多数为随机的,它们在实际应用中有存储量大、效率低等缺点,且在硬件上难以实现,故构造确定性测量矩阵对压缩感知理论的推广与应用具有重要的意义.本文回顾了国内外学者在确定性测量矩阵构造方面的研究,着重对目前已有的构造算法进行详细的介绍和分类,最后根据多种指标综合评述了各种算法的性能.

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

Abstract: Measurement matrix,whose performance can affect the compression and reconstruction of original signal,plays a key role in compressive sensing.Most of the existing measurement matrices are random ones,which have shortcomings in practical application,such as large storage capacity,low efficiency and difficulty when implemented in the hardware.Therefore,it is of important practical significance to construct deterministic measurement matrix for the promotion and application of the compressive sensing theory.In this paper,the existing construction algorithms for deterministic measurement matrix are reviewed,introduced and classified in detail.Finally the performances of all algorithms are summarized in terms of common indicators.

Key words: compressive sensing(CS), deterministic measurement matrix, restricted isometry property, signal reconstruction

中图分类号:

TN911.7

王强, 李佳, 沈毅. 压缩感知中确定性测量矩阵构造算法综述[J]. 电子学报, 2013, 41(10): 2041-2050.

WANG Qiang, LI Jia, SHEN Yi . A Survey on Deterministic Measurement Matrix Construction Algorithms in Compressive Sensing[J]. Acta Electronica Sinica, 2013, 41(10): 2041-2050.

参考文献

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

[2] E Candès.Compressive sampling [A].Proceeding of IEEE ICM'06 [C].Madrid:IEEE Press,2006.1433-1452.

[3] 马坚伟,等.压缩感知及其应用:从稀疏约束到低秩约束优化[J].信号处理,2012,28(5):609-623. MA Jian-wei,et al.Compressive sensing and its application:from sparse to low-rank regularized optimization[J].Signal Processing,2012,28(5):609-623.

[4] M Aharon,et al.The K-SVD:An algorithm for designing of over complete dictionaries for sparse representations[J].IEEE Transactions on Image Processing,2006,54(11):4311-4322.

[5] C D Sigg,et al.Learning dictionaries with bounded self-coherence[J].IEEE Signal Processing Letter,2012,19(12):861-864.

[6] S Mallat.A Wavelet Tour of Signal Processing[M].San Diego:Academic Press,1996.

[7] H Rauhut,et al.Compressed sensing and redundant dictionaries[J].IEEE Transactions on Information Theory,2008,54(5):2210-2219.

[8] Marco F Duarte.Introduction to Compressive Sensing [OL].http://cnx.org/content/m37170/latest/?Collection=co-l11355/latest,2012-05-20.

[9] 焦李成,杨淑媛,等.压缩感知回顾与展望[J].电子学报,2011,7(7):1651-1662. JIAO Li-cheng,YANG Shu-yuan,et al.Development and prospect of compressive sensing[J].Acta Electronica Sinica,2011,7(7):1651-1662.(in Chinese)

[10] 杨海蓉,等.压缩传感理论与重构算法[J].电子学报,2011,39(1):142-148. YANG Hai-rong,et al.The theory of compressed sensing and reconstruction algorithm[J].Acta Electronica Sinica,2011,39(1):142-148.(in Chinese)

[11] S J Kim,et al.An interior-point method for large-scale l₁ regularized least squares[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(4):606-617.

[12] M A T Fiqueiredo,et al.Gradient projection for sparse reconstruction:Application to compressed sensing and other inverse problems[J].IEEE Journal of Selected Top-ics in Signal Processing,2007,1(4):586-597.

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

[14] W Dai,O Milenkovic.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Transactions on Information Theory,2009,55(5):2230-2249.

[15] D Needell,J A Tropp.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J].Applied and Computational Harmonic Analysis,2008,26(3):301-321.

[16] B S Chen,et al.Atomic decomposition by basis pursuit[J].SIAM Journal on Scientific Computing,1998,20(1):33-61.

[17] 李志林,等.一种有效的压缩感知图像重建算法[J].电子学报,2011,39(12):2796-2800. LI Zhi-lin,et al.An efficient algorithm for compressed sensing image reconstruction[J].Acta Electronica Sinica,2011,39(12):2796-2800.(in Chinese)

[18] E Candès,et al.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):489-509.

[19] J A Tropp.Greed is good:Algorithmic results for sparse approximation[J].IEEE Transactions on Information Theory,2004,50(10):2231-2242.

[20] M A Sustik,et al.On the existence of equiangular tight frames[J].Linear Algebra and its Applications,2007,426(2-3):619-635.

[21] R A Devore.Deterministic construction of compressed sensing matrices[J].Journal of complexity,2007,23(4-6):918-925.

[22] 李小波.基于压缩感知的测量矩阵研究 [D].北京:北京交通大学硕士学位论文,2010. Li Xiao-Bo.The Research of Measurement Matrix Based on Compressed Sensing [D].Beijing:A Dissertation of Beijing Jiao Tong University,2010.(in Chinese)

[23] S Jafarpour,et al.Efficient and robust compressed sensing using optimized expander graphs[J].IEEE Transactions on Information Theory,2009,55(9):4299-4308.

[24] M Raginsky,et al.Performance bounds for expander-based compressed sensing in Poisson noise[J].IEEE Transactions on Signal Processing,2011,59(9):4139-4153.

[25] V Guruswami,et al.Unbalanced expanders and randomness extractors from parvaresh-vardy codes[J].Journal of Association for Computing Machinery,2009,56(4):1-34.

[26] S Li,et al.Deterministic construction of compressed sensing matrices via algebraic curves[J].IEEE Transactions on Information Theory,2012,58(8):5035-5041.

[27] R Calderbank,et al.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.

[28] L Applebaum,et al.Chirp sensing codes:deterministic compressed sensing measurements for fast recovery[J].Applied and Computational Harmonic Analysis,2009,26(3):283-290.

[29] K Ni,S Datta,P Mahanti,et al.Efficient deterministic compressed sensing for images with chirps and reed-muller codes[J].SIAM Journal on Imaging Sciences,2011,4(3):931-953.

[30] A Amini,F Marvasti.Deterministic construction of binary,bipolar,and ternary compressed sensing matrices[J].IEEE Transactions on Information Theory,2011,57(4):2360-2370.

[31] A Amini,V Montazerhodjat,F Marvasti.Matrices with small coherence using p-Ary block codes[J].IEEE Transactions on Signal Processing,2012,60(1):172-180.

[32] 王开,等.准Toeplitz测量矩阵的有限等距性质分析[J].计算机应用研究,2011,28(4):1512-1514. Wang Kai,et al.RIP analysis for quasi-Toeplitz measurement matrices[J].Application Research of Computers,2011,28(4):1512-1514.(in Chinese)

[33] J Haupt,et al.Toeplitz compressed sensing matrices with applications to sparse channel estimation[J].IEEE Transactions on Information Theory,2010,56(10):5862-5875.

[34] V SaliGrama.Deterministic Designs with Deterministic Guarantees:Toeplitz Compressed Sensing Matrices,Sequence Design and System Identification.http://arxiv.org/abs/0806.4958v2,2008-07-28.

[35] R Holger.Circulant and Toeplitz matrices in compressed sensing [OL].http://arxiv.org/abs/0902.4394v1,2009-02-25.

[36] J A Tropp,et al.Designing structured tight frames via an alternating projection method[J].IEEE Transactions on Information Theory,2005,51(1):188-209.

[37] B Li,Y Shen,J Li.Dictionaries construction using alternating projection method in compressive sensing[J].IEEE Signal Processing Letters,2011,18(11):663-666.

[38] M Elad.Optimized projections for compressed sensing[J].IEEE Transactions on Signal Processing,2007,55(12):5695-5702.

[39] J M Duarte-Carvajalino,G Sapiro.Learning to sense sparse signals:simultaneous sensing matrix and sparsifying dictionary optimization[J].IEEE Transactions on Image Processing,2009,18(7):1395-1408.

[40] V Abolghasemi,et al.A robust approach for optimization of the measurement matrix in compressed sensing.Proceeding of IEEE IWCIP'10 [C].Elba:IEEE Press,2010.388-392.

[41] A Vahid,et al.A gradient-based alternating minimization approach for optimization of the measurement matrix in compressive sensing[J].Signal Processing,2012,92(3):999-1009.

[42] J Xu,Y Pi,Z Cao.Optimized projection matrix for compressive sensing[J].EURASIP Journal on Advances in Signal Processing,2010,(2):1-8.

[43] L Zelnik-Manor,K Rosenblum,Y C Eldar.Sensing matrix optimization for block-sparse decoding[J].IEEE Transactions on Signal Processing,2011,59(9):4300-4312.

[44] D J Love,et al.Grassmannian beamforming for multiple-input multiple-output wireless systems[J].IEEE Transactions on Information Theory,2003,49(10):2735-2747.

[45] P Xia,S Zhou,G B Giannakis.Achieving the welch bound with difference sets[J].IEEE Transactions on Information Theory,2005,51(5):1900-1907.

[46] D R Stinson.Combinatorial Designs:Constructions and Analysis[M].New York:Springer-Verlag,2004.

[47] C Ding.Complex codebooks from combinatorial designs[J].IEEE Transactions on Information Theory,2006,52(9):4229-4235.

[48] C Ding,T Feng.A generic construction of complex codebooks meeting the Welch bound[J].IEEE Transactions on Information Theory,2007,53(12):4245-4250.

[49] P Xia,G B Giannakis.Design and analysis of transmit beamforming based on limited-rate feedback [A].Proceeding of IEEE VTC'04 [C].Los Angeles,CA:IEEE Press,2004.26-29.

[50] S Hong,H Park,et al.A new performance measure using k-set correlation for compressed sensing matrices[J].IEEE Signal Processing Letter,2012,19(3):143-146.

压缩感知中确定性测量矩阵构造算法综述

A Survey on Deterministic Measurement Matrix Construction Algorithms in Compressive Sensing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈胜垚, 席峰, 张素玲, 刘中. 正交压缩采样系统时域分析[J]. 电子学报, 2023, 51(3): 573-584.
[2]	吕明久, 马建朝, 韦旭, 陈文峰, 杨军, 马晓岩. 基于矩阵化原子范数的高频雷达距离-多普勒二维估计方法[J]. 电子学报, 2022, 50(5): 1150-1158.
[3]	苏林林, 陈亮, 陈菲菲, 周鑫, 焦振航, 刘钊良. 面向B5G/6G的GFDM信号高精度测距与定位研究[J]. 电子学报, 2022, 50(4): 849-859.
[4]	魏志超, 杨春玲. 时域注意力特征对齐的视频压缩感知重构网络[J]. 电子学报, 2022, 50(11): 2584-2592.
[5]	陈文俊, 杨春玲. 图像压缩感知的特征域优化及自注意力增强神经网络重构算法[J]. 电子学报, 2022, 50(11): 2629-2637.
[6]	左婷, 王法松, 张建康, 李睿. 室内可见光通信系统中基于压缩感知的空移键控信号检测方法[J]. 电子学报, 2022, 50(1): 36-44.
[7]	冯西安, 寇思玮, 谭伟杰, 毕杨. 水声信号处理中的稀疏表示理论及应用[J]. 电子学报, 2021, 49(9): 1840-1851.
[8]	裴翰奇, 杨春玲, 魏志超, 曹燕. 基于SPL迭代思想的图像压缩感知重构神经网络[J]. 电子学报, 2021, 49(6): 1195-1203.
[9]	禤韵怡, 杨春玲. 基于帧间组稀疏的两阶段递归增强视频压缩感知重构网络[J]. 电子学报, 2021, 49(3): 435-442.
[10]	李峰, 詹邦成, 辛蕾, 刘洋, 刘志佳, 肖化超. 基于新型联合感知矩阵的压缩学习目标识别技术[J]. 电子学报, 2021, 49(11): 2108-2116.
[11]	郑恩明, 陈新华, 周权斌, 李嶷, 杨鹤, 孟浩. 一种复域压缩感知目标方位估计方法[J]. 电子学报, 2021, 49(11): 2117-2123.
[12]	孙泽宇, 李传锋, 阎奔. 传感网中基于压缩感知的丢包匹配数据收集算法[J]. 电子学报, 2020, 48(4): 723-733.
[13]	陈兵兵, 曹欣远, 陈明生, 齐琦, 况晓静, 吴先良, 陈辉. 基于欠定方程的频谱峰值搜索算法及其在连续毫米波雷达系统中的应用[J]. 电子学报, 2020, 48(2): 369-374.
[14]	郑学炜, 杨春玲, 禤韵怡. CVS中基于视频运动特征的多假设-双稀疏重构算法[J]. 电子学报, 2020, 48(2): 249-257.
[15]	马彬, 王宏明, 谢显中. 基于二项分布改进的宽带压缩频谱检测方案[J]. 电子学报, 2020, 48(2): 243-248.