[proofplan]
We first prove the restricted isometry estimate on one fixed support $S \subset \{1,\dots,d\}$ of size $k$. For that support, a fixed-vector subgaussian concentration estimate controls $|Au|^2$ for each unit vector $u \in \mathbb{R}^S$; an $\eta$-net and a symmetric-operator approximation argument upgrade this pointwise control to uniform control on the whole unit sphere in $\mathbb{R}^S$. Finally, we take a union bound over all possible supports and choose the numerical constant in the lower bound for $n$ large enough to absorb the entropy of the supports and the net.
[/proofplan]
[step:Record the fixed-vector concentration estimate used for the random matrix]
We use the following standard concentration estimate for isotropic subgaussian random matrices: there is a constant $a = a(K) > 0$ such that, for every deterministic vector $u \in \mathbb{R}^d$ with $|u| = 1$ and every $0 < t < 1$,
\begin{align*}
\mathbb{P}\bigl(\bigl||Au|^2 - 1\bigr| > t\bigr) \leq 2\exp(-a t^2 n).
\end{align*}
This is the only probabilistic input in the proof. It is a standard consequence of concentration of sums of independent centered subexponential random variables obtained from the squares of subgaussian linear forms (citing a result not yet in the wiki: concentration of isotropic subgaussian quadratic forms).
Set
\begin{align*}
a_0 := \frac{a}{4}.
\end{align*}
Applying the displayed estimate with $t = \delta/2$ gives, for every deterministic unit vector $u \in \mathbb{R}^d$,
\begin{align*}
\mathbb{P}\bigl(\bigl||Au|^2 - 1\bigr| > \delta/2\bigr) \leq 2\exp(-a_0\delta^2 n).
\end{align*}
[/step]
[step:Construct a finite net on each coordinate sphere]
Fix a set $S \subset \{1,\dots,d\}$ with $|S| = k$. Define the coordinate subspace
\begin{align*}
\mathbb{R}^S := \{x \in \mathbb{R}^d : \operatorname{supp}x \subset S\}.
\end{align*}
Let
\begin{align*}
\mathbb{S}_S := \{u \in \mathbb{R}^S : |u| = 1\}
\end{align*}
be its Euclidean unit sphere. There exists a finite set $\mathcal{N}_S \subset \mathbb{S}_S$ such that every $u \in \mathbb{S}_S$ has some $v \in \mathcal{N}_S$ with $|u-v| \leq 1/4$, and
\begin{align*}
|\mathcal{N}_S| \leq 9^k.
\end{align*}
Indeed, take $\mathcal{N}_S$ maximal with respect to the property that distinct points of $\mathcal{N}_S$ have mutual distance greater than $1/4$. Maximality gives the covering property. The open Euclidean balls in $\mathbb{R}^S$ with radius $1/8$ and centers in $\mathcal{N}_S$ are disjoint and are contained in the ball of radius $1+1/8 = 9/8$ centered at $0$. Comparing $k$-dimensional Euclidean volumes in $\mathbb{R}^S$ gives
\begin{align*}
|\mathcal{N}_S|\left(\frac{1}{8}\right)^k \leq \left(\frac{9}{8}\right)^k,
\end{align*}
hence $|\mathcal{N}_S| \leq 9^k$.
[/step]
[step:Upgrade the net estimate to all vectors on a fixed support]
Define the symmetric linear operator $B_S: \mathbb{R}^S \to \mathbb{R}^S$ by
\begin{align*}
B_S := A_S^\top A_S - I_S,
\end{align*}
where $A_S: \mathbb{R}^S \to \mathbb{R}^n$ is the restriction $u \mapsto Au$ and $I_S: \mathbb{R}^S \to \mathbb{R}^S$ is the identity map. Then, for every $u \in \mathbb{S}_S$,
\begin{align*}
\langle B_Su,u\rangle = |Au|^2 - |u|^2 = |Au|^2 - 1.
\end{align*}
Let
\begin{align*}
M_S := \sup_{u \in \mathbb{S}_S} |\langle B_Su,u\rangle|,
\qquad
M_S^{\mathcal{N}} := \sup_{v \in \mathcal{N}_S} |\langle B_Sv,v\rangle|.
\end{align*}
Choose $u_0 \in \mathbb{S}_S$ so that
\begin{align*}
M_S \leq |\langle B_Su_0,u_0\rangle| + \varepsilon
\end{align*}
for a fixed $\varepsilon > 0$. Choose $v_0 \in \mathcal{N}_S$ with $|u_0-v_0| \leq 1/4$. Since $B_S$ is symmetric, bilinear expansion gives
\begin{align*}
|\langle B_Su_0,u_0\rangle - \langle B_Sv_0,v_0\rangle| = |\langle B_S(u_0-v_0),u_0\rangle + \langle B_Sv_0,u_0-v_0\rangle|.
\end{align*}
Using the definition of $M_S$ by homogeneity on the two displayed terms, together with $|u_0|=|v_0|=1$ and $|u_0-v_0| \leq 1/4$, we obtain
\begin{align*}
|\langle B_Su_0,u_0\rangle - \langle B_Sv_0,v_0\rangle| \leq M_S |u_0-v_0|\,|u_0| + M_S |v_0|\,|u_0-v_0| \leq \frac{1}{2}M_S.
\end{align*}
Therefore
\begin{align*}
M_S \leq M_S^{\mathcal{N}} + \frac{1}{2}M_S + \varepsilon.
\end{align*}
Letting $\varepsilon \downarrow 0$ gives
\begin{align*}
M_S \leq 2M_S^{\mathcal{N}}.
\end{align*}
Thus, if
\begin{align*}
\bigl||Av|^2 - 1\bigr| \leq \delta/2
\end{align*}
for every $v \in \mathcal{N}_S$, then $M_S \leq \delta$, which means
\begin{align*}
(1-\delta)|u|^2 \leq |Au|^2 \leq (1+\delta)|u|^2
\end{align*}
for every $u \in \mathbb{R}^S$.
[guided]
The purpose of the net is to replace infinitely many unit vectors in $\mathbb{S}_S$ by finitely many test vectors. The only point that needs justification is why control on the finite set $\mathcal{N}_S$ controls every unit vector.
Define the map $B_S: \mathbb{R}^S \to \mathbb{R}^S$ by
\begin{align*}
B_S := A_S^\top A_S - I_S,
\end{align*}
where $A_S: \mathbb{R}^S \to \mathbb{R}^n$ is the restriction $u \mapsto Au$ and $I_S$ is the identity map on $\mathbb{R}^S$. This operator is symmetric because both $A_S^\top A_S$ and $I_S$ are symmetric. For each $u \in \mathbb{S}_S$,
\begin{align*}
\langle B_Su,u\rangle = |Au|^2 - |u|^2 = |Au|^2 - 1.
\end{align*}
Thus bounding $|\langle B_Su,u\rangle|$ uniformly over the sphere is exactly the restricted isometry estimate on this support.
Set
\begin{align*}
M_S := \sup_{u \in \mathbb{S}_S} |\langle B_Su,u\rangle|,
\qquad
M_S^{\mathcal{N}} := \sup_{v \in \mathcal{N}_S} |\langle B_Sv,v\rangle|.
\end{align*}
We prove $M_S \leq 2M_S^{\mathcal{N}}$. Fix $\varepsilon > 0$ and choose $u_0 \in \mathbb{S}_S$ such that
\begin{align*}
M_S \leq |\langle B_Su_0,u_0\rangle| + \varepsilon.
\end{align*}
Because $\mathcal{N}_S$ is a $1/4$-net, there is $v_0 \in \mathcal{N}_S$ with $|u_0-v_0| \leq 1/4$. We compare the quadratic form at $u_0$ with the quadratic form at $v_0$:
\begin{align*}
\langle B_Su_0,u_0\rangle - \langle B_Sv_0,v_0\rangle
= \langle B_S(u_0-v_0),u_0\rangle + \langle B_Sv_0,u_0-v_0\rangle.
\end{align*}
Since $B_S$ is symmetric, the definition of $M_S$ controls the associated [bilinear form](/page/Bilinear%20Form) on unit vectors by polarization, and hence by homogeneity controls it on arbitrary vectors in $\mathbb{R}^S$. Therefore
\begin{align*}
|\langle B_S(u_0-v_0),u_0\rangle| \leq M_S |u_0-v_0|\,|u_0|.
\end{align*}
The same homogeneity estimate applied to $v_0$ and $u_0-v_0$ gives
\begin{align*}
|\langle B_Sv_0,u_0-v_0\rangle| \leq M_S |v_0|\,|u_0-v_0|.
\end{align*}
Using $|u_0| = |v_0| = 1$ and $|u_0-v_0| \leq 1/4$, we obtain
\begin{align*}
|\langle B_Su_0,u_0\rangle - \langle B_Sv_0,v_0\rangle|
\leq \frac{1}{2}M_S.
\end{align*}
It follows that
\begin{align*}
M_S \leq M_S^{\mathcal{N}} + \frac{1}{2}M_S + \varepsilon.
\end{align*}
Letting $\varepsilon \downarrow 0$ gives $M_S \leq 2M_S^{\mathcal{N}}$.
Consequently, if the finite net satisfies
\begin{align*}
\bigl||Av|^2 - 1\bigr| \leq \delta/2
\end{align*}
for every $v \in \mathcal{N}_S$, then $M_S^{\mathcal{N}} \leq \delta/2$, so $M_S \leq \delta$. By homogeneity, this gives
\begin{align*}
(1-\delta)|u|^2 \leq |Au|^2 \leq (1+\delta)|u|^2
\end{align*}
for every $u \in \mathbb{R}^S$, not only for unit vectors.
[/guided]
[/step]
[step:Bound the failure probability for one support]
For the fixed support $S$, define the event
\begin{align*}
E_S := \left\{\bigl||Av|^2 - 1\bigr| \leq \delta/2 \text{ for every } v \in \mathcal{N}_S\right\}.
\end{align*}
By the fixed-vector concentration estimate and the union bound over $\mathcal{N}_S$,
\begin{align*}
\mathbb{P}(E_S^c) \leq \sum_{v \in \mathcal{N}_S} \mathbb{P}\bigl(\bigl||Av|^2 - 1\bigr| > \delta/2\bigr) \leq 2|\mathcal{N}_S|\exp(-a_0\delta^2 n) \leq 2\exp\bigl(k\log 9 - a_0\delta^2 n\bigr).
\end{align*}
On $E_S$, the preceding step proves
\begin{align*}
(1-\delta)|u|^2 \leq |Au|^2 \leq (1+\delta)|u|^2
\end{align*}
for every $u \in \mathbb{R}^S$.
[/step]
[step:Take the union bound over all supports]
Let
\begin{align*}
\mathcal{S}_k := \{S \subset \{1,\dots,d\} : |S| = k\}
\end{align*}
be the family of all coordinate supports of cardinality $k$. The standard binomial estimate gives
\begin{align*}
|\mathcal{S}_k| = \binom{d}{k} \leq \left(\frac{ed}{k}\right)^k.
\end{align*}
Define
\begin{align*}
E := \bigcap_{S \in \mathcal{S}_k} E_S.
\end{align*}
Using the union bound over $\mathcal{S}_k$ and the estimate for each $E_S^c$,
\begin{align*}
\mathbb{P}(E^c) \leq \sum_{S \in \mathcal{S}_k} \mathbb{P}(E_S^c) \leq 2\exp\left(k\log\!\left(\frac{ed}{k}\right) + k\log 9 - a_0\delta^2 n\right).
\end{align*}
Since $1 \leq k \leq d$, we have $\log(ed/k) \geq 1$, and hence
\begin{align*}
k\log 9 \leq (\log 9)k\log\!\left(\frac{ed}{k}\right).
\end{align*}
Choose
\begin{align*}
C := \frac{2(1+\log 9)}{a_0}
\qquad\text{and}\qquad
c := \frac{a_0}{2}.
\end{align*}
If
\begin{align*}
n \geq C\delta^{-2}k\log\!\left(\frac{ed}{k}\right),
\end{align*}
then
\begin{align*}
k\log\!\left(\frac{ed}{k}\right) + k\log 9
\leq \frac{a_0}{2}\delta^2 n.
\end{align*}
Therefore
\begin{align*}
\mathbb{P}(E^c) \leq 2\exp(-c\delta^2 n).
\end{align*}
[/step]
[step:Identify the event with the restricted isometry bound]
On the event $E$, for every support $S \in \mathcal{S}_k$ and every vector $u \in \mathbb{R}^S$,
\begin{align*}
(1-\delta)|u|^2 \leq |Au|^2 \leq (1+\delta)|u|^2.
\end{align*}
Now let $x \in \mathbb{R}^d$ satisfy $|\operatorname{supp}x| \leq k$. Choose a set $S \in \mathcal{S}_k$ with $\operatorname{supp}x \subset S$; this is possible because $k \leq d$. Then $x \in \mathbb{R}^S$, so the preceding estimate gives
\begin{align*}
(1-\delta)|x|^2 \leq |Ax|^2 \leq (1+\delta)|x|^2.
\end{align*}
By the definition of $\delta_k(A)$, this means $\delta_k(A) \leq \delta$ on $E$. Hence
\begin{align*}
\mathbb{P}\bigl(\delta_k(A) \leq \delta\bigr) \geq \mathbb{P}(E) = 1 - \mathbb{P}(E^c) \geq 1 - 2\exp(-c\delta^2 n).
\end{align*}
This proves the theorem.
[/step]
