一种基于CGLS和LSQR的联合优化的匹配追踪算法

陈善雄; 熊海灵; 廖剑伟; 周骏; 左俊森

doi:10.16383/j.aas.2018.c160569

一种基于CGLS和LSQR的联合优化的匹配追踪算法

doi: 10.16383/j.aas.2018.c160569

陈善雄^1, ,,
熊海灵^1,,
廖剑伟^1,,
周骏^1,,
左俊森^1,

1.
西南大学计算机与信息科学学院重庆 400715

基金项目:

重庆市博士后科研项目 Xm2016041

国家自然科学基金 61303227

中国博士后基金 2015M580765

详细信息

作者简介:
熊海灵  西南大学计算机与信息科学学院教授.2007年获得西南大学数字农业方向农学博士学位.主要研究方向为数据库与智能信息处理, 计算机模拟及其应用.E-mail:xionghl@swu.edu.cn

廖剑伟  西南大学计算机与信息科学学院副教授.2012年获日本东京大学计算机科学博士学位.主要研究方向为系统软件和高性能分布式存储.E-mail:liaotoad@gmail.com

周骏  西南大学计算机与信息科学学院副教授.2013年获得电子科技大学计算机应用技术博士学位, 2014~2015年在罗切斯特大学(University ofRochester)做博士后研究.主要研究方向为图像处理, 计算机视觉, 分子影像.E-mail:zhouj@swu.edu.cn

左俊森  西南大学计算机与信息科学学院硕士研究生.主要研究方向为数据库与智能检索技术, 计算机模拟及其应用.E-mail:zuojunsen@email.swu.edu.cn

通讯作者:
陈善雄西南大学计算机与信息科学学院副教授.2013年获得重庆大学计算机科学与技术博士学位.主要研究方向为数据挖掘, 模式识别, 压缩感知.本文通信作者.E-mail:csxpml@163.com

计量
- 文章访问数: 2660
- HTML全文浏览量: 445
- PDF下载量: 696
- 被引次数: 0
出版历程
- 收稿日期: 2016-08-16
- 录用日期: 2017-05-06
- 刊出日期: 2018-07-20

A Matching Pursuit Algorithm of Jointing Optimization Based on CGLS and LSQR

1.
College of Computer and Information Science, Southwest University, Chongqing 400715

Funds:

Chongqing Postdoctoral Science Foundation Xm2016041

National Natural Science Foundation of China 61303227

China Postdoctoral Science Foundation 2015M580765

More Information

Author Bio:
Professor at the College of Computer and Information Science, Southwest University. He received his Ph. D. degree in agronomy from Southwest University in 2007. His research interest covers database and intelligent information processing, computer simulation and application

Associate professor at the College of Computer and Information Science. He received his Ph. D. degree in computer science from Tokyo University in 2012. His research interest covers system software and high performance storage system

Associate professor at the College of Computer & Information Science, Southwest University. He received Ph.D. degree in computer science from the Electronic Science and Technology of China in 2013. He did one year postdoctor at University of Rochester, USA in August, from 2014 to 2015. His research interest covers image processing, computer vision, and molecular imaging

Master student at the College of Computer and Information Science, Southwest University. His research interest covers database and intelligent retrieval techniques, computer simulation and application

Corresponding author: CHEN Shan-Xiong Associate professor at the College of Computer and Information Science, Southwest University. He received his Ph. D. degree in computer science from Chongqing University in 2013. His research interest covers data mining, pattern recognition, compressed sensing. Corresponding author of this paper

摘要

摘要: 在压缩感知理论中，设计好的稀疏重构算法是一个比较重要，同时也是一个具有挑战性的问题.稀疏重构的基本目标是用较少的数据样本，通过解一个优化问题完成信号或者图像重构.关于稀疏重构过程，一个重要的研究方向是在数据受噪声干扰的情况下，如何高效快速地重建原信号.本文提出了基于共轭梯度最小二乘法（Conjugate gradient least squares，CGLS）和最小二乘QR分解（Least squares QR，LSQR）的联合优化的匹配追踪算法.该算法采用Alpha散度来测量CGLS和LSQR之间的离散度（差异度），并通过离散度来选择最优的解序列.实验分析表明基于CGLS和LSQR的联合优化的匹配追踪算法在压缩采样的信号受噪声干扰情况下具有较好的恢复能力.
- 压缩感知 /
- 匹配追踪 /
- 稀疏恢复 /
- 噪声
Abstract: For compressed sensing theory, to design a good sparse reconstruction algorithm is a challenge. The basic purpose of sparse reconstruction is to implement the signal or image reconstruction by solving optimization problem on the condition of fewer data samples. For the sparse reconstruction, an important aspect is how to reconstruct original signal when data is contaminated by noise. In this article, we present a matching pursuit algorithm, in which the conjugate gradient least squares (CGLS) method combines the least squares QR (LSQR) method to solve the optimization. This algorithm uses alpha divergence to measure dispersion between CGLS and LSQR, then selects optimization solution sequence in light of the dispersion. Experiment shows that the matching pursuit algorithm has excellent reconstruction performance when the signal of compressed sampling is contaminated.
- Compressed sensing /
- matching pursuit /
- sparse reconstruction /
- noise
注释:

1) 本文责任编委孙富春

HTML全文

图 1 OMP、StOMP、CoSaOMP、ROMP和COCLMP在噪声干扰下对稀疏信号的重构效果

Fig. 1 Reconstruction effect of sparse signals include noise for OMP, StOMP, CoSaOMP, ROMP, COCLMP

下载: 全尺寸图片幻灯片

图 2 噪声干扰的不同采样次数下OMP、StOMP、CoSaOMP、ROMP、COCLMP算法重构结果

Fig. 2 Reconstruction result include noise under different sampling number for OMP, StOMP, CoSaOMP, ROMP, COCLMP

下载: 全尺寸图片幻灯片

图 3 噪声干扰下OMP、StOMP、CoSaOMP、ROMP、COCLMP算法对图像的重构效果

Fig. 3 Image reconstruction effect include noise for OMP, StOMP, CoSaOMP, ROMP, COCLMP

下载: 全尺寸图片幻灯片

图 4 噪声下重构Lena、aerial、man、boat图的PSNR

Fig. 4 The PSNR of reconstructing Lena, aerial, man, boat include noise

下载: 全尺寸图片幻灯片

参考文献(19)

[1]	Moshtaghpour A, Jacques L, Cambareri V, Degraux K, De Vleeschouwer C. Consistent basis pursuit for signal and matrix estimates in quantized compressed sensing. IEEE Signal Processing Letters, 2016, 23(1):25-29 doi: 10.1109/LSP.2015.2497543
[2]	Zhao W Q, Beach T H, Rezgui Y. Efficient least angle regression for identification of linear-in-the-parameters models. Proceedings of the Royal Society A:Mathematical, Physical and Engineering Sciences, 2017, 473(2198):Article No.20160775 doi: 10.1098/rspa.2016.0775
[3]	Lee H C, Song B, Kim J S, Jung J J, Li H H, Mutic S, et al. An efficient iterative CBCT reconstruction approach using gradient projection sparse reconstruction algorithm. Oncotarget, 2016, 7(52):87342-87350 http://europepmc.org/abstract/MED/27894103
[4]	许志强.压缩感知.中国科学:数学, 2012, 42(9):865-877 https://www.wenkuxiazai.com/doc/3851fb1eff00bed5b9f31d8b.html Xu Zhi-Qiang. Compressed sensing:a survey. Science China:Mathematics, 2012, 42(9):865-877 https://www.wenkuxiazai.com/doc/3851fb1eff00bed5b9f31d8b.html
[5]	方红, 杨海蓉.贪婪算法与压缩感知理论.自动化学报, 2011, 37(12):1413-1421 http://www.aas.net.cn/CN/abstract/abstract17639.shtml Fang Hong, Yang Hai-Rong. Greedy algorithms and compressed sensing. Acta Automatica Sinica, 2011, 37(12):1413-1421 http://www.aas.net.cn/CN/abstract/abstract17639.shtml
[6]	Cohen A, Dahmen W, DeVore R. Orthogonal matching pursuit under the restricted isometry property. Constructive Approximation, 2017, 45(1):113-127 doi: 10.1007/s00365-016-9338-2
[7]	Do T T, Gan L, Nguyen N, Tran T D. Sparsity adaptive matching pursuit algorithm for practical compressed sensing. In: Proceedings of the 42th Asilomar Conference on Signals, Systems and Computers. Pacific Grove, CA, USA: IEEE, 2008. 581-587
[8]	Needell D, Vershynin R. Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit. IEEE Journal of Selected Topics in Signal Processing, 2010, 4(2):310-316 doi: 10.1109/JSTSP.2010.2042412
[9]	Lee D. MIMO OFDM channel estimation via block stagewise orthogonal matching pursuit. IEEE Communications Letters, 2016, 20(10):2115-2118 doi: 10.1109/LCOMM.2016.2594059
[10]	Davenport M A, Needell D, Wakin M B. Signal space CoSaMP for sparse recovery with redundant dictionaries. IEEE Transactions on Information Theory, 2013, 59(10):6820-6829 doi: 10.1109/TIT.2013.2273491
[11]	Giryes R, Elad M. RIP-based near-oracle performance guarantees for SP, CoSaMP, and IHT. IEEE Transactions on Signal Processing, 2012, 60(3):1465-1468 doi: 10.1109/TSP.2011.2174985
[12]	Ramirez-Giraldo J C, Trzasko J, Leng S, Yu L, Manduca A, McCollough C H. Nonconvex prior image constrained compressed sensing (NCPICCS):theory and simulations on perfusion CT. Medical Physics, 2011, 38(4):2157-2167 doi: 10.1118/1.3560878
[13]	Babaie-Kafaki S, Ghanbari R. A hybridization of the Hestenes-Stiefel and Dai-Yuan conjugate gradient methods based on a least-squares approach. Optimization Methods and Software, 2015, 30(4):673-681 doi: 10.1080/10556788.2014.966825
[14]	Shaw C B, Prakash J, Pramanik M, Yalavarthy P K. Least squares QR-based decomposition provides an efficient way of computing optimal regularization parameter in photoacoustic tomography. Journal of Biomedical Optics, 2013, 18(8):Article No.80501 doi: 10.1117/1.JBO.18.8.080501
[15]	Paige C C, S M A. LSQR:an algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software, 1982, 8(1):43-71 doi: 10.1145/355984.355989
[16]	Cichocki A, Zdunek R, Amari S I. Csiszár's divergences for non-negative matrix factorization: family of new algorithms. In: Proceedings of the 2006 International Conference on Independent Component Analysis and Blind Signal Separation. Charleston, SC, USA: Springer, 2006. 32-39
[17]	Cichocki A, Amari S I. Families of Alpha-Beta-and Gamma-divergences:flexible and robust measures of similarities. Entropy, 2010, 12(6):1532-1568 doi: 10.3390/e12061532
[18]	余南南, 邱天爽.压缩传感条件下红外和可见光图像融合技术的研究.信号处理, 2012, 28(5):692-698 http://cdmd.cnki.com.cn/Article/CDMD-10183-2008126444.htm Yu Nan-Nan, Qiu Tian-Shuang. Fusion technology of infrared and visible images in compressive sensing. Signal Processing, 2012, 28(5):692-698 http://cdmd.cnki.com.cn/Article/CDMD-10183-2008126444.htm
[19]	王琴, 沈远彤.基于压缩感知的多尺度最小二乘支持向量机.自动化学报, 2016, 42(4):631-640 http://www.aas.net.cn/CN/abstract/abstract18849.shtml Wang Qin, Shen Yuan-Tong. Multi-scale least squares support vector machine using compressive sensing. Acta Automatica Sinica, 2016, 42(4):631-640 http://www.aas.net.cn/CN/abstract/abstract18849.shtml