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

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

Abstract

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

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.

Figures/Tables 5

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

算法	计算消耗（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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 17

Related Articles 15

Metrics

Recommended 0

[1]	Guang YANG, Zhaoyang WU, Min NIE, Xiaohong YAN, Fan JIANG. Research on PAPR reduction algorithm based on CWGAN-SLM for multi-wavelet OFDM system [J]. Journal on Communications, 2023, 44(4): 99-110.
[2]	Yong LIAO, Zhirong CAI. Basis expansion model-based improved regularized orthogonal matching pursuit channel estimation for V2X fast time-varying SC-FDMA [J]. Journal on Communications, 2021, 42(4): 177-184.
[3]	Yanyan HUANG,Hua PENG. Carrier frequency offsets estimation for distributed MIMO system based on SOMP method [J]. Journal on Communications, 2018, 39(8): 133-139.
[4]	Yue-hai ZHOU,Xiu-ling CAO,Dong-sheng CHEN,Feng TONG. Jointing sparse recovery estimation algorithm of underwater acoustic channels with long time delay spread [J]. Journal on Communications, 2016, 37(2): 166-173.
[5]	Hua-wei HUANG,Chang-wen PENG,Yun-yun QU,Chun-hua LI. Security of the cryptosystems based on ergodic matrices [J]. Journal on Communications, 2015, 36(8): 61-67.
[6]	Hong-zhi MEN,Ming-lu JIN. Low-complexity optimal MPSK detection for spatial modulation [J]. Journal on Communications, 2015, 36(8): 118-124.
[7]	. Research on greedy reconstruction algorithms of compressed sensing based on variable metric method [J]. Journal on Communications, 2014, 35(12): 12-105.
[8]	Zuo-liang YIN,Xing-peng MAO,Qin-yu ZHANG,Nai-tong ZHANG. Fast recursive algorithm for implementation of MIMO ZF-SIC detection [J]. Journal on Communications, 2012, 33(7): 67-74.
[9]	Da-gang TIAN. Notes on channel capacity per unit cost [J]. Journal on Communications, 2011, 32(4): 32-38.
[10]	Shang-yuan GUAN,Wei-guo WU,Xiao-she DONG,De-pei QIAN. Research on formal description and verification of automated trust negotiation [J]. Journal on Communications, 2011, 32(2): 86-99.
[11]	Shu-bo REN,Jun-qi GUO,Hai-ge XIANG. Channel estimation algorithms for STBC-SCFDE systems [J]. Journal on Communications, 2009, 30(8): 84-88.
[12]	Hai-jun ZHAO,Meng-tian CUI,Ming-dong LI. Research of an cascaded neural net filter applied in echo-cancellation [J]. Journal on Communications, 2008, 29(8): 107-112.
[13]	Qian-lei LIU,Lv-xi YANG,Dao-feng XU. Reduced-complexity V-BLAST algorithm for MIMO signal detection [J]. Journal on Communications, 2007, 28(9): 40-45.
[14]	Hai-jun ZHAO,Meng-tian CUI,Ming-dong LI. Sort of data driven frequency-domain echo-cancellation algorithm [J]. Journal on Communications, 2006, 27(6): 134-140.
[15]	Yi-ming WANG,Hong-bo ZHU. Less complicated adaptive equalization for UWB channels [J]. Journal on Communications, 2005, 26(10): 13-18.