[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$.[/step]

[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: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]