Let A⊆S^p-1 and let X∈R^p be an isotropic random vector satisfying a uniform small-ball condition: there exist constants kappa,q>0 such that inf_u∈ AP(|langle X,u rangle|≥kappa)≥ q. For independent copies X_1,…,X_n and w(A)=Esup_u∈ Alangle g,u rangle, where g simN(0,I_p), does there exist a constant C=C(kappa,q) such that, whenever n≥ C bigl(1+w(A)^2+log(1/delta)bigr), one has with probability at least 1-delta the restricted-eigenvalue bound inf_u∈ Afrac1n∑_i=1^n langle X_i,u rangle^2≥ c(kappa,q)>0? Equivalently, does a uniform small-ball condition alone guarantee the Gaussian-width sample-complexity law for empirical restricted eigenvalues for arbitrary sets A?

Banerjee et al. (2015) open problem on restricted eigenvalues under heavy-tailed designs

Let $A\subseteq\mathbb{S}^{p-1}$ and let $X\in\mathbb{R}^p$ be an isotropic random vector satisfying a uniform small-ball condition: there exist constants $\kappa,q>0$ such that $\inf_{u\in A}\mathbb{P}(|\langle X,u\rangle|\geq\kappa)\geq q$ . For independent copies $X_1,\ldots,X_n$ and $w(A)=\mathbb{E}\sup_{u\in A}\langle g,u\rangle$ , where $g\sim\mathcal{N}(0,I_p)$ , does there exist a constant $C=C(\kappa,q)$ such that, whenever $n\geq C\bigl(1+w(A)^2+\log(1/\delta)\bigr)$ , one has with probability at least $1-\delta$ the restricted-eigenvalue bound $\inf_{u\in A}\frac{1}{n}\sum_{i=1}^n\langle X_i,u\rangle^2\geq c(\kappa,q)>0$ ? Equivalently, does a uniform small-ball condition alone guarantee the Gaussian-width sample-complexity law for empirical restricted eigenvalues for arbitrary sets $A$ ?

References

Primary source

arXiv

Additional references

Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails — arXiv

compressed-sensing high-dimensional-probability statistical-learning-theory

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A September 2026 preprint claims the proposed heavy-tailed scaling law is false, but the claim has not been independently verified.

Banerjee, Chen, and Sivakumar posed in 2015 whether heavy-tailed designs satisfying a small-ball condition achieve restricted-eigenvalue guarantees with the same sample complexity as sub-Gaussian designs. The question is motivated by guarantees for the Lasso and Dantzig selector.

Known results

Banerjee, Chen, and Sivakumar (2015) formulated the heavy-tailed restricted-eigenvalue question and identified Gaussian-width-squared scaling as the target behavior.

September 3, 2026 claimed counterexample

A preprint claims that constant-width polyhedral cones and isotropic heavy-tailed measurements can have empirical restricted-eigenvalue failure despite fixed small-ball constants. It proposes threshold occupancy as the missing obstruction, implying that Gaussian-width-only sample-complexity scaling does not extend to this setting; this remains unverified.

Current status (as of September 2026): The original question is not settled by verified literature; a preprint claims a negative answer through a counterexample, but independent confirmation is absent.

Sources

No solutions have been posted yet.