CaltechTHESIS
  A Caltech Library Service

Practical compressed sensing : modern data acquisition and signal processing

Citation

Becker, Stephen R. (2011) Practical compressed sensing : modern data acquisition and signal processing. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:06022011-152525054

Abstract

Since 2004, the field of compressed sensing has grown quickly and seen tremendous interest because it provides a theoretically sound and computationally tractable method to stably recover signals by sampling at the information rate. This thesis presents in detail the design of one of the world's first compressed sensing hardware devices, the random modulation pre-integrator (RMPI). The RMPI is an analog-to-digital converter (ADC) that bypasses a current limitation in ADC technology and achieves an unprecedented 8 effective number of bits over a bandwidth of 2.5 GHz. Subtle but important design considerations are discussed, and state-of-the-art reconstruction techniques are presented. Inspired by the need for a fast method to solve reconstruction problems for the RMPI, we develop two efficient large-scale optimization methods, NESTA and TFOCS, that are applicable to a wide range of other problems, such as image denoising and deblurring, MRI reconstruction, and matrix completion (including the famous Netflix problem). While many algorithms solve unconstrained $\ell_1$ problems, NESTA and TFOCS can solve the constrained form of $\ell_1$ inimization, and allow weighted norms. In addition to $\ell_1$ minimization problems such as the LASSO, both NESTA and TFOCS solve total-variation minimization problem. TFOCS also solves the Dantzig selector and most variants of the nuclear norm minimization problem. A common theme in both NESTA and TFOCS is the use of smoothing techniques, which make the problem tractable, and the use of optimal first-order methods that have an accelerated convergence rate yet have the same cost per iteration as gradient descent. The conic dual methodology is introduced in TFOCS and proves to be extremely flexible, covering such generic problems as linear programming, quadratic programming, and semi-definite programming. A novel continuation scheme is presented, and it is shown that the Dantzig selector benefits from an exact-penalty property. Both NESTA and TFOCS are released as software packages available freely for academic use.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:compressed sensing; RMPI; analog-to-information; AIC; A2I; TFOCS; NESTA; first-order algorithms; Nesterov acceleration; smoothing
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Candes, Emmanuel J.
Thesis Committee:
  • Candes, Emmanuel J. (chair)
  • Emami-Neyestanak, Azita
  • Tropp, Joel A.
  • Hassibi, Babak
  • Vandenberghe, Lieven
Defense Date:7 April 2011
Author Email:srbecker (AT) wesleyan.edu
Funders:
Funding AgencyGrant Number
DARPAFA8650-08-C-7853
Record Number:CaltechTHESIS:06022011-152525054
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:06022011-152525054
Related URLs:
URLURL TypeDescription
http://tfocs.stanford.eduOtherUNSPECIFIED
http://www.acm.caltech.edu/~nestaOtherUNSPECIFIED
http://arxiv.org/abs/1009.2065arXivUNSPECIFIED
http://arxiv.org/abs/0904.3367arXivUNSPECIFIED
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6492
Collection:CaltechTHESIS
Deposited By: Stephen Becker
Deposited On:03 Jun 2011 18:40
Last Modified:26 Dec 2012 04:37

Thesis Files

[img]
Preview
PDF (Main thesis) - Final Version
See Usage Policy.

8Mb
[img]
Preview
PDF (Front-matter) - Final Version
See Usage Policy.

256Kb
[img]
Preview
PDF (Chapter 1: Introduction) - Final Version
See Usage Policy.

890Kb
[img]
Preview
PDF (Chapter 2: RMPI) - Final Version
See Usage Policy.

5Mb
[img]
Preview
PDF (Chapter 3: NESTA) - Final Version
See Usage Policy.

1075Kb
[img]
Preview
PDF (Chapter 4: TFOCS) - Final Version
See Usage Policy.

2156Kb
[img]
Preview
PDF (Chapter 5: Conclusion) - Final Version
See Usage Policy.

142Kb
[img]
Preview
PDF (Bibliography) - Final Version
See Usage Policy.

262Kb

Repository Staff Only: item control page