Sparse maximum eigenvalue (${\kappa }_m^2$)

For a design matrix $X$ with $p$ columns, define ${\kappa }_m^2={\max }_{|M|=m}{\lambda }_{\max }(X_M^T{X}_M/n)$ for $1\le m\le p$. Equivalently this bounds $\Vert Xv{\Vert }_2^2/(n\Vert v{\Vert }_2^2)$ for vectors supported on at most $m$ coordinates. These quantities are nondecreasing: extend the support of a maximizing vector by zero coordinates and use the variational characterization of the largest eigenvalue. Values at $m>p$, including infinity, require a separate convention.

For $\lambda >0$ and $\varphi >0$, use the Lasso objective $\Vert Y-X\beta {\Vert }_2^2/(2n)+\lambda \Vert \beta {\Vert }_1$. Suppose the noise score has maximum norm at most $\lambda /2$, the true support has size $s$, and $\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2/n\le 16{\lambda }^{2}s/{\varphi }^2$. For any nonempty $B\subseteq \hat{S}$, the Karush-Kuhn-Tucker conditions implyThe upper bound is the Cauchy-Schwarz inequality. Hence $|B|\le 64{\kappa }_{|B|}^{2}s/{\varphi }^2$. A finite first index $m_{\ast }$ violating this inequality must exceed $|\hat{S}|$. Its minimality also gives $|\hat{S}|\le 64{\kappa }_{m_{\ast }}^{2}s/{\varphi }^2$. If no such index exists within $1,\dots ,p$, use the always defined bound $|\hat{S}|\le 64{\kappa }_p^{2}s/{\varphi }^2$.