Lecture 21: Sparse Recovery
Random measurements, the escape theorem, and basis pursuit
The last application of the course is a problem from signal processing and statistics. An unknown vector \(x\in\mathbb R^n\) is observed only through \(m\ll n\) linear measurements \(y=Ax\), and the task is to recover it. Without further information the problem is hopeless, since the solutions of \(Ax'=y\) form an affine subspace of dimension \(n-m\). With the information that \(x\) is sparse, and with \(A\) random, the problem becomes solvable, by a convex program, from \(m\approx s\log(n/s)\) measurements for an \(s\)-sparse signal. The entire analysis is one application of the matrix deviation inequality of Lecture 19 to a set whose Gaussian width was computed in Lecture 13, and the reason the recovery is exact is the random cone picture previewed there.
Throughout, \(A\) is an \(m\times n\) matrix with independent, mean-zero, isotropic, \(K\)-subgaussian rows, and \(w(T)\) and \(\operatorname{rad}(T)\) are as in Lecture 19.
1 The kernel of a random matrix meets a set
Everything rests on one geometric fact: the kernel of \(A\), a random subspace of codimension \(m\), is nearly disjoint from any set whose Gaussian width is small compared to \(\sqrt m\).
Theorem 1 (Diameter of a section by the kernel) For every bounded \(T\subseteq\mathbb R^n\), \[ \mathbb E\operatorname{diam}\big(T\cap\ker A\big)\leq\frac{CKw(T)}{\sqrt m}. \]
Let \(x,y\in T\cap\ker A\). Then \(A(x-y)=0\), so \[ \sqrt m\|x-y\|_2=\Big|\|A(x-y)\|_2-\sqrt m\|x-y\|_2\Big|\leq\sup_{z\in T-T}\Big|\|Az\|_2-\sqrt m\|z\|_2\Big| . \] Take the supremum over \(x,y\) and expectations. By the matrix deviation inequality of Lecture 19 applied to \(T-T\), whose width is \(2w(T)\) and whose radius is \(\operatorname{diam}(T)\leq Cw(T)\) (Lecture 20), \[ \sqrt m\,\mathbb E\operatorname{diam}(T\cap\ker A)\leq CK\big(2w(T)+\operatorname{diam}(T)\big)\leq C'Kw(T). \]
For \(T=B_2^n\) the theorem says nothing, since \(\ker A\) contains an \((n-m)\)-dimensional ball. For \(T=B_1^n\), with \(w(B_1^n)\asymp\sqrt{\log n}\) (Lecture 3), it says that a random subspace of codimension \(m\) meets the \(\ell^1\) ball in a set of diameter about \(\sqrt{\log n/m}\), although the ball has diameter \(2\). This is the phenomenon behind everything below: the \(\ell^1\) ball is large in every coordinate direction but small in most directions, and a random subspace sees only the small ones. The bound is due to Milman and the high-dimensional literature calls it the \(M^*\) bound, after the notation \(M^*\) for the spherical width.
For sets on the sphere there is a stronger, high-probability statement: the kernel misses the set entirely.
Theorem 2 (The escape theorem) Let \(T\subseteq S^{n-1}\). If \(m\geq CK^2\big(w(T)+1\big)^2\), then \[ \mathbb P\big\{T\cap\ker A=\varnothing\big\}\geq1-2\exp\Big(-\frac{cm}{K^2(w(T)+1)^2}\Big). \]
If \(z\in T\cap\ker A\) then \(\|Az\|_2=0\) and \(\|z\|_2=1\), so \(\sup_{x\in T}|\|Ax\|_2-\sqrt m\|x\|_2|\geq\sqrt m\). By the tail form of the matrix deviation inequality, with probability at least \(1-2e^{-u^2}\) this supremum is at most \(C_0K(1+u)(w(T)+1)\). Choose \(u\) so that \(C_0K(1+u)(w(T)+1)=\sqrt m/2\), which is possible with \(u\geq1\) once \(m\geq16C_0^2K^2(w(T)+1)^2\). On the good event, \(\sqrt m\leq\sqrt m/2\) is impossible, so \(T\cap\ker A=\varnothing\), and \(u^2\geq cm/(K^2(w(T)+1)^2)\).
The theorem is due to Gordon (Gordon 1988) for Gaussian matrices, in the sharp form: a subspace of codimension \(m\) misses \(T\subseteq S^{n-1}\) with high probability as soon as \(\sqrt m\) exceeds \(w(T)\) by a constant, with no unspecified factor. In the language of Lecture 13, the kernel is a cone of statistical dimension \(n-m\), the cone generated by \(T\) has statistical dimension about \(w(T)^2\), and the two miss each other when the dimensions add to less than \(n\).
2 Recovery with a prior set
Model the prior knowledge about the signal by a set \(T\subseteq\mathbb R^n\) with \(x\in T\), and consider the simplest conceivable procedure: output any \(\hat x\) consistent with the data and the prior, \[ \text{find }\hat x\in T\ \text{ with }\ A\hat x=y . \tag{1}\] If \(T\) is convex, this is a convex feasibility problem, and it can be solved efficiently.
Theorem 3 (Recovery from a prior set) Let \(y=Ax\) with \(x\in T\), and let \(\hat x\) be any solution of Equation 1. Then \[ \mathbb E\|\hat x-x\|_2\leq\frac{CKw(T)}{\sqrt m}. \] If the measurements are noisy, \(y=Ax+\nu\), and \(\hat x\in T\) satisfies \(\|A\hat x-y\|_2\leq\|\nu\|_2\), then \(\mathbb E\|\hat x-x\|_2\leq CK\,w(T)/\sqrt m+2\|\nu\|_2/\sqrt m\).
Both \(x\) and \(\hat x\) lie in \(T\), and \(A\hat x=Ax\), so both lie in \(T\cap(x+\ker A)\). Hence \[ \|\hat x-x\|_2\leq\operatorname{diam}\big(T\cap(x+\ker A)\big)=\operatorname{diam}\big((T-x)\cap\ker A\big), \] and \(w(T-x)=w(T)\) by translation invariance. Apply Theorem 1 to \(T-x\). For the noisy case, \(h=\hat x-x\) satisfies \(\|Ah\|_2\leq\|A\hat x-y\|_2+\|y-Ax\|_2\leq2\|\nu\|_2\), and the matrix deviation inequality on \(T-T\) gives \(\sqrt m\|h\|_2\leq\|Ah\|_2+\sup_{z\in T-T}|\|Az\|_2-\sqrt m\|z\|_2|\).
Two remarks put the theorem in perspective. First, the set \(T\) may be replaced by its convex hull without changing the guarantee, since \(w(\operatorname{conv}T)=w(T)\) (Lecture 3); so a nonconvex prior can be convexified for free. Second, in terms of the stable dimension \(d(T)=w(T)^2/\operatorname{diam}(T)^2\) of Lecture 13, the relative error \(\mathbb E\|\hat x-x\|_2\leq\varepsilon\operatorname{diam}(T)\) is achieved as soon as \[ m\geq\frac{CK^2d(T)}{\varepsilon^2}. \] The number of measurements needed is the stable dimension of the prior set, which can be far smaller than \(n\).
3 Sparse signals
Write \(\|x\|_0\) for the number of nonzero coordinates of \(x\), and call \(x\) \(s\)-sparse if \(\|x\|_0\leq s\). Sparsity is the prior that most coordinates of the signal are zero, without knowing which. It is a natural prior in many settings: a handful of genes among thousands affect a trait, or a signal has few active frequencies. The set of sparse vectors is not convex, and the program Equation 1 over it is a combinatorial search over \(\binom ns\) supports. The remedy is the one Lecture 14 used for the discrete cube: relax to the tightest convex set available.
Lemma 1 (The convex hull of the sparse vectors) Let \(S_{n,s}:=\{x\in\mathbb R^n:\|x\|_0\leq s,\ \|x\|_2\leq1\}\) and \(T_{n,s}:=\sqrt s\,B_1^n\cap B_2^n\). Then \[ S_{n,s}\subseteq T_{n,s}\subseteq2\operatorname{conv}(S_{n,s}). \] Consequently \(w(T_{n,s})\asymp w(S_{n,s})\asymp\sqrt{s\log(en/s)}\).
The first inclusion is the Cauchy–Schwarz inequality \(\|x\|_1\leq\sqrt s\|x\|_2\) for \(s\)-sparse \(x\). For the second, let \(x\in T_{n,s}\) and partition its support into blocks \(I_1,I_2,\ldots\) of size \(s\), with \(I_1\) the \(s\) largest coordinates in absolute value, \(I_2\) the next \(s\), and so on. Each coordinate of \(x_{I_j}\) for \(j\geq2\) is at most the average absolute coordinate of \(x_{I_{j-1}}\), which is \(\|x_{I_{j-1}}\|_1/s\), so \[ \|x_{I_j}\|_2\leq\sqrt s\cdot\frac{\|x_{I_{j-1}}\|_1}s=\frac{\|x_{I_{j-1}}\|_1}{\sqrt s} \qquad(j\geq2), \] and summing, \(\sum_{j\geq2}\|x_{I_j}\|_2\leq\|x\|_1/\sqrt s\leq1\). With \(\|x_{I_1}\|_2\leq\|x\|_2\leq1\), the total \(\lambda:=\sum_j\|x_{I_j}\|_2\) is at most \(2\). Then \[ x=\sum_jx_{I_j}=\lambda\sum_j\frac{\|x_{I_j}\|_2}\lambda\cdot\frac{x_{I_j}}{\|x_{I_j}\|_2} \] exhibits \(x/\lambda\) as a convex combination of the \(s\)-sparse unit vectors \(x_{I_j}/\|x_{I_j}\|_2\in S_{n,s}\), so \(x\in\lambda\operatorname{conv}(S_{n,s})\subseteq2\operatorname{conv}(S_{n,s})\). The width statement follows from the invariance of width under convex hulls and the computation \(w(S_{n,s})\asymp\sqrt{s\log(en/s)}\) of Lecture 13.
So the relaxation of “\(s\)-sparse with \(\|x\|_2\leq1\)” is the truncated \(\ell^1\) ball \(T_{n,s}\), at the cost of a factor \(2\) in width. The recovery program Equation 1 becomes the convex problem \[ \text{find }\hat x\ \text{ with }\ A\hat x=y,\quad\|\hat x\|_1\leq\sqrt s,\quad\|\hat x\|_2\leq1 . \]
Corollary 1 (Sparse recovery, approximate) Let \(x\) be \(s\)-sparse with \(\|x\|_2\leq1\) and \(y=Ax\). Any solution \(\hat x\) of the program above satisfies \[ \mathbb E\|\hat x-x\|_2\leq CK\sqrt{\frac{s\log(en/s)}m}. \]
The error is small once \(m\gtrsim K^2s\log(en/s)\): the number of measurements is linear in the sparsity and only logarithmic in the ambient dimension. This is the regime \(m\ll n\) in which the linear system \(Ax=y\) is badly underdetermined, and it is solvable because the solution is sparse. The theorem is an instance of the stable-dimension remark above, since \(d(T_{n,s})\asymp s\log(en/s)\).
4 Exact recovery by basis pursuit
The approximate guarantee is not the end of the story. For an exactly sparse signal the recovery is exact, and the program can be simplified to one with no parameter \(s\) in it: \[ \hat x:=\operatorname*{arg\,min}\big\{\|x'\|_1:\ Ax'=y\big\}, \tag{2}\] called basis pursuit. The geometry is this. The \(\ell^1\) ball of radius \(\|x\|_1\) is a polytope, and an \(s\)-sparse \(x\) lies on one of its low-dimensional faces. The affine subspace \(x+\ker A\) passes through \(x\), and if it is tangent to the polytope there, touching it only at \(x\), then \(x\) is the unique minimizer of the \(\ell^1\) norm on the subspace. Tangency is a statement about the cone of directions that decrease the \(\ell^1\) norm at \(x\), the descent cone of Lecture 13, and the escape theorem says a random subspace misses this cone.
Lemma 2 (Error vectors of basis pursuit are nearly sparse) Let \(x\) be \(s\)-sparse with support \(S\), let \(\hat x\) be a minimizer in Equation 2, and let \(h=\hat x-x\). Then \[ \|h_{S^c}\|_1\leq\|h_S\|_1 \qquad\text{and hence}\qquad \|h\|_1\leq2\sqrt s\,\|h\|_2 . \]
Since \(x\) is feasible, \(\|\hat x\|_1\leq\|x\|_1\). On the other hand, using \(x_{S^c}=0\) and the triangle inequality on \(S\), \[ \|\hat x\|_1=\|x_S+h_S\|_1+\|h_{S^c}\|_1\geq\|x\|_1-\|h_S\|_1+\|h_{S^c}\|_1 . \] Combining gives the first claim. Then \(\|h\|_1\leq2\|h_S\|_1\leq2\sqrt s\|h_S\|_2\leq2\sqrt s\|h\|_2\).
Theorem 4 (Exact sparse recovery) There are constants \(C,c>0\) such that the following holds. If \[ m\geq CK^2s\log(en/s), \] then with probability at least \(1-2\exp(-cm/K^2)\), simultaneously for every \(s\)-sparse \(x\in\mathbb R^n\), the basis pursuit program Equation 2 with \(y=Ax\) has \(x\) as its unique solution.
Let \[ T'_s:=\big\{z\in S^{n-1}:\ \|z\|_1\leq2\sqrt s\big\}=2T_{n,s}\cap S^{n-1}\subseteq2T_{n,s}, \] so \(w(T'_s)\leq2w(T_{n,s})\leq C\sqrt{s\log(en/s)}\) by Lemma 1. By Theorem 2, if \(m\geq CK^2(w(T'_s)+1)^2\), which holds under the stated hypothesis, then \(T'_s\cap\ker A=\varnothing\) with probability at least \(1-2\exp(-cm/(K^2(w(T'_s)+1)^2))\), and the exponent is at least \(c'm/K^2\) when \(m\) is a large constant multiple of \(K^2(w(T'_s)+1)^2\), as we may assume by adjusting \(C\).
On this event, let \(x\) be any \(s\)-sparse vector and \(\hat x\) any minimizer of Equation 2. If \(h=\hat x-x\neq0\), then \(Ah=0\) and, by Lemma 2, \(h/\|h\|_2\in T'_s\). So \(h/\|h\|_2\in T'_s\cap\ker A\), which is empty. Hence \(h=0\): the minimizer is \(x\), and it is unique. The event does not depend on \(x\), which gives the simultaneous statement.
The theorem is the basic result of compressed sensing, due to Candès, Romberg and Tao (Candès et al. 2006) and Donoho (Donoho 2006). Three comments.
The sample size is optimal up to the constant. Any method that recovers every \(s\)-sparse vector from \(y=Ax\) needs \(m\geq2s\), since otherwise two distinct \(s\)-sparse vectors have the same image, and the logarithm is also necessary for stable recovery. The kinematic formula of Lecture 13 gives the exact constant for Gaussian \(A\): basis pursuit succeeds with high probability when \(m\geq(1+\varepsilon)\,\delta(D)\) and fails when \(m\leq(1-\varepsilon)\,\delta(D)\), where \(\delta(D)\approx2s\log(n/s)\) is the statistical dimension of the descent cone. The proof above is the same argument with the escape theorem in place of the sharp kinematic formula.
The program needs neither \(s\) nor \(\|x\|_2\). Unlike the feasibility program for \(T_{n,s}\), basis pursuit uses only the data. The sparsity enters only through the analysis.
Uniform versus nonuniform. The event in the theorem works for all sparse \(x\) at once, because the set \(T'_s\) contains the normalized error of every one of them. For a single fixed \(x\) the escape theorem could be applied to the smaller set \(D(x)\cap S^{n-1}\), the descent cone at that particular \(x\), and the constant improves.
5 Noise and the Lasso
With noisy measurements \(y=Ax+\nu\) the constraint \(Ax'=y\) is no longer appropriate. The standard replacement keeps the \(\ell^1\) constraint and fits the data by least squares: \[ \hat x:=\operatorname*{arg\,min}\big\{\|y-Ax'\|_2:\ \|x'\|_1\leq R\big\}, \tag{3}\] the Lasso of Tibshirani (Tibshirani 1996), in its constrained form. The parameter \(R\) is a bound on \(\|x\|_1\); we take \(R=\|x\|_1\) for the analysis.
Theorem 5 (Recovery with noise by the Lasso) Let \(x\) be \(s\)-sparse, let \(y=Ax+\nu\) with \(\nu\in\mathbb R^m\) a fixed vector, and let \(\hat x\) solve Equation 3 with \(R=\|x\|_1\). If \(m\geq CK^2s\log(en/s)\), then with probability at least \(1-2\exp(-cm/K^2)-n^{-1}\), \[ \|\hat x-x\|_2\leq\frac{C\sqrt K\sqrt{s\log n}\,\|\nu\|_2}m . \]
Let \(h=\hat x-x\). Since \(x\) is feasible for Equation 3, \(\|y-A\hat x\|_2\leq\|y-Ax\|_2=\|\nu\|_2\), and \(y-A\hat x=\nu-Ah\), so \(\|\nu-Ah\|_2^2\leq\|\nu\|_2^2\), which expands to \[ \|Ah\|_2^2\leq2\langle\nu,Ah\rangle=2\langle A^{\mathsf T}\nu,h\rangle\leq2\|A^{\mathsf T}\nu\|_\infty\|h\|_1 . \] Since \(\|\hat x\|_1\leq R=\|x\|_1\), the proof of Lemma 2 applies verbatim and gives \(\|h\|_1\leq2\sqrt s\|h\|_2\), so \(h/\|h\|_2\in T'_s\) if \(h\neq0\).
Lower bound on \(\|Ah\|_2\). By the tail form of the matrix deviation inequality on \(T'_s\), with probability at least \(1-2\exp(-cm/K^2)\) every \(z\in T'_s\) satisfies \(\|Az\|_2\geq\sqrt m-\sqrt m/2=\sqrt m/2\) under the hypothesis on \(m\), exactly as in the proof of Theorem 2. Hence \(\|Ah\|_2\geq\sqrt m\|h\|_2/2\).
Upper bound on \(\|A^{\mathsf T}\nu\|_\infty\). The \(j\)-th coordinate of \(A^{\mathsf T}\nu\) is \(\sum_i\nu_i\langle A_i,e_j\rangle\), a sum of independent variables, the \(i\)-th of which is \(K\nu_i^2\)-subgaussian; by the Pythagorean theorem of Lecture 5 it is \(K\|\nu\|_2^2\)-subgaussian, and the union bound of Lecture 4 over the \(n\) coordinates gives \(\|A^{\mathsf T}\nu\|_\infty\leq\sqrt K\|\nu\|_2\sqrt{2\log(2n^2)}\leq C\sqrt K\|\nu\|_2\sqrt{\log n}\) with probability at least \(1-n^{-1}\).
Conclusion. On the intersection of the two events, \[ \frac m4\|h\|_2^2\leq\|Ah\|_2^2\leq2\cdot C\sqrt K\|\nu\|_2\sqrt{\log n}\cdot2\sqrt s\|h\|_2 , \] and dividing by \(\|h\|_2\) gives the claim.
For Gaussian noise \(\nu\sim N(0,\sigma^2I_m)\) one has \(\|\nu\|_2\approx\sigma\sqrt m\), and the bound reads \[ \|\hat x-x\|_2\lesssim\sigma\sqrt{\frac{s\log n}m}, \] which is the rate of an oracle that knows the support of \(x\) and performs least squares on it, up to the logarithm. The logarithm is the price of not knowing the support, and it is unavoidable. The proof reused the two ingredients of the noiseless case, the cone lemma and the lower bound on \(\|Az\|_2\) over the cone, and added only a union bound for the noise.
6 Looking back
The sparse recovery theorems close a loop that began in the first week. The ingredients, in the order the course built them, are the volume bounds and covering numbers of Lecture 1, the Gaussian width of Lecture 3, sub-Gaussian and sub-exponential tails, net arguments for random matrices, the isonormal process and Gaussian comparison, chaining and the majorizing measure theorem, and the matrix deviation inequality. Each step turned a probabilistic question about a random object into a geometric question about a set, and the final answer, that \(s\log(n/s)\) random measurements determine an \(s\)-sparse vector, is a statement about the Gaussian width of a truncated \(\ell^1\) ball. That the width is the right measure of size in high dimension, not the dimension and not the volume, is the thesis of the course.