[proofplan] We prove uniform control of the empirical quadratic form $v \mapsto |Xv|^2/n$ over all $m$-sparse unit vectors. For each fixed support $S$ with $|S|=m$, an $\varepsilon$-net of the unit sphere in the coordinate subspace supported on $S$ reduces the problem to finitely many fixed Gaussian directions. A Chernoff bound for sums of squared standard normal variables controls each net point, and a union bound over the net and over all supports gives the required probability once $n$ dominates $m\log(ed/m)$. Finally, the net estimate is upgraded from the net to the whole sphere, and supports of size less than $m$ are handled by embedding them into supports of size $m$. [/proofplan]

[step:Control one fixed Gaussian direction by a Chernoff bound] Let $(\Omega,\mathcal{F},\mathbb{P})$ denote the probability space on which the random matrix $X$ is defined. For each $i\in\{1,\dots,n\}$, let $X_i:\Omega\to\mathbb{R}^d$ denote the measurable map giving the $i$-th row of $X$. Let $v \in \mathbb{R}^d$ satisfy $|v|=1$. For each $i\in\{1,\dots,n\}$, define the real-valued [random variable](/page/Random%20Variable) $Z_i:\Omega\to\mathbb{R}$ by $Z_i(\omega)=(X_i(\omega),v)_{\mathbb{R}^d}$. Since $X_i \sim \mathcal{N}(0,I_d)$ and the rows are independent, the variables $Z_1,\dots,Z_n$ are independent standard normal random variables. Therefore \begin{align*} \frac{|Xv|^2}{n}=\frac{1}{n}\sum_{i=1}^{n}Z_i^2. \end{align*} We claim that there is a universal constant $a>0$ such that \begin{align*} \mathbb{P}\left(\left|\frac{|Xv|^2}{n}-1\right|>\frac{1}{4}\right)\le 2e^{-an}. \end{align*} Indeed, for a standard normal random variable $Z$, the [Gaussian integral](/theorems/1140) gives \begin{align*} \mathbb{E}[e^{\lambda Z^2}]=(1-2\lambda)^{-1/2} \end{align*} for every $\lambda<1/2$. By independence, \begin{align*} \mathbb{E}\left[e^{\lambda\sum_{i=1}^{n}Z_i^2}\right]=(1-2\lambda)^{-n/2}. \end{align*} For the upper tail, choose $\lambda=1/10$. [Markov's inequality](/page/Markov%20Inequality) gives \begin{align*} \mathbb{P}\left(\sum_{i=1}^{n}Z_i^2\ge \frac{5n}{4}\right)\le e^{-n/8}\left(1-\frac{1}{5}\right)^{-n/2}= \exp\left(-n\left(\frac{1}{8}+\frac{1}{2}\log\left(\frac{4}{5}\right)\right)\right). \end{align*} The exponent is negative with absolute value a positive universal constant. For the lower tail, choose $\lambda=1/10$ and apply [Markov's inequality](/page/Markov%20Inequality) to $e^{-\lambda\sum_i Z_i^2}$: \begin{align*} \mathbb{P}\left(\sum_{i=1}^{n}Z_i^2\le \frac{3n}{4}\right) &\le e^{3n/40}\left(1+\frac{1}{5}\right)^{-n/2} = \exp\left(-n\left(\frac{1}{2}\log\left(\frac{6}{5}\right)-\frac{3}{40}\right)\right). \end{align*} Taking $a>0$ to be the smaller of these two positive constants proves the claimed bound. [/step]

[step:Discretize every coordinate sphere by a fixed net]For each subset $S\subset \{1,\dots,d\}$ with $|S|=m$, define the coordinate subspace \begin{align*} E_S:=\{v\in \mathbb{R}^d:\operatorname{supp}(v)\subset S\} \end{align*} and its unit sphere \begin{align*} \mathbb{S}_S:=\{v\in E_S:|v|=1\}. \end{align*} Choose a finite set $\mathcal{N}_S\subset \mathbb{S}_S$ such that for every $v\in \mathbb{S}_S$ there exists $u\in \mathcal{N}_S$ with $|v-u|\le 1/4$, and with cardinality \begin{align*} |\mathcal{N}_S|\le 9^m. \end{align*} Such a net is obtained as follows. Since $\mathbb{S}_S$ is compact in the finite-dimensional Euclidean space $E_S$, it is totally bounded. Hence no infinite subset of $\mathbb{S}_S$ can have pairwise distances greater than $1/4$: finitely many balls of radius $1/8$ cover $\mathbb{S}_S$, and each such ball contains at most one point of a $1/4$-separated set. Choose a $1/4$-separated subset $\mathcal{N}_S\subset\mathbb{S}_S$ of maximal cardinality among all $1/4$-separated subsets; this maximum exists because the preceding bound makes the possible cardinalities a finite nonempty subset of $\mathbb{N}$. Maximality implies the covering property: if some $v\in\mathbb{S}_S$ were farther than $1/4$ from every point of $\mathcal{N}_S$, adjoining $v$ would produce a $1/4$-separated set with larger cardinality, contradicting maximality. Finally, the open balls in $E_S$ of radius $1/8$ centered at points of $\mathcal{N}_S$ are pairwise disjoint and are contained in the ball of radius $9/8$ centered at $0$, so comparing $m$-dimensional Euclidean volumes gives $|\mathcal{N}_S|(1/8)^m\le (9/8)^m$, hence $|\mathcal{N}_S|\le 9^m$.[/step]

[guided]Fix a support $S\subset\{1,\dots,d\}$ with $|S|=m$. The relevant vectors are not all of $\mathbb{R}^d$, but only the $m$-dimensional coordinate subspace \begin{align*} E_S:=\{v\in \mathbb{R}^d:\operatorname{supp}(v)\subset S\}. \end{align*} Inside this subspace we consider the unit sphere \begin{align*} \mathbb{S}_S:=\{v\in E_S:|v|=1\}. \end{align*} We need a finite replacement for $\mathbb{S}_S$. Choose $\mathcal{N}_S\subset \mathbb{S}_S$ to be a $1/4$-separated subset of maximal cardinality. Such a finite maximal-cardinality set exists because $\mathbb{S}_S$ is compact and therefore totally bounded: finitely many balls of radius $1/8$ cover $\mathbb{S}_S$, so a $1/4$-separated set has at most one point in each ball of this finite cover. Hence the set of possible cardinalities of $1/4$-separated subsets is a finite nonempty subset of $\mathbb{N}$ and has a maximum. Maximality implies covering: if some $v\in \mathbb{S}_S$ had distance greater than $1/4$ from every point of $\mathcal{N}_S$, then adding $v$ would produce a $1/4$-separated subset with larger cardinality, contradicting maximality. Thus $\mathcal{N}_S$ is a $1/4$-net. It remains to justify the size bound. The open balls in $E_S$ of radius $1/8$ centered at the points of $\mathcal{N}_S$ are pairwise disjoint. Since every center lies on the unit sphere, all these balls are contained in the ball of radius $1+1/8=9/8$ centered at $0$. Comparing $m$-dimensional Euclidean volumes in $E_S$ gives \begin{align*} |\mathcal{N}_S|\left(\frac{1}{8}\right)^m \le \left(\frac{9}{8}\right)^m, \end{align*} and hence \begin{align*} |\mathcal{N}_S|\le 9^m. \end{align*} This is the point where the dimension $m$ enters the argument: each support contributes an $m$-dimensional sphere, so the net size is exponential in $m$, not in $d$.[/guided]

[step:Apply the union bound over all supports and net points] Define the event \begin{align*} \mathcal{E}:=\left\{\left|\frac{|Xu|^2}{n}-1\right|\le \frac{1}{4} \text{ for every } S\subset\{1,\dots,d\},\ |S|=m,\text{ and every }u\in \mathcal{N}_S\right\}. \end{align*} Using the fixed-direction bound from the first step and the [union bound](/page/Union%20Bound), \begin{align*} \mathbb{P}(\mathcal{E}^c) &\le \binom{d}{m}9^m\cdot 2e^{-an}. \end{align*} The elementary [binomial coefficient estimate](/page/Binomial%20Coefficient) $\binom{d}{m}\le (ed/m)^m$ gives \begin{align*} \mathbb{P}(\mathcal{E}^c) &\le 2\exp\left(m\log\left(\frac{9ed}{m}\right)-an\right). \end{align*} Since $1\le m\le d$, we have $ed/m\ge e$, and therefore $\log(ed/m)\ge 1$. Hence \begin{align*} \log\left(\frac{9ed}{m}\right)=\log 9+\log\left(\frac{ed}{m}\right). \end{align*} Because $\log(ed/m)\ge 1$, this gives \begin{align*} \log\left(\frac{9ed}{m}\right)\le (1+\log 9)\log\left(\frac{ed}{m}\right). \end{align*} Since $1+\log 9\le 4$, we obtain \begin{align*} \log\left(\frac{9ed}{m}\right)\le 4\log\left(\frac{ed}{m}\right). \end{align*} Choose \begin{align*} C\ge \max\left\{\frac{8}{a},\frac{16\log 2}{a}\right\} \end{align*} and set $c:=a/4$. If \begin{align*} n\ge C m\log\left(\frac{ed}{m}\right), \end{align*} then $4m\log(ed/m)\le an/2$ and, since $m\log(ed/m)\ge 1$, also $2\le e^{an/4}$. Consequently \begin{align*} \mathbb{P}(\mathcal{E}^c) &\le 2e^{-an/2} \le e^{-an/4} =e^{-cn}, \end{align*} which is equivalent to \begin{align*} \mathbb{P}(\mathcal{E})\ge 1-e^{-cn}. \end{align*} [/step]

[step:Upgrade the net estimate to every sparse unit vector]Assume the event $\mathcal{E}$ holds. For a fixed support $S$ with $|S|=m$, let $P_S:\mathbb{R}^d\to E_S$ denote the coordinate projection defined by $(P_S x)_j=x_j$ for $j\in S$ and $(P_S x)_j=0$ for $j\notin S$. Define the self-adjoint [linear map](/page/Linear%20Map) $A_S:E_S\to E_S$ by $A_Sv=P_S(X^\top Xv)/n-v$ for $v\in E_S$. Let $I_m\in\mathbb{R}^{m\times m}$ denote the identity matrix. Equivalently, after identifying $E_S$ with $\mathbb{R}^m$ by the ordered coordinates in $S$, this map is represented by $X_S^\top X_S/n-I_m$, where $X_S\in\mathbb{R}^{n\times m}$ is the submatrix of $X$ formed by the columns indexed by $S$. Let \begin{align*} M_S:=\sup_{v\in \mathbb{S}_S}|(A_Sv,v)_{\mathbb{R}^d}|. \end{align*} For every $u\in \mathcal{N}_S$, the event $\mathcal{E}$ gives \begin{align*} |(A_Su,u)_{\mathbb{R}^d}|=\left|\frac{|Xu|^2}{n}-1\right|\le \frac{1}{4}. \end{align*} We record why $M_S$ controls mixed terms. Because $A_S:E_S\to E_S$ is self-adjoint on the finite-dimensional Euclidean space $E_S$, the [spectral theorem](/page/Spectral%20Theorem) gives an [orthonormal basis](/page/Orthonormal%20Basis) $e_1,\dots,e_m$ of $E_S$ and real eigenvalues $\lambda_1,\dots,\lambda_m$ such that $A_Se_k=\lambda_k e_k$. Hence \begin{align*} M_S=\max_{1\le k\le m}|\lambda_k|. \end{align*} Indeed, the inequality $|(A_Sw,w)_{\mathbb{R}^d}|\le \max_k|\lambda_k|$ follows by expanding a unit vector $w=\sum_k \alpha_k e_k$, and equality is attained by an eigenvector corresponding to an eigenvalue of maximal absolute value. Therefore, for all $x,y\in E_S$, the [Cauchy-Schwarz inequality](/page/Cauchy-Schwarz%20Inequality) in the orthonormal eigenbasis gives \begin{align*} |(A_Sx,y)_{\mathbb{R}^d}|\le M_S|x|\,|y|. \end{align*} Choose $v\in \mathbb{S}_S$ and $u\in\mathcal{N}_S$ with $|v-u|\le 1/4$. Since $A_S$ is self-adjoint on $E_S$ and $v=u+(v-u)$, \begin{align*} |(A_Sv,v)_{\mathbb{R}^d}|\le |(A_Su,u)_{\mathbb{R}^d}|+ |(A_S(v-u),v)_{\mathbb{R}^d}|+ |(A_Su,v-u)_{\mathbb{R}^d}|. \end{align*} Using the mixed-term estimate with $|u|=|v|=1$ gives \begin{align*} |(A_Sv,v)_{\mathbb{R}^d}|\le \frac{1}{4}+M_S|v-u|+M_S|v-u|\le \frac{1}{4}+\frac{1}{2}M_S. \end{align*} Taking the supremum over $v\in\mathbb{S}_S$ yields \begin{align*} M_S\le \frac{1}{4}+\frac{1}{2}M_S, \end{align*} so $M_S\le 1/2$. Therefore, for every $v\in \mathbb{S}_S$, \begin{align*} \frac{1}{2}\le \frac{|Xv|^2}{n}\le \frac{3}{2}. \end{align*}[/step]

[guided]Fix a support $S$ with $|S|=m$ and assume that the event $\mathcal{E}$ holds. The net only gives information at points $u\in\mathcal{N}_S$, so we introduce an operator whose quadratic form is exactly the error we want to control. Let $P_S:\mathbb{R}^d\to E_S$ be the coordinate projection defined by $(P_S x)_j=x_j$ for $j\in S$ and $(P_S x)_j=0$ for $j\notin S$. Define the self-adjoint linear map $A_S:E_S\to E_S$ by \begin{align*} A_Sv=\frac{P_S(X^\top Xv)}{n}-v. \end{align*} For $v\in E_S$, the identity $(P_S z,v)_{\mathbb{R}^d}=(z,v)_{\mathbb{R}^d}$ gives \begin{align*} (A_Sv,v)_{\mathbb{R}^d}=\frac{|Xv|^2}{n}-|v|^2. \end{align*} Thus bounding the quadratic form of $A_S$ on the unit sphere is exactly the same as bounding $|Xv|^2/n-1$ for $v\in\mathbb{S}_S$. Define \begin{align*} M_S:=\sup_{v\in\mathbb{S}_S}|(A_Sv,v)_{\mathbb{R}^d}|. \end{align*} For every $u\in\mathcal{N}_S$, the event $\mathcal{E}$ gives \begin{align*} |(A_Su,u)_{\mathbb{R}^d}|=\left|\frac{|Xu|^2}{n}-1\right|\le \frac{1}{4}. \end{align*} The obstacle is that after replacing $v$ by a nearby net point $u$, mixed terms involving $v-u$ appear. We control them by $M_S$ itself. Since $A_S:E_S\to E_S$ is self-adjoint on the finite-dimensional Euclidean space $E_S$, the [spectral theorem](/page/Spectral%20Theorem) gives an orthonormal basis $e_1,\dots,e_m$ of $E_S$ and real eigenvalues $\lambda_1,\dots,\lambda_m$ such that $A_Se_k=\lambda_k e_k$. For a unit vector $w=\sum_{k=1}^m\alpha_k e_k$, we have \begin{align*} (A_Sw,w)_{\mathbb{R}^d}=\sum_{k=1}^m\lambda_k\alpha_k^2, \end{align*} so \begin{align*} M_S=\max_{1\le k\le m}|\lambda_k|. \end{align*} Therefore, for all $x,y\in E_S$, the [Cauchy-Schwarz inequality](/page/Cauchy-Schwarz%20Inequality) applied in this orthonormal eigenbasis gives \begin{align*} |(A_Sx,y)_{\mathbb{R}^d}| =\left|\sum_{k=1}^m\lambda_k x_k y_k\right| \le M_S\left(\sum_{k=1}^m x_k^2\right)^{1/2}\left(\sum_{k=1}^m y_k^2\right)^{1/2} =M_S|x|\,|y|, \end{align*} where $x_k=(x,e_k)_{\mathbb{R}^d}$ and $y_k=(y,e_k)_{\mathbb{R}^d}$. Now choose $v\in\mathbb{S}_S$ and choose $u\in\mathcal{N}_S$ with $|v-u|\le 1/4$. Expanding $v=u+(v-u)$ in the quadratic form and using self-adjointness gives \begin{align*} |(A_Sv,v)_{\mathbb{R}^d}|\le |(A_Su,u)_{\mathbb{R}^d}|+ |(A_S(v-u),v)_{\mathbb{R}^d}|+ |(A_Su,v-u)_{\mathbb{R}^d}|. \end{align*} The event $\mathcal{E}$ controls the first term, and the mixed-term estimate controls the remaining two terms, so \begin{align*} |(A_Sv,v)_{\mathbb{R}^d}|\le \frac{1}{4}+M_S|v-u|\,|v|+M_S|u|\,|v-u|. \end{align*} Since $|u|=|v|=1$ and $|v-u|\le 1/4$, this gives \begin{align*} |(A_Sv,v)_{\mathbb{R}^d}|\le \frac{1}{4}+\frac{1}{2}M_S. \end{align*} Taking the supremum over $v\in\mathbb{S}_S$ gives \begin{align*} M_S\le \frac{1}{4}+\frac{1}{2}M_S, \end{align*} and hence $M_S\le 1/2$. Since $(A_Sv,v)_{\mathbb{R}^d}=|Xv|^2/n-1$ for $v\in\mathbb{S}_S$, we conclude that every $v\in\mathbb{S}_S$ satisfies \begin{align*} \frac{1}{2}\le \frac{|Xv|^2}{n}\le \frac{3}{2}. \end{align*}[/guided]

[step:Extend the bound from exact support size $m$ to support size at most $m$] Assume again that $\mathcal{E}$ holds. Let $v\in\mathbb{R}^d\setminus\{0\}$ satisfy $|\operatorname{supp}(v)|\le m$. Choose a set $S\subset\{1,\dots,d\}$ with $|S|=m$ and $\operatorname{supp}(v)\subset S$, which is possible because $m\le d$. Define $w:=v/|v|$. Then $w\in \mathbb{S}_S$, and the previous step gives \begin{align*} \frac{1}{2}\le \frac{|Xw|^2}{n}\le \frac{3}{2}. \end{align*} Since $Xv=|v|Xw$, this is equivalent to \begin{align*} \frac{1}{2}\le \frac{|Xv|^2}{n|v|^2}\le \frac{3}{2}. \end{align*} Taking the infimum over all nonzero $m$-sparse $v$ gives $\kappa_-(m;X)\ge 1/2$, and taking the supremum gives $\kappa_+(m;X)\le 3/2$. The inequality $\kappa_-(m;X)\le \kappa_+(m;X)$ follows directly from the definitions. Hence, on $\mathcal{E}$, \begin{align*} \frac{1}{2}\le \kappa_-(m;X)\le \kappa_+(m;X)\le \frac{3}{2}. \end{align*} Since $\mathbb{P}(\mathcal{E})\ge 1-e^{-cn}$, the desired probability bound follows. [/step]