Sharp Thresholds for Sparsity Recovery in the High-Dimensional and Noisy Setting Using l₁ Relaxations

Martin Wainwright
Department of Electrical Engineering and Computer Sciences
Department of Statistics
University of California, Berkeley


Wednesday, November 29, 2006
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

The problem of recovering the sparsity pattern of an unknown signal arises in various domains, including graphical model selection, signal denoising, constructive approximation, compressive sensing, and subset selection in regression. The standard optimization-theoretic formulation of sparsity recovery involves l₀-constraints, and typically leads to computationally intractable problems. This difficulty motivates the development and analysis of approximate methods; in particular, a great deal of work over the past decade has focused on the use of l₁-relaxations for sparsity recovery. In this work, we analyze the performance of l₁-constrained quadratic programming, also known in the statistics literature as the Lasso, for recovering an unknown signal in p dimensions with at most s non-zero entries based on a set of n noisy observations. Of interest is the growth rate n = n(p,s) in the number of observations required as a function of p and s for exact sparsity recovery. We analyze this question in the high-dimensional setting, in which both the model dimension p and number of observations n tend to infinity. Our main result is to establish, for a broad class of Gaussian measurement ensembles, precise thresholds on the required growth rate: i.e., for all n above threshold, the Lasso recovers the exact sparsity pattern with probability converging to one, and conversely *fails to recover* with probability converging to one for all n below threshold.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html