基于边膨胀图的压缩感知理论

伍政华; 王强; 刘劼; 孙明健; 沈毅

doi:10.3724/SP.J.1004.2014.02824

基于边膨胀图的压缩感知理论

doi: 10.3724/SP.J.1004.2014.02824

伍政华¹,
王强^1, ,,
刘劼^1,2,
孙明健¹,
沈毅¹

1.
哈尔滨工业大学控制科学与工程系哈尔滨 150001, 中国;
2.
美国微软研究院雷德蒙德 98052, 美国

基金项目:

国家自然科学基金(61174016,61201307,61371045),中央高校基本科研业务费专项资金(HIT.NSRIF.2013132)资助

详细信息

作者简介:
伍政华哈尔滨工业大学控制科学与工程系博士研究生. 2011 年获得哈尔滨工业大学硕士学位. 主要研究方向为稀疏重建, 压缩感知和光声成像.E-mail: zhenghuahitchina@gmail.com

通讯作者:
王强哈尔滨工业大学控制科学与工程系教授. 2004 年获得哈尔滨工业大学博士学位. 主要研究方向为图像处理, 数据融合和无线传感器网络. 本文通信作者. E-mail: wangqiang@hit.edu.cn

计量
- 文章访问数: 1462
- HTML全文浏览量: 71
- PDF下载量: 1233
- 被引次数: 0
出版历程
- 收稿日期: 2013-11-12
- 修回日期: 2014-02-24
- 刊出日期: 2014-12-20

Compressive Sensing Theory Based on Edge Expander Graphs

1.
Department of Control Science and Engineering, Harbin Institute of Technology, Harbin 150001, China;
2.
Microsoft Research of USA, Redmond 98052, USA

Funds:

Supported by National Natural Science Foundation of China (61174016, 61201307, 61371045) and the Fundamental Research Funds for the Central Universities (HIT.NSRIF.2013132)

摘要

摘要: 膨胀图(Expander graphs, EG) 理论与压缩感知(Compressive sensing, CS)理论相结合是近几年发展起来的一个新方向, 其优点在于能设计出具有确定结构的0-1测量矩阵, 且可根据膨胀图的结构协同设计重建算法, 相当于在重建算法中引入了先验知识, 能更快更准确地重构出稀疏信号. 本文从非均匀采样的必要性和合理性分析出发, 在已有的膨胀图压缩感知理论基础上, 将膨胀图的定义拓展到左顶点度数不相等的边膨胀图, 并建立起边膨胀图邻接矩阵与有限等距性质 (Restricted isometry property, RIP)条件之间的联系, 又进一步给出了边膨胀图邻接矩阵的列相关系数的上限值. 同时根据边膨胀图的特性, 协同设计了两种压缩感知重建算法. 通过仿真实验对比边膨胀图代表的非均匀采样模式与现有膨胀图代表的均匀采样模式, 以及本文设计的算法与传统算法在重建稀疏信号上的性能, 实验结果验证了边膨胀图压缩感知理论的有效性.
- 压缩感知 /
- 边膨胀图 /
- 非均匀采样 /
- 邻接矩阵 /
- 稀疏重建
Abstract: It is a new research direction to explore expander graphs for compressive sensing (CS). Using expander graphs for compressive sensing has several advantages, such as incorporating 0-1 deterministic structure measurement matrices, and fast and accurate recovery of sparse signals by leveraging prior knowledge. In this paper, we extend the notion of expanders with irregular left vertices degrees for non-uniform sampling. Through analyzing the relationship between adjacent matrices in edge expander graph and restricted isometry property (RIP), we obtain the upper limit of the coherence of the adjacent matrices. Based on these results, we design two algorithms for non-uniform sampling and corresponding sparse signal recovery. We evaluate the algorithms with numerical experiments. Finally, the experimental results demonstrate that the proposed non-uniform sampling pattern together with the algorithms have better performances on recovering sparse signals with known support set, as compared to the previous approaches.
- Compressive sensing (CS) /
- edge expander graphs /
- non-uniform sampling /
- adjacent matrix /
- sparse recon-struction

HTML全文

参考文献(27)

[1]	Candés E J. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 2008, 346(9-10): 589-592
[2]	Donoho D L. Compressed sensing. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306
[3]	Fang Hong, Yang Hai-Rong. Greedy algorithms and compressed sensing. Acta Automatica Sinica, 2011, 37(12): 1413-1421(方红, 杨海蓉. 贪婪算法与压缩感知理论. 自动化学报, 2011, 37(12): 1413-1421)
[4]	Li Shu-Tao, Wei Dan. A survey on compressive sensing. Acta Automatica Sinica, 2009, 35(11): 1369-1377(李树涛, 魏丹. 压缩传感综述. 自动化学报, 2009, 35(11): 1369- 1377)
[5]	Candés E J, Tao T. Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Transactions on Information Theory, 2006, 52(12): 5406- 5425
[6]	Song Xiao-Xia, Shi Guang-Ming. Fewer Bernoulli measurements satisfying the constraint of reconstruction probability. Acta Automatica Sinica, 2013, 39(1): 53-56(宋晓霞, 石光明. 满足重构概率约束的更少贝努利观测. 自动化学报, 2013, 39(1): 53-56)
[7]	Candés E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete fourier information. IEEE Transactions on Information Theory, 2006, 52(2): 489-509
[8]	Lian Qiu-Sheng, Chen Shu-Zhen. Image reconstruction for compressed sensing based on the combined sparse image representation. Acta Automatica Sinica, 2010, 36(3): 385-391(练秋生, 陈书贞. 基于混合基稀疏图像表示的压缩传感图像重构. 自动化学报, 2010, 36(3): 385-391)
[9]	Blanchard J, Tanner J. Gpu accelerated greedy algorithms for compressed sensing. Mathematical Programming Computation, 2013, 5(3): 267-304
[10]	Jafarpour S, Xu W, Hassibi B, Calderbank R. Efficient and robust compressed sensing using optimized expander graphs. IEEE Transactions on Information Theory, 2009, 55(9): 4299-4308
[11]	Xu W, Hassibi B. Efficient compressed sensing with deterministic guarantees using expander graphs. In: Proceedings of the 2007 IEEE Information Theory Workshop. Lake Tahoe, USA: IEEE, 2007. 414-419
[12]	Xu W, Hassibi B. Further results on performance analysis for compressive sensing using expander graphs. In: Proceedings of the 41st Asilomar Conference on Signals, Systems, and Computers. Pacific Grove, USA: IEEE, 2007. 621-625
[13]	Haupt J, Bajwa W, Rabbat M, Nowak R. Compressed sensing for networked data. IEEE Signal Processing Magazine, 2008, 25(2): 92-101
[14]	Liu Y, Zhu X Q, Zhang L, Cho S H. Expanding window compressed sensing for non-uniform compressible signals. Sensors, 2012, 12: 13034-13057
[15]	Jacques L, Hammond D, Fadili M. Dequantizing compressed sensing: when oversampling and non-Gaussian constraints combine. IEEE Transactions on Information Theory, 2011, 57(1): 559-571
[16]	Donoho D L, Elad M, Temlyakov V N. Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Transactions on Information Theory, 2006, 52(1): 6- 18
[17]	Candés E J, Romberg J. Sparsity and incoherence in compressive sampling. Inverse Problem, 2007, 23(3): 969-985
[18]	Guruswami V, Umans C, Vadhan S. Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity. San Diego, USA: IEEE, 2007. 96- 108
[19]	Sipser M, Spielman D A. Expander codes. IEEE Transactions on Information Theory, 1996, 42(6): 1710-1722
[20]	Sun M J, Feng N Z, Shen Y, Shen X L, Ma L Y, Li J G, Wu Z H. Photoacoustic imaging method based on arc-direction compressed sensing and multi-angle observation. Optics Express, 2011, 19(16): 14801-14806
[21]	Wang M, Xu W, Tang A. A unique "nonnegative" solution to an underdetermined system: from vectors to matrices. IEEE Transactions on Signal Processing, 2011, 59(3): 1007 -1016
[22]	Berinde R, Indyk P. Sequential sparse matching pursuit. In: Proceedings of the 47th Annual Allerton Conference on Communication, Control and Computing. Monticello, IL, USA: IEEE, 2009. 36-43
[23]	Tibshirani R. Regression shrinkage and selection via the Lasso. Journal Royal Statistical B, 1996, 58(1): 267-288
[24]	Tsaig Y, Donoho D L. Extensions of compressed sensing. Signal Processing, 2006, 86(3): 549-571
[25]	Chen S B, Donoho D L, Saunders M A. Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing, 1998, 20(1): 33-61
[26]	Tropp J, Gilbert A. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on Information Theory, 2007, 53(12): 4655-4666
[27]	Baraniuk R. Compressive sensing. IEEE Signal Processing Magazine, 2007, 24(4): 118-121

施引文献

资源附件(0)

访问统计

点击查看大图

计量

文章访问数: 1462
HTML全文浏览量: 71
PDF下载量: 1233
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

基于边膨胀图的压缩感知理论

doi: 10.3724/SP.J.1004.2014.02824

作者简介:
伍政华哈尔滨工业大学控制科学与工程系博士研究生. 2011 年获得哈尔滨工业大学硕士学位. 主要研究方向为稀疏重建, 压缩感知和光声成像.E-mail: zhenghuahitchina@gmail.com

通讯作者:
王强哈尔滨工业大学控制科学与工程系教授. 2004 年获得哈尔滨工业大学博士学位. 主要研究方向为图像处理, 数据融合和无线传感器网络. 本文通信作者. E-mail: wangqiang@hit.edu.cn

计量

Compressive Sensing Theory Based on Edge Expander Graphs

计量

目录

留言板

基于边膨胀图的压缩感知理论

doi: 10.3724/SP.J.1004.2014.02824

作者简介: 伍政华 哈尔滨工业大学控制科学与工程系博士研究生. 2011 年获得哈尔滨工业大学硕士学位. 主要研究方向为稀疏重建, 压缩感知和光声成像.E-mail: zhenghuahitchina@gmail.com

通讯作者: 王强 哈尔滨工业大学控制科学与工程系教授. 2004 年获得哈尔滨工业大学博士学位. 主要研究方向为图像处理, 数据融合和无线传感器网络. 本文通信作者. E-mail: wangqiang@hit.edu.cn

计量

出版历程

Compressive Sensing Theory Based on Edge Expander Graphs

计量

出版历程

目录

作者简介:
伍政华哈尔滨工业大学控制科学与工程系博士研究生. 2011 年获得哈尔滨工业大学硕士学位. 主要研究方向为稀疏重建, 压缩感知和光声成像.E-mail: zhenghuahitchina@gmail.com

通讯作者:
王强哈尔滨工业大学控制科学与工程系教授. 2004 年获得哈尔滨工业大学博士学位. 主要研究方向为图像处理, 数据融合和无线传感器网络. 本文通信作者. E-mail: wangqiang@hit.edu.cn