Séminaire de Probabilités commun ICJ/UMPA

Statistical physics approach to compressed sensing and generalized linear regression

by Lenka Zdeborova

salle 435 (UMPA)

salle 435


Bayesian inference and statistical physics are formally closely related. Therefore methodology and concepts developed in statistical physics to understand disordered materials such as glasses and spin glasses can be elevated to analyze models of statistical inference. We will present this approach in a rather general setting that covers analysis of compressed sensing, generalized linear regression, and the perceptron - a kind of a single layer neural network. At the one hand, this approach leads to the approximate message passing algorithm that is gaining its place among other widely used regression and classification algorithms. At the other hand, the related analyses leads to identification of phase transitions in the performance of Bayes-optimal estimators. We will discuss relation between these phase transitions and algorithmic hardness, and in the case of compressed sensing we will show how this understanding leads to a design of optimal measurement protocols. Based partly on "Statistical-physics-based reconstruction in compressed sensing" PRX 2012 and reviewed in "Statistical physics of inference: Thresholds and algorithms" Advances of Physics 2016.
From the same series
1 2 4 5 6 7 8 9 10 11 12 13