A Caltech Library Service

Compressed Sensing, Sparse Approximation, and Low-Rank Matrix Estimation


Plan, Yaniv (2011) Compressed Sensing, Sparse Approximation, and Low-Rank Matrix Estimation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/K8W9-RS71.


The importance of sparse signal structures has been recognized in a plethora of applications ranging from medical imaging to group disease testing to radar technology. It has been shown in practice that various signals of interest may be (approximately) sparsely modeled, and that sparse modeling is often beneficial, or even indispensable to signal recovery. Alongside an increase in applications, a rich theory of sparse and compressible signal recovery has recently been developed under the names compressed sensing (CS) and sparse approximation (SA). This revolutionary research has demonstrated that many signals can be recovered from severely undersampled measurements by taking advantage of their inherent low-dimensional structure. More recently, an offshoot of CS and SA has been a focus of research on other low-dimensional signal structures such as matrices of low rank. Low-rank matrix recovery (LRMR) is demonstrating a rapidly growing array of important applications such as quantum state tomography, triangulation from incomplete distance measurements, recommender systems (e.g., the Netflix problem), and system identification and control.

In this dissertation, we examine CS, SA, and LRMR from a theoretical perspective. We consider a variety of different measurement and signal models, both random and deterministic, and mainly ask two questions.

How many measurements are necessary? How large is the recovery error?

We give theoretical lower bounds for both of these questions, including oracle and minimax lower bounds for the error. However, the main emphasis of the thesis is to demonstrate the efficacy of convex optimization---in particular l1 and nuclear-norm minimization based programs---in CS, SA, and LRMR. We derive upper bounds for the number of measurements required and the error derived by convex optimization, which in many cases match the lower bounds up to constant or logarithmic factors. The majority of these results do not require the restricted isometry property (RIP), a ubiquitous condition in the literature.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Compressed sensing, sparse approximation, low-rank matrix estimation
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)
  • Tropp, Joel A.
  • Owhadi, Houman
  • Hassibi, Babak
Defense Date:1 February 2011
Record Number:CaltechTHESIS:02272011-233144146
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6259
Deposited By: Yaniv Plan
Deposited On:29 Mar 2011 16:30
Last Modified:09 Oct 2019 17:08

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page