Sparse Recovery, Compressed Sensing and the Lasso

Restricted isometry, restricted eigenvalues, the lasso error bound, and why sparsity turns an impossible problem into a tractable one.

High-Dim StatisticsResearch⏱ 1 day13 min readlassosparsitycompressed sensingriprestricted eigenvalue

6 problems →

AssumesCovariance Estimation and Sample Complexity · Convex Sets, Convex Functions, Smoothness and Strong Convexity

The restricted isometry property

DefinitionRestricted isometry property

$X \in \R^{n\times p}$ satisfies the $(s,\delta)$ -restricted isometry property (RIP) if

(1-\delta)\norm{\beta}_2^2 \;\le\; \frac{1}{n}\norm{X\beta}_2^2 \;\le\; (1+\delta)\norm{\beta}_2^2

for every $\beta$ with $\norm{\beta}_0 \le s$ , where $\norm{\beta}_0$ counts non-zeros.

Compare the form of this condition with the conclusion of the Johnson–Lindenstrauss lemma: it is the same $1\pm\delta$ two-sided norm preservation, but required uniformly over an infinite set (all $s$ -sparse vectors) rather than a finite one. That is exactly the situation nets were built for.

TheoremRandom matrices satisfy the RIP

Let $X\in\R^{n\times p}$ have i.i.d. $\Ncal(0,1)$ entries and fix $\delta\in(0,1)$ . There is an absolute constant $C$ such that if

n \ge \frac{C}{\delta^2}\, s\log\frac{p}{s},

then $X$ satisfies the $(s,\delta)$ -RIP with probability at least $1 - 2e^{-c\delta^2 n}$ .

Key idea

The exponent bookkeeping again. There are $(ep/s)^s = e^{s\log(ep/s)}$ support sets; each fails with probability $e^{-c\delta^2 n}$ once $n \gtrsim s/\delta^2$ ; so we need $\delta^2 n \gtrsim s\log(p/s)$ . The $\log(p/s)$ is the union bound over supports and the $s/\delta^2$ is the per-support covariance estimate. Both factors are necessary, and together they are the information-theoretic optimum up to constants.

TheoremExact recovery by basis pursuit

Suppose $X$ satisfies the $(2s,\delta)$ -RIP with $\delta < \sqrt2 - 1$ , and let $y = X\beta^\star$ for some $\beta^\star$ with $\norm{\beta^\star}_0\le s$ . Then the solution of the convex program

\hat\beta = \argmin_{\beta}\ \norm{\beta}_1 \quad\text{subject to}\quad X\beta = y

satisfies $\hat\beta = \beta^\star$ .

Quoted from Candès–Tao and the Foucart–Rauhut text. The mechanism worth understanding even without the proof: $\norm{\cdot}_1$ is the convex function whose sublevel sets — the $\ell^1$ balls — have vertices exactly at the sparse vectors. Minimising a linear functional over a polytope lands at a vertex; minimising $\norm{\cdot}_1$ over an affine subspace therefore lands at a sparse point, when it lands anywhere distinguished at all. Replacing $\norm{\cdot}_0$ (non-convex, NP-hard to minimise) by $\norm{\cdot}_1$ is not an approximation that happens to work; it is the convex envelope of the sparsity constraint on the unit ball, and the RIP is the condition under which the relaxation is tight.

The lasso

With noise, exact recovery is impossible and the goal becomes estimation. Consider

y = X\beta^\star + w, \qquad w \sim \Ncal(0,\sigma^2I_n),

and the lasso estimator

\hat\beta \in \argmin_{\beta\in\R^p}\ \left\{\frac{1}{2n}\norm{y - X\beta}_2^2 + \lambda\norm{\beta}_1\right\}.

DefinitionRestricted eigenvalue condition

$X$ satisfies the restricted eigenvalue condition with constant $\gamma>0$ over a cone $\mathcal{C}$ if

\frac{1}{n}\norm{X v}_2^2 \ge \gamma\norm{v}_2^2 \qquad\text{for all } v \in \mathcal{C}.

The relevant cone for the lasso is $\mathcal{C}(S) = \{v : \norm{v_{S^c}}_1 \le 3\norm{v_S}_1\}$ , where $S = \operatorname{supp}(\beta^\star)$ .

TheoremLasso error bound

Let $S = \operatorname{supp}(\beta^\star)$ with $|S| = s$ , suppose the columns of $X$ are normalised so that $\norm{X_j}_2 \le\sqrt n$ , and suppose the restricted eigenvalue condition holds with constant $\gamma$ over $\mathcal{C}(S)$ . If

\lambda \ge 2\sigma\sqrt{\frac{2\log(2p/\delta)}{n}},

then with probability at least $1-\delta$ ,

\norm{\hat\beta - \beta^\star}_2 \le \frac{3\sqrt s\,\lambda}{\gamma}, \qquad \frac{1}{n}\norm{X(\hat\beta - \beta^\star)}_2^2 \le \frac{9s\lambda^2}{\gamma} .

With $\lambda \asymp \sigma\sqrt{\log p / n}$ this is $\norm{\hat\beta-\beta^\star}_2^2 \lesssim \sigma^2 s\log p/(\gamma^2 n)$ .

Assumptions

Independent Gaussian noise with known scale, column normalisation, a restricted eigenvalue condition with a known constant $\gamma$ , and a regularisation parameter $\lambda$ chosen at least as large as the stated threshold — which depends on $\sigma$ . In practice $\sigma$ is unknown and $\lambda$ is chosen by cross-validation, which the theorem does not cover.

Key idea

Read the rate: $\sigma^2 s\log p/n$ instead of $\sigma^2 p/n$ . Sparsity replaces the ambient dimension $p$ by the sparsity level $s$ , at the cost of a $\log p$ factor. The $\log p$ is the price of not knowing which $s$ coordinates matter — it is the union bound over the $p$ coordinates in Step 2, and if the support were known the rate would be exactly $\sigma^2 s/n$ .

TheoremMinimax rate for sparse regression

Over the class $\{\beta : \norm\beta_0\le s\}$ with a suitable design, every estimator $\tilde\beta$ satisfies

\sup_{\norm{\beta^\star}_0\le s}\E\norm{\tilde\beta - \beta^\star}_2^2 \;\gtrsim\; \frac{\sigma^2 s\log(p/s)}{n}.

Quoted from Wainwright's text; the proof is a Fano-type argument over a well-separated packing of sparse vectors. Combined with the lasso bound, the conclusion is that the lasso is minimax optimal up to constants — a genuinely strong statement, and one of the reasons the estimator is as important as it is.

Open problemCertifying the RIP for a given matrix

Open problem — no proof and no counterexample is known to the author of this page.

The theorem above says a random Gaussian matrix satisfies the RIP with high probability. Given a specific matrix, deciding whether it satisfies the $(s,\delta)$ -RIP is a different question, and no polynomial-time algorithm is known for it; the natural formulations are NP-hard. So compressed sensing guarantees in practice rest on randomised constructions rather than on verification.

What this does not say

The lasso bound is about estimation and prediction, not about support recovery. Getting $\operatorname{supp}(\hat\beta) = \operatorname{supp}(\beta^\star)$ requires stronger conditions — an irrepresentable or incoherence condition on the design, plus a minimum signal strength $\min_{j\in S}|\beta^\star_j| \gtrsim \lambda$ . Without a beta-min condition, a coefficient too small to distinguish from noise will be missed, and no method can do better. Reporting the selected support as though it were a discovery, with no such condition checked, is one of the more common over-claims in applied high-dimensional statistics.

Problems

The lasso error vector lies in a coneProof · Graduate · 1 hour Union bound over supports for the restricted isometry propertyProof · Advanced · 1 hour The geometry of l1 versus l2 constraintsProof · Intermediate · 30 min Derive the soft-thresholding operatorProof · Intermediate · 30 min Implement ISTA and verify the lasso rateCoding · Advanced · 3 hours

References

PaperEmmanuel J. Candès and Terence Tao (2005). Decoding by linear programming
PaperDavid L. Donoho (2006). Compressed sensing
PaperPeter J. Bickel, Ya'acov Ritov and Alexandre B. Tsybakov (2009). Simultaneous analysis of Lasso and Dantzig selectorThe source of the restricted-eigenvalue analysis whose structure the proof below follows.
BookMartin J. Wainwright (2019). High-Dimensional Statistics: A Non-Asymptotic ViewpointChapters 7 and 11 treat sparse linear models and minimax lower bounds.
BookSimon Foucart and Holger Rauhut (2013). A Mathematical Introduction to Compressive Sensing

These works are cited as sources to read, not reproduced. All exposition, examples and problems on this site are written independently; where an argument is standard, the citation points to a canonical treatment.

Results stated on this page

DefinitionRestricted isometry propertyA matrix acts as a near-isometry on all sparse vectors.
TheoremRandom matrices satisfy the RIPproof includedA Gaussian matrix with order s log(p/s) rows satisfies the restricted isometry property with high probability.
TheoremExact recovery by basis pursuit under RIPUnder a restricted isometry condition, minimising the l1 norm subject to the measurements recovers every sparse signal exactly.
TheoremLasso prediction and estimation errorproof includedUnder a restricted eigenvalue condition the lasso attains squared error of order s log(p) / n.
TheoremMinimax rate for sparse regressionNo estimator can beat s log(p/s) / n uniformly over s-sparse signals, so the lasso is optimal up to constants.
Open problemCertifying the RIP for a given matrixDeciding whether a specific matrix satisfies the restricted isometry property is computationally hard in general.

Problems (6)

All problems