Small-Ball Marginals Do Not Control Restricted Eigenvalues by Euclidean Gaussian Width

Source abstract

Banerjee, Chen, and Sivakumar asked at COLT 2015 whether a uniform small-ball condition on the rows of a random design matrix forces a restricted-eigenvalue lower bound whose sample complexity is governed by the ordinary Euclidean Gaussian width of an arbitrary spherical subset. We give a negative answer to the natural distribution-free formulation of that question. For every sample size $n$, we construct a centered, genuinely heavy-tailed row distribution in dimension $p=4^n+1$ and a set $A=C\cap\mathbb{S}^{p-1}$, where $C$ is a closed polyhedral convex cone, such that $$\inf_{v\ne 0}\mathbb{P}\!\left( \left|\left\langle Z,v\right\rangle\right| \ge \frac{\left\lVert v\right\rVert_2}{\sqrt{2}} \right)\ge \frac{1}{12} \quad\text{and}\quad w(A)<2.$$ Nevertheless, for the matrix $X$ with $n$ independent copies of $Z$ as rows, $$\mathbb{P}\!\left( \inf_{u\in A}\left\lVert Xu\right\rVert_2^2=0 \right) \ge 1-\exp(-2^n).$$ Thus no positive constants depending only on the fixed small-ball parameters can yield a lower bound of the proposed form $c_1n-c_2w(A)^2$ with high probability. The construction isolates the obstruction: a marginal small-ball lower bound controls every fixed direction, but does not control the distribution-dependent complexity of searching over many directions. We state the quantifiers explicitly and discuss why isotropic or upper-tail assumptions lead to a different, still meaningful problem.