Approximate message passing algorithms for compressed sensing
Abstract/Contents
- Abstract
- 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.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Copyright date | 2011 |
| Publication date | 2010, c2011; 2010 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Maleki, Mohammad Ali |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering |
| Primary advisor | Donoho, David Leigh |
| Thesis advisor | Donoho, David Leigh |
| Thesis advisor | Gray, Robert M, 1943 |
| Thesis advisor | Montanari, Andrea |
| Advisor | Gray, Robert M, 1943 |
| Advisor | Montanari, Andrea |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Arian Maleki. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Mohammad Ali Maleki
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...