Author : Mohammad Ali Maleki
Publisher : Stanford University
Page : 311 pages
File Size : 53,6 Mb
Release : 2010
Category : Electronic
ISBN : STANFORD:rd797hn1131
Approximate Message Passing Algorithms for Compressed Sensing by Mohammad Ali Maleki Pdf
Compressed sensing refers to a growing body of techniques that `undersample' high-dimensional signals and yet recover them accurately. Such techniques make fewer measurements than traditional sampling theory demands: rather than sampling proportional to frequency bandwidth, they make only as many measurements as the underlying `information content' of those signals. However, as compared with traditional sampling theory, which can recover signals by applying simple linear reconstruction formulas, the task of signal recovery from reduced measurements requires nonlinear, and so far, relatively expensive reconstruction schemes. One popular class of reconstruction schemes uses linear programming (LP) methods; there is an elegant theory for such schemes promising large improvements over ordinary sampling rules in recovering sparse signals. However, solving the required LPs is substantially more expensive in applications than the linear reconstruction schemes that are now standard. In certain imaging problems, the signal to be acquired may be an image with $10^6$ pixels and the required LP would involve tens of thousands of constraints and millions of variables. Despite advances in the speed of LP, such methods are still dramatically more expensive to solve than we would like. In this thesis we focus on a class of low computational complexity algorithms known as iterative thresholding. We study them both theoretically and empirically. We will also introduce a new class of algorithms called approximate message passing or AMP. These schemes have several advantages over the classical thresholding approaches. First, they take advantage of the statistical properties of the problem to improve the convergence rate and predictability of the algorithm. Second, the nice properties of these algorithms enable us to make very accurate theoretical predictions on the asymptotic performance of LPs as well. It will be shown that more traditional techniques such as coherence and restricted isometry property are not able to make such precise predictions.
