Probabilistic reconstruction in compressed sensing: algorithms, phase diagrams, and threshold achieving matrices

被引:176
作者
Krzakala, Florent [1 ,2 ]
Mezard, Marc [3 ,4 ]
Sausset, Francois [3 ,4 ]
Sun, Yifan [1 ,2 ,5 ,6 ]
Zdeborova, Lenka [7 ,8 ]
机构
[1] CNRS, F-75005 Paris, France
[2] ESPCI ParisTech, UMR Gulliver 7083, F-75005 Paris, France
[3] Univ Paris 11, F-91405 Orsay, France
[4] CNRS, UMR8626, LPTMS, F-91405 Orsay, France
[5] Beihang Univ, LMIB, Beijing 100191, Peoples R China
[6] Beihang Univ, Sch Math & Syst Sci, Beijing 100191, Peoples R China
[7] CEA Saclay, IPhT, Inst Phys Theor, F-91191 Gif Sur Yvette, France
[8] CENS, Lab Leon Brillouin, CNRS, URA 2306, F-91191 Gif Sur Yvette, France
来源
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2012年
关键词
cavity and replica method; message-passing algorithms; error correcting codes; statistical inference;
D O I
10.1088/1742-5468/2012/08/P08009
中图分类号
O3 [力学];
学科分类号
08 ; 0801 ;
摘要
Compressed sensing is a signal processing method that acquires data directly in a compressed form. This allows one to make fewer measurements than were considered necessary to record a signal, enabling faster or more precise measurement protocols in a wide range of applications. Using an interdisciplinary approach, we have recently proposed in Krzakala et al (2012 Phys. Rev. X 2 021005) a strategy that allows compressed sensing to be performed at acquisition rates approaching the theoretical optimal limits. In this paper, we give a more thorough presentation of our approach, and introduce many new results. We present the probabilistic approach to reconstruction and discuss its optimality and robustness. We detail the derivation of the message passing algorithm for reconstruction and expectation maximization learning of signal-model parameters. We further develop the asymptotic analysis of the corresponding phase diagrams with and without measurement noise, for different distributions of signals, and discuss the best possible reconstruction performances regardless of the algorithm. We also present new efficient seeding matrices, test them on synthetic data and analyze their performance asymptotically.
引用
收藏
页数:57
相关论文
共 55 条
[1]  
[Anonymous], 2001, Statistical Physics of Spin Glasses and Information Processes
[2]  
[Anonymous], P AS C SIGN SYST COM
[3]  
[Anonymous], ARXIV11116822V1CSIT
[4]  
[Anonymous], 2010, 2010 44th Annual Conference on Information Sciences and Systems (CISS)
[5]  
[Anonymous], ARXIV12022525V1CSIT
[6]  
[Anonymous], ARXIV12077321
[7]  
[Anonymous], 2003, Exploring artificial intelligence in the new millennium, DOI DOI 10.5555/779343.779352
[8]  
[Anonymous], 1982, P AAAI NATINAL C AI
[9]  
[Anonymous], ARXIV09063234V2
[10]  
[Anonymous], 2008, P 25 INT C MACH LEAR