A Caltech Library Service

Combinatorial Regression and Improved Basis Pursuit for Sparse Estimation


Khajehnejad, M. Amin (2012) Combinatorial Regression and Improved Basis Pursuit for Sparse Estimation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/04J6-Y832.


Sparse representations accurately model many real-world data sets. Some form of sparsity is conceivable in almost every practical application, from image and video processing, to spectral sensing in radar detection, to bio-computation and genomic signal processing. Modern statistics and estimation theory have come up with ways for efficiently accounting for sparsity in enhanced information retrieval systems. In particular, \emph{compressed sensing} and \emph{matrix rank minimization} are two newly born branches of dimensionality reduction techniques, with very promising horizons. Compressed sensing addresses the reconstruction of sparse signals from ill-conditioned linear measurements, a mathematical problem that arises in practical applications in one of the following forms: model fitting (regression), analog data compression, sub-Nyquist sampling, and data privacy. Low-rank matrix estimation addresses the reconstruction of multi-dimensional data (matrices) with strong coherence properties (low rank) under restricted sensing. This model is motivated by modern problems in machine learning, dynamic systems, and quantum computing.

This thesis provides an in-depth study of recent developments in the fields of compressed sensing and matrix rank minimization, and sets forth new directions for improved sparse recovery techniques. The contributions are threefold: the design of combinatorial structures for sparse encoding, the development of improved recovery algorithms, and extension of sparse vector recovery techniques to other problems.

We propose combinatorial structures for the measurement matrix that facilitate compressing sparse analog signal representations with better guarantees than any of the currently existing architectures. Our constructions are mostly deterministic and are based on ideas from expander graphs, LDPC error-correcting codes and combinatorial separators.

We propose novel reconstruction algorithms that are amenable to the combinatorial structures we study, and have various advantages over the conventional convex optimization techniques for sparse recovery. In addition, we separately study the convex optimization Basis Pursuit method for compressed sensing, and propose regularization schemes that expand the success domain for such algorithms. Our studies contain rigorous analysis, numerical simulations, and examples from practical applications.

Lastly, we extend some of our proposed techniques to low-rank matrix estimation and channel coding. These generalizations lead to the development of a novel and fast reconstruction algorithm for matrix rank minimization, and a modified regularized linear-programming-based decoding algorithm for detecting codewords of a linear LDPC code during an erroneous communication.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:compressed sensing, dimensionality reduction, regression, sparsity
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Awards:Charles and Ellen Wilts Prize, 2012
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Hassibi, Babak
Thesis Committee:
  • Hassibi, Babak (chair)
  • Vaidyanathan, P. P.
  • Tropp, Joel A.
  • Ho, Tracey C.
  • Dimakis, Alexandros G.
Defense Date:2 February 2012
Record Number:CaltechTHESIS:06072012-001523622
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7142
Deposited By: Mohammadamin Khajehnejad
Deposited On:08 Jun 2012 21:47
Last Modified:07 Jun 2023 17:26

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page