压缩感知中基于变尺度法的贪婪重构算法的研究

doi:10.3969/j.issn.1000-436x.2014.12.012

通信学报 ›› 2014, Vol. 35 ›› Issue (12): 98-105.doi: 10.3969/j.issn.1000-436x.2014.12.012

压缩感知中基于变尺度法的贪婪重构算法的研究

刘盼盼,李雷,王浩宇

南京邮电大学非结构化数据计算理论与应用研究中心，江苏南京 210046

出版日期:2014-12-25 发布日期:2017-06-17
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目

Research on greedy reconstruction algorithms of compressed sensing based on variable metric method

Pan-pan LIU,Lei LI,Hao-yu WNAG

Unstructured Data Calculation Theory and Application Research Center,Nanjing University of Posts and Telecommunications,Nanjing 210046,China

Online:2014-12-25 Published:2017-06-17
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China

摘要/Abstract

摘要：

首先将最优化方法中的梯度法与贪婪算法相结合，在已有梯度追踪算法的基础上提出了基于变尺度法的梯度追踪（VMMGP）算法，分析比较这些算法的计算复杂度和存储需求；其次用这些算法分别重构一维、二维信号，分析比较了算法重构效果及其性能好坏。实验结果表明，对于一维信号和二维信号的重构，所提出的VMMGP算法，重构效果是所有梯度追踪算法中最好的。

关键词: 正交匹配追踪, 梯度方向, 梯度追踪, 变尺度法, 计算复杂度, 存储需求

Abstract:

A variable metric method based gradient pursuit algorithm based on some existing gradient pursuit algorithms was proposed by combining the gradient direction of optimization methods with greedy algorithms.The computational complexity and storage requirements of these algorithms were also analysed and compared.In experimental part,all these algorithms were used to reconstruct one-dimensional audio signal and two-dimensional image signal.Experimental results show that the VMMGP algorithm has the best reconstruction performance among all the gradient pursuit algorithms.

Key words: orthogonal matching pursuit, gradient direction, gradient pursuit, variable metric method, computational complexity, storage requirements

刘盼盼,李雷,王浩宇. 压缩感知中基于变尺度法的贪婪重构算法的研究[J]. 通信学报, 2014, 35(12): 98-105.

Pan-pan LIU,Lei LI,Hao-yu WNAG. Research on greedy reconstruction algorithms of compressed sensing based on variable metric method[J]. Journal on Communications, 2014, 35(12): 98-105.

图/表 5

表1

图1

表2

表3

图2

参考文献 17

[1]	GOYAL V K , VETTERLI M , THAO N T . Quantized overcomplete expansions in Rn:Analysis,synthesis and algorithms[J]. IEEE Trans Inf Theory, 1984,44(1):16-31.
[2]	FEVOTTE C , GODSILL S . Sparse linear regression in unions of bases via Bayesian variable selection[J]. IEEE Signal Process Lett, 2006,13(7):441-444.
[3]	DAVIES M , MITIANOUDIS N . A simple mixture model for sparse overcomplete ICA[A]. Proc Inst Elect Eng,Vis,Image Signal Proc-essing[C]. 2004.35-43.
[4]	CANDèS E , ROMBERG J , TAO T . Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency infor-mation[J]. IEEE Trans Inf Theory, 2006,52(2):489-509.
[5]	CHEN S S , DONOHO D L , SAUNDERS M A . Atomic decomposition by basis pursuit[J]. SIAM J of Scientific Computing, 1998,20(1):33-61.
[6]	FIGUEIREDO M , NOWAK R , WRIGHT S . Gradient projection for sparse reconstruction:application to compressed sensing and other in-verse problems[J]. IEEE J of Slaected Topics in Signal Processing, 2007,12(4):586-597.
[7]	DAUBECHIES I , DEFRISE M , DEMOL C . An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[J]. Comm Pure Appl Math, 2004,57:1413-1457.
[8]	BLUMENSATH T , DAVIES M . Iterative hard thresholding for com-pressed sensing[J]. Appl Comput Harmon Anal, 2009,27(3):265-274.
[9]	MALLAT S , ZHANG Z . Matching pursuit in a time-frequency dic-tionary[J]. IEEE Trans SP, 1993,41(12):3397-3415.
[10]	TROPP J , GILBERT A . Signal recovery from partial information via orthogonal matching pursuit[J]. IEEE Trans Inform Theory, 2007,53(12):4655-4666.
[11]	DONOHO D L , DRORI I , TSAIG Y . Sparse solution of underdeter-mined linear equations by stagewise orthogonal matching pursuit[J]. IEEE Trans Inf Theory, 2012,58(2):1094-112.
[12]	NEEDELL D , VERSHYNIN R . Signal recovery from inaccurate and incomplete measurements via regularized orthogonal matching pur-suit[J]. Found Comput Math, 2009,9(3):317-334.
[13]	NEEDELL D , TROPP J A . CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J]. Appl Comp Harm Anal, 2009,26:309-321.
[14]	DAI W , MILENKOVIC O . Subspace pursuit for compressive sensing signal reconstruction[J]. IEEE Trans Inform Theory, 2009,55(5):2230-2249.
[15]	BLUMENSATH T , DAVIES M . Gradient pursuits[J]. IEEE Trans Signal Processing, 2008,56(6):2370-2382.
[16]	ZHU L , QIU C T . Newton pursuit algorithm for sparse signal recon-struction in compressed sensing[J]. IEEE Computer Science and In-formation Technology, 2010,6:463-466.
[17]	YUAN Y X , SUN W Y . Theory and Methods of Optimization[M]. Beijing: Science Press, 1997.

算法	计算消耗（flops）	存储需求（浮点数）
QR OMP	2Mn+3M+[Φ+N]	Mn+ 0.5n(n+1)+[Φ+M+2n+N]
GP	Φ+n+ 3M+[Φ+N]	M+ [Φ+M+2n+N]
CGP	2Mn+3M+[Φ+N]	Mn+ 0.5n(n+1)+[Φ+M+2n+N]
ACGP	2Φ+2n+4M+[Φ+N]	M+ [Φ+M+2n+N]
NP	Φ+2n+3M+[Φ+N]	M+ [Φ+M+2n+N]
VMMGP	Φ+ 3n+3M+[Φ+N]	M+n ²+[Φ+M+2n+N]

算法	时间/s	均方误差	信噪比/dB
OMP	0.151 5	10.814 8	37.824 6
QR OMP	0.081 3	10.016 1	38.395 8
GP	0.030 0	5.971 4	40.404 0
CGP	0.081 0	10.279 6	38.067 2
ACGP	0.057 9	5.711 6	40.597 2
NP	0.036 8	6.510 2	40.028 9
VMMGP	0.040 1	5.389 5	40.849 3

算法	时间/s	均方误差	峰值信噪比/dB
OMP	5.149 7	9.015 4×10⁶	26.745 7
QROMP	4.8675	8.443 5×10⁶	27.024 9
GP	4.291 8	8.715 2×10⁶	26.892 8
CGP	4.867 1	8.981 3×10⁷	26.808 8
ACGP	4.537 6	8.499 2×10⁶	27.001 8
NP	4.518 0	8.459 7×10⁶	27.022 1
VMMGP	4.5286	8.433 9×10⁶	27.035 3

压缩感知中基于变尺度法的贪婪重构算法的研究

Research on greedy reconstruction algorithms of compressed sensing based on variable metric method

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 17

相关文章 14

Metrics

推荐阅读 0

[1]	杨光, 吴朝阳, 聂敏, 闫晓红, 江帆. 基于CWGAN-SLM的多小波OFDM系统峰均比抑制算法研究[J]. 通信学报, 2023, 44(4): 99-110.
[2]	廖勇, 蔡志镕. 基于基扩展模型的改进正则化正交匹配追踪V2X快时变SC-FDMA信道估计[J]. 通信学报, 2021, 42(4): 177-184.
[3]	黄艳艳,彭华. 基于SOMP方法的分布式MIMO系统载波频偏估计[J]. 通信学报, 2018, 39(8): 133-139.
[4]	周跃海,曹秀岭,陈东升,童峰. 长时延扩展水声信道的联合稀疏恢复估计[J]. 通信学报, 2016, 37(2): 166-173.
[5]	黄华伟,彭长文,瞿云云,李春华. 遍历矩阵密码体制的安全性[J]. 通信学报, 2015, 36(8): 61-67.
[6]	门宏志,金明录. 低复杂度空间调制MPSK信号的最优检测[J]. 通信学报, 2015, 36(8): 118-124.
[7]	刘盼盼，李雷，王浩宇. 压缩感知中基于变尺度法的贪婪重构算法的研究[J]. 通信学报, 2014, 35(12): 12-105.
[8]	殷作亮,毛兴鹏,张钦宇,张乃通. 实现MIMO系统串行干扰消除迫零检测的快速递归算法[J]. 通信学报, 2012, 33(7): 67-74.
[9]	綦科,张大方,谢冬青. 基于颜色梯度特性的彩色图像隐写分析[J]. 通信学报, 2011, 32(1): 27-36.
[10]	任术波,郭俊奇,项海格. 基于STBC-SCFDE系统的信道估计算法研究[J]. 通信学报, 2009, 30(8): 84-88.
[11]	韦永壮,胡予濮. 42轮SHACAL-2新的相关密钥矩形攻击[J]. 通信学报, 2009, 30(1): 7-11.
[12]	赵海军,崔梦天,李明东. 回波抵消中级联神经网络滤波器的研究[J]. 通信学报, 2008, 29(8): 107-112.
[13]	阳少平,胡予濮,钟名富. 相关密钥不可能差分31轮SHACAL-2攻击[J]. 通信学报, 2007, 28(11A): 54-58.
[14]	赵海军,崔梦天,李明东. 数据驱动的频域回波抵消算法[J]. 通信学报, 2006, 27(6): 134-140.