Appears in collection : Nexus Trimester - 2016 - Inference Problems Theme

Large compressed sensing problems can exhibit phase transitions in which a small change in the number of measurements leads to a large change in the mean-squared error. Over the past decade, these phase transitions have been studied using an amazingly diverse set of ideas from information theory, statistical physics, high-dimensional geometry, and statistical decision theory. The goal of this talk is to use an information theoretic framework to explain the connections between three very different methods of analysis. The first uses the heuristic replica method from statistical physics to characterize the fundamental limits. The second uses the analysis of approximate loopy belief propagation to characterize the asymptotic performance of practical algorithms, and the third uses Gaussian process theory and concentration of measure to provide sharp non-asymptotic bounds for optimization-based algorithms.