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

By Florent Krzakala, M. M'ezard, François Sausset, Yifan Sun, Lenka Zdeborov'a. arXiv.org, 2012

298 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Radiation, Radiology, Nuclear Medicine and Imaging

View Paper: https://www.semanticscholar.org/paper/5b90e8cd40146269a721e87f77f7adaf8b7d3e69

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Radiation

In Radiology, Nuclear Medicine and Imaging

Citations in the corpus

Statistical physics of inference: thresholds and algorithms (2015, methodology): “[134] further studied how is the inference performance influenced by measurement noise, mismatch between the prior and the actual signal distribution, how the performance changes under expectation maximization learning of the parameters, such as ρ or mean x and variance σ of the signal distribution.”
An equivalence between high dimensional Bayes optimal inference and M-estimation (2016, methodology): “ot yet been rigorously proven, but the associated SE is believed to be exact in the dense iid Gaussian measurement setting based on replica arguments from statistical physics (see e.g. section 4.3 in [16] for further discussion). For this reason, similar arguments have been used to determine theoret”
Compressive phase retrieval via generalized approximate message passing (2012, methodology): “can be computed in closed form [40] after which the resulting expression (63) simplifies.”
Optimal errors and phase transitions in high-dimensional generalized linear models (2017, methodology): “In this case, three di erent phases are present [68, 80]: i) For α < ρ, perfect reconstruction is impossible; ii) for ρ < α < αs reconstruction is possible, but not with any known polynomialcomplexity algorithm; iii) for α > αs, the so-called spinodal transition computed with state evolution, GAMP p”
Understanding overfitting peaks in generalization error: Analytical risk curves for l2 and l1 penalized interpolation (2019, background): “Many approaches can be brought to bear on this problem, including the replica and cavity approaches from statistical physics[13, 14, 9, 15] and the message-passing/belief propagation approaches[7, 5, 20].”
Generalized approximate message passing for estimation with random linear mixing (2010, methodology): “Specifically, we present a generalization of the SE equations to arbitrary output channels recovering several earlier results on AWGN channels as special instances.”
The committee machine: computational to statistical gaps in learning a two-layers neural network (2018, methodology): “This could be done for instance with a combination of EM and AMP along the lines of [43, 44] where this is done for the simpler single layer case.”