A Caltech Library Service

Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing

Thrampoulidis, Christos and Oymak, Samet and Hassibi, Babak (2015) Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing. In: Compressed Sensing and its Applications. Applied and Numerical Harmonic Analysis. Springer , Cham, pp. 97-141. ISBN 978-3-319-16041-2.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The typical scenario that arises in most “big data” problems is one where the ambient dimension of the signal is very large (e.g., high resolution images, gene expression data from a DNA microarray, social network data, etc.), yet is such that its desired properties lie in some low dimensional structure (sparsity, low-rankness, clusters, etc.). In the modern viewpoint, the goal is to come up with efficient algorithms to reveal these structures and for which, under suitable conditions, one can give theoretical guarantees. We specifically consider the problem of recovering such a structured signal (sparse, low-rank, block-sparse, etc.) from noisy compressed measurements. A general algorithm for such problems, commonly referred to as generalized LASSO, attempts to solve this problem by minimizing a least-squares cost with an added “structure-inducing” regularization term (ℓ_ 1 norm, nuclear norm, mixed ℓ _2/ℓ_ 1 norm, etc.). While the LASSO algorithm has been around for 20 years and has enjoyed great success in practice, there has been relatively little analysis of its performance. In this chapter, we will provide a full performance analysis and compute, in closed form, the mean-square-error of the reconstructed signal. We will highlight some of the mathematical vignettes necessary for the analysis, make connections to noiseless compressed sensing and proximal denoising, and will emphasize the central role of the “statistical dimension” of a structured signal.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Thrampoulidis, Christos0000-0001-9053-9365
Additional Information:© 2015 Springer International Publishing Switzerland. The authors gratefully acknowledge the anonymous reviewers for their attention and their helpful comments.
Series Name:Applied and Numerical Harmonic Analysis
Record Number:CaltechAUTHORS:20160901-121710649
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:70119
Deposited By: Tony Diaz
Deposited On:01 Sep 2016 19:35
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page