Computer Science ›› 2015, Vol. 42 ›› Issue (11): 279-283.doi: 10.11896/j.issn.1002-137X.2015.11.057

Previous Articles     Next Articles

Reconstruction Algorithm in Compressed Sensing Based on Maximum Posteriori Estimation

ZHUANG Yan-bin, WANG Zun-zhi, XIAO Xian-jian and ZHANG Xue-wu   

  • Online:2018-11-14 Published:2018-11-14

Abstract: This paper proposed a systematic method for constructing a sparse data reconstruction algorithm in compressed sensing which owns a relatively low computational cost for general observation matrix.It is known that the cost of 1-norm minimization using a standard linear programming algorithm is O(N3).The cost of proposed method can be reduced to O(N2) by applying the approach of posterior maximization.By introducing the division ratio,the algorithm achieves better convergence.Furthermore,in principle,the algorithm from our approach is expected to achieve the widest successful reconstruction region,which is evaluated from theoretical argument.

Key words: Compressed sensing,Cost,Posterior maximization,Reconstruction region

[1] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306
[2] Candes E J,Tao T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2005,51(12):4203-4215
[3] Candes E J,Romberg J,Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):489-509
[4] Candes E J,Wakin M B.An introduction to compressive sampling[J].Signal Processing Magazine,IEEE,2008,25(2):21-30
[5] Elad M,Figueiredo M A T,Ma Yi.On the role of sparse and redundant representations in image processing[J].Proceedings of the IEEE,2010,98(6):972-982
[6] Tropp J A,Wright S J.Computational methods for sparse solution of linear inverse problems[J].Proceedings of the IEEE,2010,98(6):948-958
[7] Donoho D L,Maleki A,Montanari A.Message passing algo-rithms for compressed sensing:i.motivation and construction[C]∥Information Theory Workshop (ITW).2010 IEEE,2010:1-5
[8] Kj S,Andersen R.Probabilistic reasoning in intelligent systems:networks of plausible inference judea pearl[J].Artificial Intelligence,1991,4(1):117-124
[9] 赵玉娟,郑宝玉,陈守宁.压缩感知自适应观测矩阵设计[J].信号处理,2012,28(12):1635-1641 Zhao Yu-juan,Zheng Bao-yu,Chen Shou-ning.The design of adaptive measurement matrix in compressed sensing[J].Signal Processing,2012,28(12):1635-1641
[10] Recht B,Xu Wei-yu,Hassibi B.Null space conditions and thres-holds for rank minimization[J].Mathematical Programming,2011,127(1):175-202
[11] 冯祖仁,吕娜,李良福.基于最大后验概率的图像匹配相似性指标研究[J].自动化学报,2007,3(1):1-8 Feng Zhu-ren,Lv Na,Li Liang-fu.Research on Image Matching Similarity Criterion Based on Maximun Posterior Probability[J].Acta Automation Sinica,2007,3(1):1-8
[12] Tibshirani R.regression shrinkage and selection via the lasso[J].Journal of the Royal Statistical Society,series b:methodological,1996,58(1):267-288
[13] Bayati M,Montanari A.The dynamics of message passing ondense graphs,with applications to compressed sensing[J].IEEE Transactions on Information Theory,2011,57(2):764-785
[14] Krzakala F,Mézard M,Sausset F.Probabilistic reconstruction in compressed sensing:algorithms,phase diagrams,and threshold achieving matrices[J].Journal of Statistical Mechanics:Theory and Experiment,2012(4):P08009
[15] 李书波,张渡淮.heaviside函数的非标准分析表示[J].哈尔滨科学技术大学学报,1987,45(4):760-782 Li Shu-bo,Zhang Du-huai.Non-standard analysis representation of heaviside function[J].Journal of Harbin University of Science and Technology,1987,45(4):760-782
[16] 李慧玲,张春阳,李卓识,等.解非凸优化问题的一个同伦内点方法[J].东北师大学报(自然科学版),2009,41(4):764-785 Li Hui-ling,Zhang Chun-yang,Li Zuo-shi,et al.Homotopy interior point method for non-convex optimization problem with weak pseudo cone condition[J].Journal of Northeast Normal University(Natural Science Edition),2009,41(4):764-785
[17] Gupta S.A note on the asymptotic distribution of lasso estimator for correlated data[J].Sankhya A,2012,74(1):10-28
[18] Kutyniok G.Theory and applications of compressed sensing[J].Gamm-mitteilungen,2013,36(1):79-101
[19] Gallavotti G.Chaotic hypothesis:onsager reciprocity and fluctuation-dissipation theorem[J].Journal of Statistical Physics,1996,84(5/6):899-925
[20] 王定成,苏淳.b值独立同分布随机变元序列的矩完全收敛性[J].应用数学学报,2004,7(3):440-448 Wang Ding-cheng,Sun Chun.Moment Complete Convergence for Sums of i.i.d.Random Elements in Banach Space[J].Acta Mathematicae Applicatae Sinica,2004,7(3):440-448

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!