Paper Info
Title
Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
Abstract
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.
Year
DOI
Venue
2012
10.1088/1742-5468/2012/08/P08009
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT
Keywords
Field
DocType
cavity and replica method,message-passing algorithms,error correcting codes,statistical inference
Signal processing,Expectation–maximization algorithm,Matrix (mathematics),Algorithm,Robustness (computer science),Synthetic data,Probabilistic logic,Compressed sensing,Message passing,Mathematics
Journal
Volume
Issue
ISSN
abs/1206.3953
8
1742-5468
Citations 
PageRank 
References 
94
3.60
27
Authors
5
Name
Order
Citations
PageRank
Florent Krzakala197767.30
Marc Mézard259039.09
François Sausset31897.63
Yifan Sun422911.34
Lenka Zdeborová5119078.62