Restricted Eigenvalues Beyond Gaussian Width: Threshold Occupancy under Heavy Tails

# Restricted Eigenvalues Beyond Gaussian Width:Threshold Occupancy under Heavy Tails
Source: [https://arxiv.org/html/2609.03504](https://arxiv.org/html/2609.03504)
\\jmlrpages\\coltauthor

and and and Generative AI Lab, College of Computing and Data Science, Nanyang Technological University, Singapore

###### Abstract

Restricted eigenvalue \(RE\) bounds govern stable recovery by norm\-regularized estimators\. For isotropic sub\-Gaussian measurements, the benchmark sample size is1\+w​\(A\)21\+w\(A\)^\{2\}, wherew⁡\(A\)w\(A\)is the Gaussian width of the normalized descent cone\. The COLT 2015 open\-problem note\([Banerjee et al\., 2015](https://arxiv.org/html/2609.03504#bib.bib1)\)asked whether the same law follows for heavy\-tailed designs from a uniform small\-ball condition alone\. We give an explicit and systematic negative answer to the general question as formulated there: the proposed law fails in its full dimension\-free, arbitrary\-set form, and the missing obstruction is simultaneous threshold occupancy\. A constant\-width polyhedral descent cone with fixed small\-ball constants has zero empirical RE on every sample path up to half the ambient dimension\. More generally, every finite range space admits exact threshold encoding in an arbitrarily narrow spherical cap and a lift to a full polyhedral descent\-cone section\. For every fixed threshold VC dimensiondd, asβ↓0\\beta\\downarrow 0, the sharp worst\-case sample complexity isΘ⁡\(β−1​\[d​log⁡\(1/β\)\+log⁡\(1/δ\)\]\)\\Theta\(\\beta^\{\-1\}\[d\\log\(1/\\beta\)\+\\log\(1/\\delta\)\]\)\. The separation persists under exact isotropy and all finite moments: on the same constant\-width cone, Gaussian measurements succeed withO⁡\(1\+log⁡\(1/δ\)\)O\(1\+\\log\(1/\\delta\)\)samples, whereas an isotropic heavy\-tailed design fails pathwise forn≲p/log⁡pn\\lesssim\\sqrt\{p/\\log p\}\. Gaussian smoothing yields an everywhere\-positiveC∞C^\{\\infty\}density while retaining arbitrarily poor RE\. Under isotropy, a distribution\-free fallback governed by affine dimension times squared enclosing radius is sharp on this family\.

††proceedings:Preprint: Preprint††year:2026###### keywords

restricted eigenvalues; heavy\-tailed designs; small\-ball method; Gaussian width; VC dimension

## 1Introduction

Many high\-dimensional estimators recover a structured parameter by minimizing a norm subject to fitting the data\. The Lasso is the canonical example: theℓ1\\ell\_\{1\}norm favors sparse vectors, but it cannot distinguish the targetθ⋆\\theta^\{\\star\}from a perturbation that both preserves the measurements and does not increase the norm\. More generally, the perturbations that a regularizer cannot exclude form its*descent cone*\. Recovery is possible only when the measurement matrix is well conditioned on this cone\.

The restricted eigenvalue \(RE\) quantifies this condition\. LetX∈ℝn×pX\\in\\mathbb\{R\}^\{n\\times p\}have i\.i\.d\. rowsZ1,…,ZnZ\_\{1\},\\ldots,Z\_\{n\}with common lawPP, and letA⊆𝕊p−1A\\subseteq\\mathbb\{S\}^\{p\-1\}be the normalized set of relevant directions, typically the spherical section of a descent cone\. We write

Λn​\(X,A\)=infu∈A‖X​u‖22n=infu∈A1n​∑i=1n⟨Zi,u⟩2\.\\Lambda\_\{n\}\(X;A\)=\\inf\_\{u\\in A\}\\frac\{\\\|Xu\\\|\_\{2\}^\{2\}\}\{n\}=\\inf\_\{u\\in A\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\langle Z\_\{i\},u\\rangle^\{2\}\.\(1\)IfΛn​\(X,A\)\>0\\Lambda\_\{n\}\(X;A\)\>0, no relevant direction lies in the kernel\. A quantitative lower bound controls the sensitivity of recovery to noise and, in statistical models, the estimation error\([Bickel et al\., 2009](https://arxiv.org/html/2609.03504#bib.bib3);[Chandrasekaran et al\., 2012](https://arxiv.org/html/2609.03504#bib.bib5);[Negahban et al\., 2012](https://arxiv.org/html/2609.03504#bib.bib4)\)\.

For centered isotropic sub\-Gaussian rows, a clean geometric law holds up to distribution\-dependent constants: the benchmark sample size is controlled by1\+w​\(A\)21\+w\(A\)^\{2\}, wherew⁡\(A\)=𝔼​supu∈A⟨g,u⟩w\(A\)=\\mathbb\{E\}\\sup\_\{u\\in A\}\\langle g,u\\rangleis the Gaussian width\. Thew​\(A\)2w\(A\)^\{2\}term acts as an effective dimension of the cone, while the additive constant covers even zero\-width sets\. For Gaussian measurements, statistical\-dimension theory sharpens the picture to precise phase transitions for sparse recovery, low\-rank recovery, and many other convex inverse problems\([Gordon, 1988](https://arxiv.org/html/2609.03504#bib.bib19);[Chandrasekaran et al\., 2012](https://arxiv.org/html/2609.03504#bib.bib5);[Amelunxen et al\., 2014](https://arxiv.org/html/2609.03504#bib.bib6);[Tropp, 2015b](https://arxiv.org/html/2609.03504#bib.bib7)\)\.

Heavy\-tailed measurements motivate a different route\. Upper\-tail concentration may be unavailable, but each fixed direction may still be visible with nontrivial probability\. The small\-ball condition asks that, for someα,β\>0\\alpha,\\beta\>0,

𝖰α\(P,A\):⁣=infu∈AP\{\|⟨Z,u⟩\|≥α\}≥β\.\\mathsf\{Q\}\_\{\\alpha\}\(P,A\)\\mathrel\{:=\}\\inf\_\{u\\in A\}P\\\{\|\\langle Z,u\\rangle\|\\geq\\alpha\\\}\\geq\\beta\.\(2\)The apparent analogy hides a change in quantifiers\. The small\-ball condition says that, for every fixed directionuu, a fresh population draw detectsuuwith probability at leastβ\\beta\. An RE bound asks for more: with high probability, one common sample must detect every direction inAAsimultaneously\. Under sub\-Gaussian assumptions, increment control couples nearby directions and Gaussian width measures the remaining uniformity cost\. A bare small\-ball condition provides no such coupling\.

The COLT 2015 open problem of[Banerjee et al\. \(2015\)](https://arxiv.org/html/2609.03504#bib.bib1)asked whether, for arbitrary sphericalAA, one can nevertheless prove

infu∈A‖X​u‖22≥c1​\(α,β\)​n−c2​\(α,β\)​w​\(A\)2\\inf\_\{u\\in A\}\\\|Xu\\\|\_\{2\}^\{2\}\\geq c\_\{1\}\(\\alpha,\\beta\)n\-c\_\{2\}\(\\alpha,\\beta\)w\(A\)^\{2\}\(3\)with high probability\. We make explicit the sample\-complexity interpretation of the “suitable constants” in that question:c1\>0c\_\{1\}\>0andc2<∞c\_\{2\}<\\inftymay depend on the small\-ball parameters but not on the ambient dimension or onAA\. Without this dimension\-free uniformity, the proposed Gaussian\-width law would not express the same\-order sample\-complexity principle posed in the original note\. A positive answer would have made the Gaussian\-width phase diagram universal far beyond Gaussian designs, without upper\-tail concentration or high\-order moment assumptions\.

#### Our answer\.

We show that the dimension\-free Gaussian\-width law posed in the COLT 2015 note does not follow from a bare small\-ball condition, even when the design is exactly isotropic\. Our results identify simultaneous threshold occupancy as the general obstruction, determine its sharp worst\-case complexity, and delineate what isotropy does and does not recover\.

#### The missing information is simultaneous coverage\.

Gaussian width measures Euclidean proximity between directions, but a small\-ball hypothesis need not couple their visibility events\. Imagine many latent row types and one direction for each subset of these types\. Directionuuis visible precisely when the sampled row type belongs to its associated subset\. All directions can be placed in an arbitrarily narrow spherical cap, so their Gaussian width is tiny, while a finite sample must still hit every subset in a complicated range system\. Missing one range leaves a direction with zero empirical energy\. Thus the problem is not Gaussian\-process geometry but threshold coverage\.

#### Main contributions\.

We establish four complementary results that expose the obstruction, quantify its complexity, and identify a positive boundary\.

- •*A pathwise counterexample at constant width\.*For every evenmm, we give a polyhedral norm and a centered, directionally heavy\-tailed design withw⁡\(A\)=O⁡\(1\)w\(A\)=O\(1\)and fixed small\-ball constants, yetΛn​\(X,A\)=0\\Lambda\_\{n\}\(X;A\)=0on every sample path whenevern≤m/2n\\leq m/2\([Theorem1](https://arxiv.org/html/2609.03504#Thmtheorem1)\)\. This is a deterministic finite\-sample obstruction, not a failure event hidden in a tail bound\.
- •*Range\-space universality and the sharp low\-mass law\.*We represent every finite probability range space exactly by threshold events at arbitrarily small Gaussian width \([Theorem3](https://arxiv.org/html/2609.03504#Thmtheorem3)\), then lift missed\-range witnesses to a full polyhedral descent\-cone section while preserving uniform small\-ball mass over the cone \([Theorem4](https://arxiv.org/html/2609.03504#Thmtheorem4)\)\. Thus occupancy is intrinsic\. At threshold VC dimensiondd, uniform RE holds atn≳β−1​\{d​log⁡\(2/β\)\+log⁡\(1/δ\)\}n\\gtrsim\\beta^\{\-1\}\\\{d\\log\(2/\\beta\)\+\\log\(1/\\delta\)\\\}, and this order is necessary for every fixedddasβ↓0\\beta\\downarrow 0\([Theorem5](https://arxiv.org/html/2609.03504#Thmtheorem5)\)\. This sharp law concerns general spherical sets; the cone lift does not claim to preserve the generating range space’s VC dimension\.
- •*An isotropic and smooth separation on the same geometry\.*On one common descent cone, Gaussian measurements succeed afterO⁡\(1\+log⁡\(1/δ\)\)O\(1\+\\log\(1/\\delta\)\)samples, whereas a centered isotropic heavy\-tailed design with all moments has zero RE pathwise forn≲p/log⁡pn\\lesssim\\sqrt\{p/\\log p\}\([Theorems7](https://arxiv.org/html/2609.03504#Thmtheorem7)and[8](https://arxiv.org/html/2609.03504#Thmtheorem8)\)\. Gaussian smoothing gives a positiveC∞C^\{\\infty\}density while leaving the restricted singular value arbitrarily small \([Corollary9](https://arxiv.org/html/2609.03504#Thmtheorem9)\)\. Thus neither covariance normalization nor removing atoms restores Gaussian\-width control\.
- •*A positive boundary under isotropy\.*Isotropy yields a coarser distribution\-free guarantee: ifq⁡\(A\)q\(A\)is the affine dimension andr⁡\(A\)r\(A\)the minimum enclosing radius, thenq⁡\(A\)​r​\(A\)2q\(A\)r\(A\)^\{2\}replacesw​\(A\)2w\(A\)^\{2\}in a small\-ball RE bound \([Theorems10](https://arxiv.org/html/2609.03504#Thmtheorem10)and[11](https://arxiv.org/html/2609.03504#Thmtheorem11)\)\. The anchored\-frame family matches this scale\. This is a genuine positive consequence of isotropy, without asserting a joint minimax formula for all complexity pairs\.

#### Relation to earlier sparse\-recovery constructions\.

The spiky construction in the 2014 arXiv version of[Lecué and Mendelson \(2017b\)](https://arxiv.org/html/2609.03504#bib.bib12)predates the COLT note and can be retrospectively interpreted as a negative instance of the fully uniform Gaussian\-width implication for a particularℓ1\\ell\_\{1\}\-related sparse\-recovery geometry\. The COLT note cited that work in its discussion of unitss\-sparse directions and, after reviewing it together with the threshold\-VC approach of[Koltchinskii and Mendelson \(2015\)](https://arxiv.org/html/2609.03504#bib.bib10), nevertheless stated that the known results covered only “certain special cases ofAA” and that the problem for generalAAunder the small\-ball property remained open\([Banerjee et al\., 2015](https://arxiv.org/html/2609.03504#bib.bib1), p\. 1754\)\. Our contribution is a structural treatment of that arbitrary\-set formulation: constant\-width pathwise failure, exact encoding of arbitrary finite range spaces, the sharp occupancy law, and same\-geometry isotropic and smooth separations\.[Section7](https://arxiv.org/html/2609.03504#S7)gives the full comparison\.

#### Scope\.

Our impossibility concerns what follows uniformly from marginal small\-ball information alone\. Moment or increment assumptions and sparsity\-specific structure can couple nearby directions and thereby exclude our unrestricted encodings\. The appendices provide all constants, measurability conventions, and proofs\.

## 2Problem setup and proof ideas

LetVVbe a finite\-dimensional Euclidean space, writeS⁡\(V\)=\{v∈V:‖v‖2=1\}S\(V\)=\\\{v\\in V:\\\|v\\\|\_\{2\}=1\\\}, and letA⊆S⁡\(V\)A\\subseteq S\(V\)be nonempty\. For a normℛ\\mathcal\{R\}andθ≠0\\theta\\neq 0, set𝒟⁡\(ℛ,θ\)=\{h:ℛ⁡\(θ\+t​h\)≤ℛ⁡\(θ\)​for some​t\>0\}\\mathcal\{D\}\(\\mathcal\{R\},\\theta\)=\\\{h:\\mathcal\{R\}\(\\theta\+th\)\\leq\\mathcal\{R\}\(\\theta\)\\text\{ for some \}t\>0\\\}\. All cones below are closed and polyhedral\.

We use the fixed radial variableL=1\+eG0L=1\+e^\{G\_\{0\}\}, whereG0∼𝖭⁡\(0,1\)G\_\{0\}\\sim\\mathsf\{N\}\(0,1\)\. It has finite moments of every order but𝔼​es​L=∞\\mathbb\{E\}e^\{sL\}=\\inftyfor everys\>0s\>0\. An independent Rademacher sign centers our designs\. We call a random vector*directionally heavy\-tailed*if

𝔼​es​\|⟨Z,v⟩\|=∞for every​v≠0​and every​s\>0\.\\mathbb\{E\}e^\{s\|\\langle Z,v\\rangle\|\}=\\infty\\qquad\\text\{for every \}v\\neq 0\\text\{ and every \}s\>0\.\(4\)For range\-space encodings with possibly degenerate marginals, “heavy\-tailed radial multiplier” refers to this sameLL\.

The proof first encodes incidence in a narrow cap and then lifts it to a descent cone; isotropic negative and positive extensions complete the picture\.

#### Narrow\-cap incidence encoding\.

For a finite range space\{C1,…,CM\}\\\{C\_\{1\},\\ldots,C\_\{M\}\\\}, place eachuju\_\{j\}near one common anchor and let a row store\(𝟏\{Y∈Cj\}\)j≤M\(\\mathbf\{1\}\\\{Y\\in C\_\{j\}\\\}\)\_\{j\\leq M\}\. Then\|⟨Z,uj⟩\|≥1\|\\langle Z,u\_\{j\}\\rangle\|\\geq 1exactly whenY∈CjY\\in C\_\{j\}\. Shrinking the perturbation drives width to zero without changing these events\.

#### From finitely many directions to a descent cone\.

A finite spherical set is not yet a regularizer geometry\. Transporting the positive orthant through a narrow embedding yields a polyhedral norm whose cone directions are normalized mixtures of the generators\. Averaging preserves uniform small\-ball mass over the cone, while a missed range annihilates an extreme ray\.

#### Restoring isotropy without losing the witness\.

Start with polynomially many anchored Rademacher row types having near\-identity covariance, constant slab mass, and well\-conditioned small submatrices; whitening gives a tight frame\. After observing typesDD, normalize the residual obtained by projecting the anchor off their span\. It annihilates every observed row and stays withinO⁡\(\|D\|/p\)O\(\\sqrt\{\|D\|/p\}\)of the anchor\. A cap\-to\-cone lemma controls the full cone’s width\.

#### Why isotropy still yields a positive theorem\.

For a centered isotropic design, translateAAby a minimum enclosing centeraaand project the symmetrized process onto the linear spacespan⁡\(A−a\)\\operatorname\{span\}\(A\-a\)parallel toaff⁡\(A\)\\operatorname\{aff\}\(A\)\. Its expected supremum is at mostr⁡\(A\)​q⁡\(A\)r\(A\)\\sqrt\{q\(A\)\}, giving the dimension–radius bound\. On our family,q⁡\(A\)=pq\(A\)=pandr​\(A\)2≍k/pr\(A\)^\{2\}\\asymp k/p, matching the pathwise scalekk\.

## 3A constant\-width pathwise counterexample

The first theorem already rules out \([3](https://arxiv.org/html/2609.03504#S1.E3)\)\. Its role is to expose the coverage obstruction in an elementary form before the universal encoding\.

###### Theorem 1\(Explicit constant\-width counterexample\)\.

For every evenm≥2m\\geq 2, there are a Euclidean spaceVmV\_\{m\}of dimensionmm, a polyhedral normℛm\\mathcal\{R\}\_\{m\}, a pointθm⋆\\theta\_\{m\}^\{\\star\}, and a centered, directionally heavy\-tailedZm∈VmZ\_\{m\}\\in V\_\{m\}with lawPmP\_\{m\}\. SetAm=𝒟⁡\(ℛm,θm⋆\)∩S⁡\(Vm\)A\_\{m\}=\\mathcal\{D\}\(\\mathcal\{R\}\_\{m\},\\theta\_\{m\}^\{\\star\}\)\\cap S\(V\_\{m\}\)\. Then

𝖰1/\(2​2\)​\(Pm,Am\)≥13,w⁡\(Am\)≤2​2/π,VC⁡\(𝒯1​\(Am\)\|supp⁡Pm\)≥m2\.\\mathsf\{Q\}\_\{1/\(2\\sqrt\{2\}\)\}\(P\_\{m\},A\_\{m\}\)\\geq\\frac\{1\}\{3\},\\qquad w\(A\_\{m\}\)\\leq 2\\sqrt\{2/\\pi\},\\qquad\\operatorname\{VC\}\(\\mathcal\{T\}\_\{1\}\(A\_\{m\}\)\|\_\{\\operatorname\{supp\}P\_\{m\}\}\)\\geq\\frac\{m\}\{2\}\.\(5\)Moreover, for everyn≤m/2n\\leq m/2and every realization of the sample,

Λn​\(X,Am\)=0\.\\Lambda\_\{n\}\(X;A\_\{m\}\)=0\.\(6\)The radial lawLLis the same in every dimension\.

Here𝒯α​\(A\)=\{\{z:\|⟨z,u⟩\|≥α\}:u∈A\}\\mathcal\{T\}\_\{\\alpha\}\(A\)=\\\{\\\{z:\|\\langle z,u\\rangle\|\\geq\\alpha\\\}:u\\in A\\\}\. The construction separates an anchor coordinatettfrom a balanced perturbationyy\. Work inVm=\{\(t,y/m\):∑jyj=0\}V\_\{m\}=\\\{\(t,y/m\):\\sum\_\{j\}y\_\{j\}=0\\\}and define

Cm\\displaystyle C\_\{m\}=\{\(t,y/m\):t≥0,\|yj\|≤t\},\\displaystyle=\\\{\(t,y/m\):t\\geq 0,\\ \|y\_\{j\}\|\\leq t\\\},\(7\)ℛm​\(t,y/m\)\\displaystyle\\mathcal\{R\}\_\{m\}\(t,y/m\)=max⁡\{\|t\|,maxj⁡\|t−yj\|,maxj⁡\|t\+yj\|\}\.\\displaystyle=\\max\\\{\|t\|,\\max\_\{j\}\|t\-y\_\{j\}\|,\\max\_\{j\}\|t\+y\_\{j\}\|\\\}\.The norm makesCm=𝒟⁡\(ℛm,\(−1,0\)\)C\_\{m\}=\\mathcal\{D\}\(\\mathcal\{R\}\_\{m\},\(\-1,0\)\)\. Since‖y/m‖2≤t/m\\\|y/m\\\|\_\{2\}\\leq t/\\sqrt\{m\}, its normalized directions occupy anO\(m−1/2\)O\(m^\{\-1/2\}\)cap, explaining the constant width\. For visibility, letJJbe uniform on\[m\]\[m\]andσ\\sigmaan independent Rademacher sign, setrj=e0\+m​ej−∑ℓ=1meℓr\_\{j\}=e\_\{0\}\+me\_\{j\}\-\\sum\_\{\\ell=1\}^\{m\}e\_\{\\ell\}, and takeZm=σ​L​rJZ\_\{m\}=\\sigma Lr\_\{J\}\. Atv=\(t,y/m\)∈Cmv=\(t,y/m\)\\in C\_\{m\}, typejjhas scoret\+yjt\+y\_\{j\}\. These scores lie in\[0,2​t\]\[0,2t\]and average tott, so at leastm/3m/3are at leastt/2t/2\. Normalization gives the uniform small\-ball bound\.

For the pathwise witness, letDDbe the distinct observed types\. When\|D\|≤m/2\|D\|\\leq m/2, the assignmentssj=−1s\_\{j\}=\-1onDDextend to a balanceds∈\{−1,1\}ms\\in\\\{\-1,1\\\}^\{m\}\. Thenus∝\(1,s/m\)u\_\{s\}\\propto\(1,s/m\)belongs toAmA\_\{m\}, and every observed score vanishes because⟨rj,us⟩∝1\+sj=0\\langle r\_\{j\},u\_\{s\}\\rangle\\propto 1\+s\_\{j\}=0\. Thus one data\-dependent direction annihilates the sample\. Extending arbitrary signs on any prescribedm/2m/2types also gives shattering\.[AppendixB](https://arxiv.org/html/2609.03504#A2)supplies the norm, width, tail, and boundary calculations\.

###### Corollary 2\(Uniform failure of the Gaussian\-width law\)\.

Fix anyc1\>0c\_\{1\}\>0,0≤c2<∞0\\leq c\_\{2\}<\\infty, and integern0≥1n\_\{0\}\\geq 1\. There aren≥n0n\\geq n\_\{0\}, a spherical descent\-cone sectionAA, and a design with the fixed small\-ball constants in[Theorem1](https://arxiv.org/html/2609.03504#Thmtheorem1)for whichinfu∈A‖X​u‖22<c1​n−c2​w​\(A\)2\\inf\_\{u\\in A\}\\\|Xu\\\|\_\{2\}^\{2\}<c\_\{1\}n\-c\_\{2\}w\(A\)^\{2\}with probability one\.

Indeed, takem=2​nm=2nand thennnlarge enough\. Thus a cone that has constant complexity according to Gaussian width can require a number of heavy\-tailed measurements proportional to its ambient dimension\. The obstruction is not a rare failure of concentration\.

## 4Threshold occupancy governs the small\-ball worst case

Foru∈Au\\in A, letIα​\(u\)=\{i∈\[n\]:\|⟨Zi,u⟩\|≥α\}I\_\{\\alpha\}\(u\)=\\\{i\\in\[n\]:\|\\langle Z\_\{i\},u\\rangle\|\\geq\\alpha\\\}collect the rows thatα\\alpha\-detectuu, and writeq^n,α​\(A\)=n−1​infu∈A\|Iα​\(u\)\|\\widehat\{q\}\_\{n,\\alpha\}\(A\)=n^\{\-1\}\\inf\_\{u\\in A\}\|I\_\{\\alpha\}\(u\)\|\. Every detected row contributes at leastα2\\alpha^\{2\}to the empirical energy, so deterministically

Λn​\(X,A\)≥α2​q^n,α​\(A\)\.\\Lambda\_\{n\}\(X;A\)\\geq\\alpha^\{2\}\\widehat\{q\}\_\{n,\\alpha\}\(A\)\.\(8\)Thus uniform threshold coverage is sufficient\. It is not pointwise necessary for a fixed law—a few unusually large observations may still supply quadratic energy—but the results below give the relevant minimax converse: every finite coverage obstruction can be realized as an RE obstruction at arbitrarily small Gaussian width\.

### 4\.1Arbitrary range spaces in narrow caps and descent cones

Let\(Ω,μ,𝒞\)\(\\Omega,\\mu,\\mathscr\{C\}\)be a finite probability range space with full support, meaningΩ=supp⁡\(μ\)\\Omega=\\operatorname\{supp\}\(\\mu\), and let𝒞=\{C1,…,CM\}\\mathscr\{C\}=\\\{C\_\{1\},\\ldots,C\_\{M\}\\\}withμ⁡\(Cj\)≥β\\mu\(C\_\{j\}\)\\geq\\beta\. Its VC dimension is the largest number of row types on which all hit–miss labelings occur\. For a latent sampleY1,…,YnY\_\{1\},\\ldots,Y\_\{n\}, writeμn\(C\)=n−1∑i=1n𝟏\{Yi∈C\}\\mu\_\{n\}\(C\)=n^\{\-1\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{Y\_\{i\}\\in C\\\}\.

###### Theorem 3\(Exact range\-space representation\)\.

For everyη\>0\\eta\>0there are a centered design with the fixed heavy\-tailed radial multiplier and a finiteA=\{u1,…,uM\}⊂𝕊MA=\\\{u\_\{1\},\\ldots,u\_\{M\}\\\}\\subset\\mathbb\{S\}^\{M\}such thatw⁡\(A\)≤ηw\(A\)\\leq\\eta,𝖰1​\(P,A\)≥β\\mathsf\{Q\}\_\{1\}\(P,A\)\\geq\\beta, and, on the design support,

𝟏\{\|⟨Z,uj⟩\|≥1\}=𝟏\{Y∈Cj\}\(j∈\[M\]\)\.\\mathbf\{1\}\\\{\|\\langle Z,u\_\{j\}\\rangle\|\\geq 1\\\}=\\mathbf\{1\}\\\{Y\\in C\_\{j\}\\\}\\qquad\(j\\in\[M\]\)\.\(9\)Consequently the support\-restricted threshold class and𝒞\\mathscr\{C\}have the same VC dimension\. For every sample,

infu∈A1n​∑i=1nmin⁡\{1,⟨Zi,u⟩2\}=minj≤M⁡μn​\(Cj\),\\inf\_\{u\\in A\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\min\\\{1,\\langle Z\_\{i\},u\\rangle^\{2\}\\\}=\\min\_\{j\\leq M\}\\mu\_\{n\}\(C\_\{j\}\),\(10\)andΛn​\(X,A\)\>0\\Lambda\_\{n\}\(X;A\)\>0exactly when the latent sample hits everyCjC\_\{j\}\.

The representation is explicit\. Takeuj=\(e0\+ε​ej\)/1\+ε2u\_\{j\}=\(e\_\{0\}\+\\varepsilon e\_\{j\}\)/\\sqrt\{1\+\\varepsilon^\{2\}\}and

Z=1\+ε2εσL∑j𝟏\{Y∈Cj\}ej∈ℝM\+1\.Z=\\frac\{\\sqrt\{1\+\\varepsilon^\{2\}\}\}\{\\varepsilon\}\\,\\sigma L\\sum\_\{j\}\\mathbf\{1\}\\\{Y\\in C\_\{j\}\\\}e\_\{j\}\\in\\mathbb\{R\}^\{M\+1\}\.Then⟨Z,uj⟩=σL𝟏\{Y∈Cj\}\\langle Z,u\_\{j\}\\rangle=\\sigma L\\mathbf\{1\}\\\{Y\\in C\_\{j\}\\\}, whilew⁡\(A\)≤ε​2​log⁡\(2​M\)w\(A\)\\leq\\varepsilon\\sqrt\{2\\log\(2M\)\}\. Decreasingε\\varepsilonhides an arbitrary incidence pattern in an arbitrarily narrow cap without changing a single threshold event\. This exact identity, rather than a comparison inequality, is what makes the subsequent lower bounds lossless\.

The finite representation does not by itself establish a statement about norm\-regularized recovery\. The next theorem shows that the same missed\-range witness survives after passing to the full spherical section of a descent cone\.

###### Theorem 4\(Descent\-cone universality\)\.

For every finite range space above andη\>0\\eta\>0, there are an explicit polyhedral normℛε\\mathcal\{R\}\_\{\\varepsilon\}on anMM\-dimensional spaceVεV\_\{\\varepsilon\}, a pointθε⋆\\theta\_\{\\varepsilon\}^\{\\star\}, and a centered design with the fixed heavy\-tailed radial multiplier such that, forAε=𝒟⁡\(ℛε,θε⋆\)∩S⁡\(Vε\)A\_\{\\varepsilon\}=\\mathcal\{D\}\(\\mathcal\{R\}\_\{\\varepsilon\},\\theta\_\{\\varepsilon\}^\{\\star\}\)\\cap S\(V\_\{\\varepsilon\}\),

w⁡\(Aε\)≤η,𝖰1​\(P,Aε\)≥β2−β\.w\(A\_\{\\varepsilon\}\)\\leq\\eta,\\qquad\\mathsf\{Q\}\_\{1\}\(P,A\_\{\\varepsilon\}\)\\geq\\frac\{\\beta\}\{2\-\\beta\}\.\(11\)If a latent sample misses oneCjC\_\{j\}, thenΛn​\(X,Aε\)=0\\Lambda\_\{n\}\(X;A\_\{\\varepsilon\}\)=0\.

For intuition, the injective mapTε​a=\(𝟏⊤​a,ε​a\)T\_\{\\varepsilon\}a=\(\\mathbf\{1\}^\{\\top\}a,\\varepsilon a\)transports theℓ∞\\ell\_\{\\infty\}norm toVε=Tε​ℝMV\_\{\\varepsilon\}=T\_\{\\varepsilon\}\\mathbb\{R\}^\{M\}\. WriteΔM=\{q∈ℝ\+M:𝟏⊤​q=1\}\\Delta\_\{M\}=\\\{q\\in\\mathbb\{R\}\_\{\+\}^\{M\}:\\mathbf\{1\}^\{\\top\}q=1\\\}for the probability simplex\. Atθε⋆=−Tε​𝟏\\theta\_\{\\varepsilon\}^\{\\star\}=\-T\_\{\\varepsilon\}\\mathbf\{1\},

𝒟⁡\(ℛε,θε⋆\)=Tε​ℝ\+M,u⁡\(q\)=e0\+ε​q1\+ε2​‖q‖22,q∈ΔM\.\\mathcal\{D\}\(\\mathcal\{R\}\_\{\\varepsilon\},\\theta\_\{\\varepsilon\}^\{\\star\}\)=T\_\{\\varepsilon\}\\mathbb\{R\}\_\{\+\}^\{M\},\\qquad u\(q\)=\\frac\{e\_\{0\}\+\\varepsilon q\}\{\\sqrt\{1\+\\varepsilon^\{2\}\\\|q\\\|\_\{2\}^\{2\}\}\},\\quad q\\in\\Delta\_\{M\}\.\(12\)Iffq\(Y\)=∑jqj𝟏\{Y∈Cj\}f\_\{q\}\(Y\)=\\sum\_\{j\}q\_\{j\}\\mathbf\{1\}\\\{Y\\in C\_\{j\}\\\}, then0≤fq≤10\\leq f\_\{q\}\\leq 1and𝔼​fq≥β\\mathbb\{E\}f\_\{q\}\\geq\\beta, soP\{fq≥β/2\}≥β/\(2−β\)P\\\{f\_\{q\}\\geq\\beta/2\\\}\\geq\\beta/\(2\-\\beta\)\. The scaling ofZZturns this event into the threshold at one\. A missedCjC\_\{j\}annihilates the generatoru⁡\(ej\)u\(e\_\{j\}\), while a direct Gaussian calculation controls the full cone width\. See[AppendixD](https://arxiv.org/html/2609.03504#A4)\.

The obstruction is therefore not tied to one specially chosen cone: arbitrarily narrow Euclidean geometry can hide any finite combinatorial visibility pattern\.

### 4\.2The VC envelope and its sharp low\-mass regime

For a given lawPP, callAA*pointwise measurable*when\{𝟏C\|supp⁡P:C∈𝒯1​\(A\)\}\\\{\\mathbf\{1\}\_\{C\}\|\_\{\\operatorname\{supp\}P\}:C\\in\\mathcal\{T\}\_\{1\}\(A\)\\\}has a countable subclass whose pointwise sequential closure contains the whole class\. Let𝖭RE​\(d,β,δ\)\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\(d,\\beta,\\delta\)be the least integernnsuch that, for everyN≥nN\\geq n, every pointwise\-measurable spherical setAAin a finite\-dimensional Euclidean space, and every design satisfying𝖰1​\(P,A\)≥β\\mathsf\{Q\}\_\{1\}\(P,A\)\\geq\\betaandVC⁡\(𝒯1​\(A\)\|supp⁡P\)≤d\\operatorname\{VC\}\(\\mathcal\{T\}\_\{1\}\(A\)\|\_\{\\operatorname\{supp\}P\}\)\\leq d, one hasΛN​\(X,A\)≥β/2\\Lambda\_\{N\}\(X;A\)\\geq\\beta/2with probability at least1−δ1\-\\delta\. The requirement is marginal for eachNN\. No event simultaneous over allNNis asserted\.

###### Theorem 5\(VC envelope and sharp fixed\-ddlow\-mass law\)\.

There are universalc,C\>0c,C\>0such that, for every integerd≥1d\\geq 1and0<β,δ≤1/40<\\beta,\\delta\\leq 1/4,

c​d\+log⁡\(2/β\)\+log⁡\(1/δ\)β≤𝖭RE​\(d,β,δ\)≤C​d​log⁡\(2/β\)\+log⁡\(1/δ\)β\.c\\,\\frac\{d\+\\log\(2/\\beta\)\+\\log\(1/\\delta\)\}\{\\beta\}\\leq\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\(d,\\beta,\\delta\)\\leq C\\,\\frac\{d\\log\(2/\\beta\)\+\\log\(1/\\delta\)\}\{\\beta\}\.\(13\)Moreover, for every fixedd≥1d\\geq 1there isβd\>0\\beta\_\{d\}\>0such that, whenever0<β≤βd0<\\beta\\leq\\beta\_\{d\},

𝖭RE​\(d,β,δ\)≥c​d​log⁡\(2/β\)\+log⁡\(1/δ\)β\.\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\(d,\\beta,\\delta\)\\geq c\\,\\frac\{d\\log\(2/\\beta\)\+\\log\(1/\\delta\)\}\{\\beta\}\.\(14\)Thus the upper bound is optimal up to universal multiplicative constants in the low\-mass regime for each fixed VC dimension\.

The upper bound is a constant\-relative\-error VC approximation followed by \([8](https://arxiv.org/html/2609.03504#S4.E8)\)\. The general lower envelope combines three transparent mechanisms: alldd\-subsets of a uniform ground set gived/βd/\\beta, disjoint singleton ranges giveβ−1​log⁡\(1/β\)\\beta^\{\-1\}\\log\(1/\\beta\)already at VC dimension one, and one range of massβ\\betagivesβ−1​log⁡\(1/δ\)\\beta^\{\-1\}\\log\(1/\\delta\)\. The fixed\-ddproduct term follows from the sharpε\\varepsilon\-net lower bound of[Komlós et al\. \(1992\)](https://arxiv.org/html/2609.03504#bib.bib21)\.[Pach and Tardos \(2013\)](https://arxiv.org/html/2609.03504#bib.bib22)exhibit the logarithm even for geometric VC\-two systems\.[AppendixE](https://arxiv.org/html/2609.03504#A5)states the needed consequence of the external result and proves every reduction\. The classical range\-space inequalities are not new\. Their exact realization as arbitrarily narrow\-width RE problems is the new structural statement\.

## 5Isotropy does not restore Gaussian width

The preceding encodings use unconstrained row magnitudes\. One might therefore hope that exact covariance normalization reconnects Euclidean proximity with common visibility\. The following construction shows that this hope is false\.

###### Lemma 6\(Anchored tight frame\)\.

There are absolutea0,b0,c0,c1,C1\>0a\_\{0\},b\_\{0\},c\_\{0\},c\_\{1\},C\_\{1\}\>0such that, for all sufficiently largeppandM=p4M=p^\{4\}, vectorsb1,…,bM∈ℝpb\_\{1\},\\ldots,b\_\{M\}\\in\\mathbb\{R\}^\{p\}and a unitu⋆u\_\{\\star\}exist with

1M​∑jbj​bj⊤=Ip,⟨bj,u⋆⟩=1,1M​\|\{j:\|⟨bj,v⟩\|≥a0\}\|≥b0\\frac\{1\}\{M\}\\sum\_\{j\}b\_\{j\}b\_\{j\}^\{\\top\}=I\_\{p\},\\qquad\\langle b\_\{j\},u\_\{\\star\}\\rangle=1,\\qquad\\frac\{1\}\{M\}\|\\\{j:\|\\langle b\_\{j\},v\\rangle\|\\geq a\_\{0\}\\\}\|\\geq b\_\{0\}\(15\)for every unitvv\. IfBDB\_\{D\}has rowsbj⊤b\_\{j\}^\{\\top\}, then, whenever\|D\|≤c0​p/log⁡p\|D\|\\leq c\_\{0\}p/\\log p,

c1​p​I\|D\|⪯BD​BD⊤⪯C1​p​I\|D\|\.c\_\{1\}pI\_\{\|D\|\}\\preceq B\_\{D\}B\_\{D\}^\{\\top\}\\preceq C\_\{1\}pI\_\{\|D\|\}\.\(16\)

Start fromaj=\(1,ξj\)a\_\{j\}=\(1,\\xi\_\{j\}\)with independent Rademacher vectorsξj∈\{−1,1\}p−1\\xi\_\{j\}\\in\\\{\-1,1\\\}^\{p\-1\}\. Their empirical covariance is close to identity\. A uniform slab law gives global small\-ball mass, while a net argument and a union bound make every small row submatrix well conditioned\. Whitening then yields the exact tight frame without losing the common anchor\.[AppendixF](https://arxiv.org/html/2609.03504#A6)records the probability budget and the net\-to\-operator step\.

ForD⊆\[M\]D\\subseteq\[M\]with\|D\|≤c0​p/log⁡p\|D\|\\leq c\_\{0\}p/\\log p, letPDP\_\{D\}project ontospan⁡\{bj:j∈D\}\\operatorname\{span\}\\\{b\_\{j\}:j\\in D\\\}, withP∅=0P\_\{\\varnothing\}=0, and setuD=\(I−PD\)​u⋆/‖\(I−PD\)​u⋆‖2u\_\{D\}=\(I\-P\_\{D\}\)u\_\{\\star\}/\\\|\(I\-P\_\{D\}\)u\_\{\\star\}\\\|\_\{2\}\. The Gram bound gives‖uD−u⋆‖22≍\|D\|/p\\\|u\_\{D\}\-u\_\{\\star\}\\\|\_\{2\}^\{2\}\\asymp\|D\|/pandBD​uD=0B\_\{D\}u\_\{D\}=0\. DefineCp,k=cone⁡\{uD:\|D\|≤k\}C\_\{p,k\}=\\operatorname\{cone\}\\\{u\_\{D\}:\|D\|\\leq k\\\}andAp,k=Cp,k∩𝕊p−1A\_\{p,k\}=C\_\{p,k\}\\cap\\mathbb\{S\}^\{p\-1\}\.

###### Theorem 7\(Isotropic heavy\-tail separation\)\.

There are absolutec,C,α0,β0\>0c,C,\\alpha\_\{0\},\\beta\_\{0\}\>0such that, for largeppand1≤k≤c​p/log⁡p1\\leq k\\leq cp/\\log p, the following statements hold\.

1. \(i\)Ap,kA\_\{p,k\}is the spherical section of a polyhedral norm descent cone and w⁡\(Ap,k\)≤C⁡\(k​log⁡pp\+kp\)\.w\(A\_\{p,k\}\)\\leq C\\left\(k\\sqrt\{\\frac\{\\log p\}\{p\}\}\+\\frac\{k\}\{\\sqrt\{p\}\}\\right\)\.\(17\)
2. \(ii\)There are centered isotropic lawsP𝖧P\_\{\\mathsf\{H\}\}andP𝖦=𝖭⁡\(0,Ip\)P\_\{\\mathsf\{G\}\}=\\mathsf\{N\}\(0,I\_\{p\}\)with common absolute small\-ball constants infv∈𝕊p−1Ps\{\|⟨Z,v⟩\|≥α0\}≥β0,s∈\{𝖧,𝖦\}\.\\inf\_\{v\\in\\mathbb\{S\}^\{p\-1\}\}P\_\{s\}\\\{\|\\langle Z,v\\rangle\|\\geq\\alpha\_\{0\}\\\}\\geq\\beta\_\{0\},\\qquad s\\in\\\{\\mathsf\{H\},\\mathsf\{G\}\\\}\.\(18\)The lawP𝖧P\_\{\\mathsf\{H\}\}has finite moments of every order and no positive exponential moment in any nonzero marginal, yetΛn​\(X𝖧,Ap,k\)=0\\Lambda\_\{n\}\(X\_\{\\mathsf\{H\}\};A\_\{p,k\}\)=0on every sample path for everyn≤kn\\leq k\.
3. \(iii\)UnderP𝖦P\_\{\\mathsf\{G\}\}, for everyt\>0t\>0, with probability at least1−e−t2/21\-e^\{\-t^\{2\}/2\}, infu∈Ap,k‖X𝖦​u‖2≥n−1−w⁡\(Ap,k\)−t\.\\inf\_\{u\\in A\_\{p,k\}\}\\\|X\_\{\\mathsf\{G\}\}u\\\|\_\{2\}\\geq\\sqrt\{n\-1\}\-w\(A\_\{p,k\}\)\-t\.\(19\)

The heavy\-tailed law isZ𝖧=σ​ρ​bJZ\_\{\\mathsf\{H\}\}=\\sigma\\rho b\_\{J\}, whereJJis uniform on\[M\]\[M\]andρ=L/𝔼​L2\\rho=L/\\sqrt\{\\mathbb\{E\}L^\{2\}\}\. Tightness gives isotropy and the slab law gives global small\-ball\. Given a sample, the setDDof distinct row types has size at mostnn, anduDu\_\{D\}annihilates every row\. Conversely, \([19](https://arxiv.org/html/2609.03504#S5.E19)\) is Gordon’s escape theorem\. The cap\-to\-cone argument gives \([17](https://arxiv.org/html/2609.03504#S5.E17)\) for the full cone rather than only its generators\. The complete proof is in[AppendixG](https://arxiv.org/html/2609.03504#A7)\.

###### Corollary 8\(Constant\-width separation on one descent cone\)\.

Universal constants can be chosen so that the following holds\. For every sufficiently largepp, there is a descent\-cone sectionAp⊂𝕊p−1A\_\{p\}\\subset\\mathbb\{S\}^\{p\-1\}withw⁡\(Ap\)≤CGw\(A\_\{p\}\)\\leq C\_\{G\}and two centered isotropic designs with common absolute small\-ball constants\. For every0<δ<10<\\delta<1, Gaussian measurements satisfyΛn​\(X𝖦,Ap\)≥cG\\Lambda\_\{n\}\(X\_\{\\mathsf\{G\}\};A\_\{p\}\)\\geq c\_\{G\}with probability at least1−δ1\-\\deltawhenevern≥CG​\(1\+log⁡\(1/δ\)\)n\\geq C\_\{G\}\(1\+\\log\(1/\\delta\)\), whereas the heavy\-tailed design hasΛn​\(X𝖧,Ap\)=0\\Lambda\_\{n\}\(X\_\{\\mathsf\{H\}\};A\_\{p\}\)=0on every sample path for everyn≤cH​p/log⁡pn\\leq c\_\{H\}\\sqrt\{p/\\log p\}\.

Choosek=⌊a​p/log⁡p⌋k=\\lfloor a\\sqrt\{p/\\log p\}\\rfloorwith the sufficiently small universal constanta\>0a\>0fixed in[AppendixG](https://arxiv.org/html/2609.03504#A7)\. The two designs have the same covariance and the same marginal small\-ball constants\. What differs is how visibility events are coupled across directions\. Alternatively,k=⌊p1/3⌋k=\\lfloor p^\{1/3\}\\rfloorgivesw⁡\(Ap,k\)→0w\(A\_\{p,k\}\)\\to 0while the deterministic failure horizon diverges\.

### 5\.1Smooth\-density robustness

The isotropic counterexample above is discrete in its row type\. To show that the obstruction is not caused by atoms, smooth it with an independent Gaussian\. ForH∼𝖭⁡\(0,Ip\)H\\sim\\mathsf\{N\}\(0,I\_\{p\}\)andτ\>0\\tau\>0, set

Z𝖧,τ=Z𝖧\+τ​H1\+τ2\.Z\_\{\\mathsf\{H\},\\tau\}=\\frac\{Z\_\{\\mathsf\{H\}\}\+\\tau H\}\{\\sqrt\{1\+\\tau^\{2\}\}\}\.\(20\)The normalization preserves isotropy, while Gaussian convolution gives an everywhere\-positiveC∞C^\{\\infty\}density\. Smoothing removes the exact kernel, but the next result shows that the restricted energy remains of orderτ2\\tau^\{2\}\.

###### Corollary 9\(Smooth isotropic robustness\)\.

Under the construction of[Theorem7](https://arxiv.org/html/2609.03504#Thmtheorem7), there are absoluteτ0,α¯,β¯,cs\>0\\tau\_\{0\},\\bar\{\\alpha\},\\bar\{\\beta\},c\_\{s\}\>0such that, for every sufficiently largepp, every admissible1≤k≤c​p/log⁡p1\\leq k\\leq cp/\\log p, and every0<τ≤τ00<\\tau\\leq\\tau\_\{0\}, the law ofZ𝖧,τZ\_\{\\mathsf\{H\},\\tau\}is centered and isotropic, has finite moments of every order and no exponential moment in any nonzero direction, has an everywhere\-positiveC∞C^\{\\infty\}density onℝp\\mathbb\{R\}^\{p\}, and satisfies the global small\-ball condition\(α¯,β¯\)\(\\bar\{\\alpha\},\\bar\{\\beta\}\)\. For each fixed integer1≤n≤k1\\leq n\\leq k,

ℙ\{Λn\(X𝖧,τ;Ap,k\)≤2τ2\}≥1−e−cs​n\.\\mathbb\{P\}\\\{\\Lambda\_\{n\}\(X\_\{\\mathsf\{H\},\\tau\};A\_\{p,k\}\)\\leq 2\\tau^\{2\}\\\}\\geq 1\-e^\{\-c\_\{s\}n\}\.\(21\)

Conditionally on the row types, the adaptive witnessuDu\_\{D\}is independent of the Gaussian perturbations, and its normalized empirical energy is\(τ2/\(1\+τ2\)\)​\(χn2/n\)\(\\tau^\{2\}/\(1\+\\tau^\{2\}\)\)\(\\chi\_\{n\}^\{2\}/n\)\. A standard chi\-square bound gives the stated probability\. The witness is no longer an exact kernel direction, butΛn\\sqrt\{\\Lambda\_\{n\}\}can be arbitrarily small while the small\-ball constants stay fixed\.

### 5\.2A distribution\-free isotropic fallback

For bounded nonemptyAA, letr⁡\(A\)=infasupu∈A‖u−a‖2r\(A\)=\\inf\_\{a\}\\sup\_\{u\\in A\}\\\|u\-a\\\|\_\{2\}andq⁡\(A\)=dimaff⁡\(A\)q\(A\)=\\dim\\operatorname\{aff\}\(A\)\.

###### Theorem 10\(Dimension–radius RE bound\)\.

LetZZbe centered and isotropic and let∅≠A⊆𝕊p−1\\varnothing\\neq A\\subseteq\\mathbb\{S\}^\{p\-1\}\. Suppose𝖰α​\(P,A\)≥β\\mathsf\{Q\}\_\{\\alpha\}\(P,A\)\\geq\\betafor someα\>0\\alpha\>0and0<β≤10<\\beta\\leq 1\. For everyt\>0t\>0, with probability at least1−e−t2/21\-e^\{\-t^\{2\}/2\},

infu∈A‖X​u‖2≥α​β2​n−2​r​\(A\)​q⁡\(A\)−α​t2\.\\inf\_\{u\\in A\}\\\|Xu\\\|\_\{2\}\\geq\\frac\{\\alpha\\beta\}\{2\}\\sqrt\{n\}\-2r\(A\)\\sqrt\{q\(A\)\}\-\\frac\{\\alpha t\}\{2\}\.\(22\)

###### Corollary 11\(Sample\-complexity consequence\)\.

Under the assumptions of[Theorem10](https://arxiv.org/html/2609.03504#Thmtheorem10), for every0<δ<10<\\delta<1there is a universalCCsuch that

n≥C⁡\(q⁡\(A\)​r​\(A\)2α2​β2\+log⁡\(1/δ\)β2\)⟹Λn​\(X,A\)≥α2​β216n\\geq C\\left\(\\frac\{q\(A\)r\(A\)^\{2\}\}\{\\alpha^\{2\}\\beta^\{2\}\}\+\\frac\{\\log\(1/\\delta\)\}\{\\beta^\{2\}\}\\right\)\\quad\\Longrightarrow\\quad\\Lambda\_\{n\}\(X;A\)\\geq\\frac\{\\alpha^\{2\}\\beta^\{2\}\}\{16\}\(23\)with probability at least1−δ1\-\\delta\.

The proof of[Theorem10](https://arxiv.org/html/2609.03504#Thmtheorem10)is short\. ForHn=n−1/2∑iεiZiH\_\{n\}=n^\{\-1/2\}\\sum\_\{i\}\\varepsilon\_\{i\}Z\_\{i\}, translate by a minimum enclosing centeraaand project ontoL=span⁡\(A−a\)L=\\operatorname\{span\}\(A\-a\)\. Isotropy gives

𝔼​supu∈A⟨Hn,u⟩≤r⁡\(A\)​𝔼​‖PL​Hn‖2≤r⁡\(A\)​q⁡\(A\)\.\\mathbb\{E\}\\sup\_\{u\\in A\}\\langle H\_\{n\},u\\rangle\\leq r\(A\)\\mathbb\{E\}\\\|P\_\{L\}H\_\{n\}\\\|\_\{2\}\\leq r\(A\)\\sqrt\{q\(A\)\}\.\(24\)Substitution into the empirical small\-ball inequality proves \([22](https://arxiv.org/html/2609.03504#S5.E22)\)\. ForAp,kA\_\{p,k\},[AppendixG](https://arxiv.org/html/2609.03504#A7)provesq⁡\(Ap,k\)=pq\(A\_\{p,k\}\)=pandr​\(Ap,k\)2≍k/pr\(A\_\{p,k\}\)^\{2\}\\asymp k/p\. At fixed confidence and fixed small\-ball constants, the worst\-case sample complexity on this family is thereforeΘ⁡\(k\)\\Theta\(k\)\. This is a family\-wise sharpness statement, not a joint minimax characterization for every prescribed pair of threshold and radius complexities\. Thus isotropy does not recover Gaussian width, but it prevents arbitrarily bad behavior once the set is controlled by its affine dimension and enclosing radius\.

## 6Consequences and scope

Our polyhedral descent\-cone sections are closed, so their spherical sections are compact\. WheneverΛn​\(X,A\)=0\\Lambda\_\{n\}\(X;A\)=0, the minimum is attained by someu∈A∩ker⁡Xu\\in A\\cap\\ker X\. Consequently the noiseless program

minθ⁡ℛ⁡\(θ\)subject toX​θ=X​θ⋆\\min\_\{\\theta\}\\mathcal\{R\}\(\\theta\)\\quad\\text\{subject to\}\\quad X\\theta=X\\theta^\{\\star\}\(25\)does not uniquely recoverθ⋆\\theta^\{\\star\}\. The explicit and isotropic counterexamples therefore translate directly into failure of norm\-regularized recovery\.

For the smoothed construction, writeκn​\(X,A\)=Λn​\(X,A\)\\kappa\_\{n\}\(X;A\)=\\sqrt\{\\Lambda\_\{n\}\(X;A\)\}for the normalized restricted singular value and define the realized\-design inverse modulusKn​\(X,A\)=1/κn​\(X,A\)K\_\{n\}\(X;A\)=1/\\kappa\_\{n\}\(X;A\), withKn=∞K\_\{n\}=\\inftywhenκn=0\\kappa\_\{n\}=0\. On the event in[Corollary9](https://arxiv.org/html/2609.03504#Thmtheorem9),Kn≥1/\(2​τ\)K\_\{n\}\\geq 1/\(\\sqrt\{2\}\\tau\)and the corresponding quadratic modulus1/Λn1/\\Lambda\_\{n\}is at least1/\(2​τ2\)1/\(2\\tau^\{2\}\)\. This is a deterministic conditioning statement for each realized design; its witness may depend onXX, so it is not a two\-fixed\-parameter statistical minimax claim\. The obstruction is nevertheless relevant to noisy recovery, not only exact interpolation\.

The two positive mechanisms in the paper are complementary\. Relative threshold occupancy is distribution\-adapted and requires no moments\. The dimension–radius bound is Euclidean but uses isotropy\. Stronger increment or moment assumptions can recover finer chaining and, in suitable models, Gaussian\-width behavior\. We do not claim that threshold VC complexity and dimension–radius complexity form a joint minimax formula for every distribution class\.

## 7Related work

#### Restricted eigenvalues and Gaussian geometry\.

RE theory underpins the Lasso, Dantzig selector, and decomposable regularizers\([Bickel et al\., 2009](https://arxiv.org/html/2609.03504#bib.bib3);[Negahban et al\., 2012](https://arxiv.org/html/2609.03504#bib.bib4)\)\. For Gaussian measurements, escape through a mesh, Gaussian width, and statistical dimension connect descent cones to sharp recovery transitions\([Gordon, 1988](https://arxiv.org/html/2609.03504#bib.bib19);[Chandrasekaran et al\., 2012](https://arxiv.org/html/2609.03504#bib.bib5);[Amelunxen et al\., 2014](https://arxiv.org/html/2609.03504#bib.bib6);[Tropp, 2015b](https://arxiv.org/html/2609.03504#bib.bib7)\)\. Related bounds cover sub\-Gaussian, correlated, anisotropic, and stable\-rank models\([Banerjee et al\., 2014](https://arxiv.org/html/2609.03504#bib.bib2);[Raskutti et al\., 2010](https://arxiv.org/html/2609.03504#bib.bib16);[Rudelson and Zhou, 2013](https://arxiv.org/html/2609.03504#bib.bib17);[Kasiviswanathan and Rudelson, 2018](https://arxiv.org/html/2609.03504#bib.bib33)\); broader universality laws still require entry or tail structure beyond marginal visibility\([Oymak and Tropp, 2018](https://arxiv.org/html/2609.03504#bib.bib30)\)\. All constrain the joint process indexed byAA\.

#### Small\-ball methods and distribution\-dependent complexity\.

The small\-ball method lower\-bounds nonnegative empirical processes without upper\-tail concentration\([Koltchinskii and Mendelson, 2015](https://arxiv.org/html/2609.03504#bib.bib10);[Mendelson, 2015](https://arxiv.org/html/2609.03504#bib.bib9);[Tropp, 2015b](https://arxiv.org/html/2609.03504#bib.bib7)\)\. Its distribution\-dependent Rademacher or localized complexities become quadratic and multiplier fixed points in regularized estimation\([Lecué and Mendelson, 2018](https://arxiv.org/html/2609.03504#bib.bib15);[Lecué and Mendelson, 2017a](https://arxiv.org/html/2609.03504#bib.bib29)\)\. Extensions relax uniform small\-ball assumptions\([Mendelson, 2021](https://arxiv.org/html/2609.03504#bib.bib32)\), and moment\-based covariance bounds offer another route\([Oliveira, 2016](https://arxiv.org/html/2609.03504#bib.bib11)\)\. These retain information absent from ordinary Gaussian width\.

#### Positive results under stronger tail assumptions\.

Weak coordinate moments can suffice for sparse recovery\([Lecué and Mendelson, 2017b](https://arxiv.org/html/2609.03504#bib.bib12);[Dirksen et al\., 2018](https://arxiv.org/html/2609.03504#bib.bib13)\)\. Under a uniformψ1\\psi\_\{1\}assumption,[Sivakumar et al\. \(2015\)](https://arxiv.org/html/2609.03504#bib.bib18)use exponential width and threshold VC dimension at scalen≳d/β2n\\gtrsim d/\\beta^\{2\}\. Sub\-Weibull bounds\([Kuchibhotla and Chakrabortty, 2022](https://arxiv.org/html/2609.03504#bib.bib31)\), mixed\-tail chaining\([Dirksen, 2015](https://arxiv.org/html/2609.03504#bib.bib25);[Genzel and Kipp, 2022](https://arxiv.org/html/2609.03504#bib.bib26)\), and thresholding\([Wei, 2018](https://arxiv.org/html/2609.03504#bib.bib34)\)likewise add coupling or robustness that excludes our encoding\.

#### Earlier sparse\-recovery results and the 2015 open problem\.

First circulated in 2014, the spiky construction of[Lecué and Mendelson \(2017b\)](https://arxiv.org/html/2609.03504#bib.bib12)has centered isotropic rows with bounded fourth moments and hence a uniform small\-ball condition\. For anℓ1\\ell\_\{1\}\-related sparse\-recovery geometry, it can force the relevant RE and compatibility quantities to vanish with constant probability whenn​log⁡n≲pn\\log n\\lesssim p; the companion note\([Lecué and Mendelson, 2014](https://arxiv.org/html/2609.03504#bib.bib14)\)records a basis\-pursuit failure\. Thus this construction already gives a special\-case counterexample to a fully uniform implication from marginal small\-ball behavior to Gaussian\-width\-controlled RE\. The COLT note cited Lecué–Mendelson in its discussion of unitss\-sparse directions and the Koltchinskii–Mendelson threshold\-VC method, but explicitly characterized the available results as covering only “certain special cases ofAA” and left the question for generalA⊆𝕊p−1A\\subseteq\\mathbb\{S\}^\{p\-1\}under the small\-ball property open\([Banerjee et al\., 2015](https://arxiv.org/html/2609.03504#bib.bib1), p\. 1754\)\. Our results go beyond that geometry\-specific instance by establishing constant\-width pathwise failure, exact realization of arbitrary finite threshold systems, descent\-cone universality, the sharp fixed\-ddoccupancy law, and same\-geometry isotropic and smooth separations\.

#### Threshold classes and range spaces\.

The COLT note highlighted VC\-controlled threshold bounds\([Koltchinskii and Mendelson, 2015](https://arxiv.org/html/2609.03504#bib.bib10);[Banerjee et al\., 2015](https://arxiv.org/html/2609.03504#bib.bib1)\)\. Classical randomε\\varepsilon\-nets and relative approximations depend on VC dimension\([Haussler and Welzl, 1987](https://arxiv.org/html/2609.03504#bib.bib20);[Li et al\., 2001](https://arxiv.org/html/2609.03504#bib.bib23);[Har\-Peled and Sharir, 2011](https://arxiv.org/html/2609.03504#bib.bib24)\);[Komlós et al\. \(1992\)](https://arxiv.org/html/2609.03504#bib.bib21)prove the logarithmic lower bound, and[Pach and Tardos \(2013\)](https://arxiv.org/html/2609.03504#bib.bib22)give a geometric VC\-two construction\. Those inequalities are not new here\. Our contribution is their exact realization on arbitrarily narrow spherical sets and a descent\-cone lift turning every missed range into a kernel witness\.

## 8Conclusion

We show that the Gaussian\-width principle posed in the COLT 2015 open\-problem note does not follow from a uniform small\-ball condition: it can fail pathwise on a constant\-width descent cone\. Empirical RE requires one sample to cover all relevant directions, whereas bare small\-ball visibility is only pointwise\. Gaussian and sub\-Gaussian increment control couples nearby directions, but a marginal small\-ball condition does not\. Encoding arbitrary threshold range spaces in narrow spherical caps yields pathwise counterexamples and the sharp low\-mass law at each fixed threshold VC dimension\. The separation survives isotropy, moments of every order, and positive smooth densities, while isotropy still gives a sharp dimension–radius fallback\. A natural next question is which minimal structure between marginal visibility and full increment control restores a Gaussian\-width law\.

## References

- Amelunxenet al\.\(2014\)D\. Amelunxen, M\. Lotz, M\. B\. McCoy, and J\. A\. TroppLiving on the edge: phase transitions in convex programs with random data\.Information and Inference3\(3\),pp\. 224–294\.Cited by:[§1](https://arxiv.org/html/2609.03504#S1.p3.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Banerjeeet al\.\(2014\)A\. Banerjee, S\. Chen, F\. Fazayeli, and V\. SivakumarEstimation with norm regularization\.InAdvances in Neural Information Processing Systems 27,pp\. 1556–1564\.Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Banerjeeet al\.\(2015\)A\. Banerjee, S\. Chen, and V\. SivakumarOpen problem: restricted eigenvalue condition for heavy tailed designs\.InProceedings of the 28th Conference on Learning Theory,P\. Grünwald, E\. Hazan, and S\. Kale \(Eds\.\),Proceedings of Machine Learning Research, Vol\.40,Paris, France,pp\. 1752–1755\.External Links:[Link](https://proceedings.mlr.press/v40/Banerjee15.html)Cited by:[§1](https://arxiv.org/html/2609.03504#S1.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2609.03504#S1.p5.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px4.p1.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px5.p1.1),[Abstract](https://arxiv.org/html/2609.03504#abstract1.1)\.
- Bickelet al\.\(2009\)P\. J\. Bickel, Y\. Ritov, and A\. B\. TsybakovSimultaneous analysis of lasso and dantzig selector\.The Annals of Statistics37\(4\),pp\. 1705–1732\.Cited by:[§1](https://arxiv.org/html/2609.03504#S1.p2.2),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Boucheronet al\.\(2013\)S\. Boucheron, G\. Lugosi, and P\. MassartConcentration inequalities: a nonasymptotic theory of independence\.Oxford University Press\.Cited by:[§F\.2](https://arxiv.org/html/2609.03504#A6.SS2.p1.5)\.
- Chandrasekaranet al\.\(2012\)V\. Chandrasekaran, B\. Recht, P\. A\. Parrilo, and A\. S\. WillskyThe convex geometry of linear inverse problems\.Foundations of Computational Mathematics12\(6\),pp\. 805–849\.Cited by:[§1](https://arxiv.org/html/2609.03504#S1.p2.2),[§1](https://arxiv.org/html/2609.03504#S1.p3.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Dirksenet al\.\(2018\)S\. Dirksen, G\. Lecué, and H\. RauhutOn the gap between restricted isometry properties and sparse recovery conditions\.IEEE Transactions on Information Theory64\(8\),pp\. 5478–5487\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2016.2570244),1504\.05073Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px3.p1.1)\.
- Dirksen \(2015\)S\. DirksenTail bounds via generic chaining\.Electronic Journal of Probability20\(53\),pp\. 1–29\.External Links:[Document](https://dx.doi.org/10.1214/EJP.v20-3760)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px3.p1.1)\.
- Genzel and Kipp \(2022\)M\. Genzel and C\. KippGeneric error bounds for the generalized lasso with sub\-exponential data\.Sampling Theory, Signal Processing, and Data Analysis20,pp\. 15\.External Links:[Document](https://dx.doi.org/10.1007/s43670-022-00032-8)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px3.p1.1)\.
- Gordon \(1988\)Y\. GordonOn milman’s inequality and random subspaces which escape through a mesh inℝn\{\\mathbb\{R\}\}^\{n\}\.InGeometric Aspects of Functional Analysis,J\. Lindenstrauss and V\. D\. Milman \(Eds\.\),Lecture Notes in Mathematics, Vol\.1317,pp\. 84–106\.Cited by:[§1](https://arxiv.org/html/2609.03504#S1.p3.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Har\-Peled and Sharir \(2011\)S\. Har\-Peled and M\. SharirRelative\(p,ε\)\(p,\\varepsilon\)\-approximations in geometry\.Discrete & Computational Geometry45\(3\),pp\. 462–496\.External Links:[Document](https://dx.doi.org/10.1007/s00454-010-9248-1)Cited by:[§A\.3](https://arxiv.org/html/2609.03504#A1.SS3.p1.3),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px5.p1.1)\.
- Haussler and Welzl \(1987\)D\. Haussler and E\. Welzlε\\varepsilon\-Nets and simplex range queries\.Discrete & Computational Geometry2,pp\. 127–151\.Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px5.p1.1)\.
- Kasiviswanathan and Rudelson \(2018\)S\. P\. Kasiviswanathan and M\. RudelsonRestricted eigenvalue from stable rank with applications to sparse linear regression\.InProceedings of the 31st Conference on Learning Theory,Proceedings of Machine Learning Research, Vol\.75,pp\. 1011–1041\.Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Koltchinskii and Mendelson \(2015\)V\. Koltchinskii and S\. MendelsonBounding the smallest singular value of a random matrix without concentration\.International Mathematics Research Notices2015\(23\),pp\. 12991–13008\.External Links:[Document](https://dx.doi.org/10.1093/imrn/rnv096)Cited by:[§1](https://arxiv.org/html/2609.03504#S1.SS0.SSS0.Px4.p1.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px2.p1.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px5.p1.1)\.
- Komlóset al\.\(1992\)J\. Komlós, J\. Pach, and G\. J\. WoegingerAlmost tight bounds forε\\varepsilon\-nets\.Discrete & Computational Geometry7\(1\),pp\. 163–173\.External Links:[Document](https://dx.doi.org/10.1007/BF02187833)Cited by:[§A\.3](https://arxiv.org/html/2609.03504#A1.SS3.p2.1),[§4\.2](https://arxiv.org/html/2609.03504#S4.SS2.p2.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px5.p1.1)\.
- Kuchibhotla and Chakrabortty \(2022\)A\. K\. Kuchibhotla and A\. ChakraborttyMoving beyond sub\-gaussianity in high\-dimensional statistics: applications in covariance estimation and linear regression\.Information and Inference11\(4\),pp\. 1389–1456\.External Links:[Document](https://dx.doi.org/10.1093/imaiai/iaac012)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px3.p1.1)\.
- Lecué and Mendelson \(2014\)G\. Lecué and S\. MendelsonNecessary moment conditions for exact reconstruction via basis pursuit\.Note:arXiv preprint arXiv:1404\.3116External Links:1404\.3116,[Document](https://dx.doi.org/10.48550/arXiv.1404.3116)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px4.p1.1)\.
- Lecué and Mendelson \(2017a\)G\. Lecué and S\. MendelsonRegularization and the small\-ball method ii: complexity dependent error rates\.Journal of Machine Learning Research18\(146\),pp\. 1–48\.Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px2.p1.1)\.
- Lecué and Mendelson \(2017b\)G\. Lecué and S\. MendelsonSparse recovery under weak moment assumptions\.Journal of the European Mathematical Society19\(3\),pp\. 881–904\.Note:First circulated as arXiv:1401\.2188 in 2014External Links:[Document](https://dx.doi.org/10.4171/JEMS/682),1401\.2188Cited by:[§1](https://arxiv.org/html/2609.03504#S1.SS0.SSS0.Px4.p1.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px3.p1.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px4.p1.1)\.
- Lecué and Mendelson \(2018\)G\. Lecué and S\. MendelsonRegularization and the small\-ball method i: sparse recovery\.The Annals of Statistics46\(2\),pp\. 611–641\.External Links:[Document](https://dx.doi.org/10.1214/17-AOS1562)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px2.p1.1)\.
- Liet al\.\(2001\)Y\. Li, P\. M\. Long, and A\. SrinivasanImproved bounds on the sample complexity of learning\.Journal of Computer and System Sciences62\(3\),pp\. 516–527\.External Links:[Document](https://dx.doi.org/10.1006/jcss.2000.1741)Cited by:[§A\.3](https://arxiv.org/html/2609.03504#A1.SS3.p1.3),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px5.p1.1)\.
- Mendelson \(2015\)S\. MendelsonLearning without concentration\.Journal of the ACM62\(3\),pp\. 21:1–21:25\.External Links:[Document](https://dx.doi.org/10.1145/2699439)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px2.p1.1)\.
- Mendelson \(2021\)S\. MendelsonExtending the scope of the small\-ball method\.Studia Mathematica256\(2\),pp\. 147–167\.External Links:[Document](https://dx.doi.org/10.4064/sm190420-21-11)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px2.p1.1)\.
- Negahbanet al\.\(2012\)S\. N\. Negahban, P\. Ravikumar, M\. J\. Wainwright, and B\. YuA unified framework for high\-dimensional analysis ofMM\-estimators with decomposable regularizers\.Statistical Science27\(4\),pp\. 538–557\.Cited by:[§1](https://arxiv.org/html/2609.03504#S1.p2.2),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Oliveira \(2016\)R\. I\. OliveiraThe lower tail of random quadratic forms with applications to ordinary least squares\.Probability Theory and Related Fields166\(3–4\),pp\. 1175–1194\.External Links:[Document](https://dx.doi.org/10.1007/s00440-016-0738-9)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px2.p1.1)\.
- Oymak and Tropp \(2018\)S\. Oymak and J\. A\. TroppUniversality laws for randomized dimension reduction, with applications\.Information and Inference7\(3\),pp\. 337–446\.External Links:[Document](https://dx.doi.org/10.1093/imaiai/iax011)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Pach and Tardos \(2013\)J\. Pach and G\. TardosTight lower bounds for the size ofε\\varepsilon\-nets\.Journal of the American Mathematical Society26\(3\),pp\. 645–658\.Cited by:[§A\.3](https://arxiv.org/html/2609.03504#A1.SS3.p5.1),[§4\.2](https://arxiv.org/html/2609.03504#S4.SS2.p2.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px5.p1.1)\.
- Raskuttiet al\.\(2010\)G\. Raskutti, M\. J\. Wainwright, and B\. YuRestricted eigenvalue properties for correlated gaussian designs\.Journal of Machine Learning Research11\(78\),pp\. 2241–2259\.Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Rudelson and Zhou \(2013\)M\. Rudelson and S\. ZhouReconstruction from anisotropic random measurements\.IEEE Transactions on Information Theory59\(6\),pp\. 3434–3447\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2013.2243201)Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1)\.
- Sivakumaret al\.\(2015\)V\. Sivakumar, A\. Banerjee, and P\. K\. RavikumarBeyond sub\-gaussian measurements: high\-dimensional structured estimation with sub\-exponential designs\.InAdvances in Neural Information Processing Systems 28,pp\. 2206–2214\.Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px3.p1.1)\.
- Tropp \(2015a\)J\. A\. TroppAn introduction to matrix concentration inequalities\.Foundations and Trends in Machine Learning8\(1–2\),pp\. 1–230\.External Links:[Document](https://dx.doi.org/10.1561/2200000048),1501\.01571Cited by:[§F\.1](https://arxiv.org/html/2609.03504#A6.SS1.p1.3)\.
- Tropp \(2015b\)J\. A\. TroppConvex recovery of a structured signal from independent random linear measurements\.InSampling Theory, a Renaissance,G\. E\. Pfander \(Ed\.\),pp\. 67–101\.Cited by:[§A\.1](https://arxiv.org/html/2609.03504#A1.SS1.p1.2),[§1](https://arxiv.org/html/2609.03504#S1.p3.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px1.p1.1),[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px2.p1.1)\.
- Vershynin \(2018\)R\. VershyninHigh\-dimensional probability: an introduction with applications in data science\.Cambridge University Press\.Cited by:[§F\.3](https://arxiv.org/html/2609.03504#A6.SS3.p1.2)\.
- Wei \(2018\)X\. WeiStructured recovery with heavy\-tailed measurements: a thresholding procedure and optimal rates\.arXiv preprint arXiv:1804\.05959\.Cited by:[§7](https://arxiv.org/html/2609.03504#S7.SS0.SSS0.Px3.p1.1)\.

## Appendix AAuxiliary facts

This appendix records all proofs and the external tools used in them\.[AppendixA](https://arxiv.org/html/2609.03504#A1)collects the empirical small\-ball inequality, Gordon’s Gaussian escape bound, range\-space estimates, and two geometric lemmas proved here\.[AppendixB](https://arxiv.org/html/2609.03504#A2)proves the explicit constant\-width counterexample\.[AppendicesC](https://arxiv.org/html/2609.03504#A3),[D](https://arxiv.org/html/2609.03504#A4)and[E](https://arxiv.org/html/2609.03504#A5)establish exact range\-space representation, its descent\-cone lifting, and the sharp threshold\-complexity law\.[AppendicesF](https://arxiv.org/html/2609.03504#A6)and[G](https://arxiv.org/html/2609.03504#A7)construct the anchored isotropic frame and prove the isotropic separation\.[AppendicesH](https://arxiv.org/html/2609.03504#A8),[I](https://arxiv.org/html/2609.03504#A9)and[J](https://arxiv.org/html/2609.03504#A10)treat smoothing, the dimension–radius guarantee, and the consequences for convex recovery\. Throughout, numerical constants may change from one display to the next\.

Unless stated otherwise, all auxiliary random objects introduced within a construction—includingLL,σ\\sigma,JJ,YY,HH, and their sample copies—are mutually independent\. Suprema over non\-countable sets are interpreted in outer expectation or outer probability\. For the finite or compact polyhedral constructions used here, the relevant suprema are measurable and this distinction disappears\.

When an index set lies in a Euclidean subspaceVVof an ambient space, its Gaussian width is computed using a standard Gaussian vector onVV\. Equivalently, one may use an ambient standard Gaussian and project it orthogonally ontoVV, since all relevant inner products are unchanged\.

### A\.1Empirical small\-ball and Gaussian escape inequalities

For a setA⊆𝕊p−1A\\subseteq\\mathbb\{S\}^\{p\-1\}and a distributionPPonℝp\\mathbb\{R\}^\{p\}, define

𝖰ξ​\(P,A\)=infu∈Aℙ⁡\(\|⟨Z,u⟩\|≥ξ\),Wn​\(A,P\)=𝔼​supu∈A⟨1n​∑i=1nεi​Zi,u⟩,\\mathsf\{Q\}\_\{\\xi\}\(P,A\)=\\inf\_\{u\\in A\}\\mathbb\{P\}\\bigl\(\|\\langle Z,u\\rangle\|\\geq\\xi\\bigr\),\\qquad W\_\{n\}\(A;P\)=\\mathbb\{E\}\\sup\_\{u\\in A\}\\left\\langle\\frac\{1\}\{\\sqrt\{n\}\}\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}Z\_\{i\},u\\right\\rangle,whereZ,Z1,…,ZnZ,Z\_\{1\},\\ldots,Z\_\{n\}are distributed according toPPand theεi\\varepsilon\_\{i\}are independent Rademacher variables\. We use the following form of the small\-ball inequality, which is Proposition 5\.1 of[Tropp \(2015b\)](https://arxiv.org/html/2609.03504#bib.bib7)\.

###### Lemma 12\(Small\-ball inequality\)\.

For everyξ,t\>0\\xi,t\>0, with probability at least1−e−t2/21\-e^\{\-t^\{2\}/2\},

infu∈A‖X​u‖2≥ξ​n​𝖰2​ξ​\(P,A\)−2​Wn​\(A,P\)−ξ​t\.\\inf\_\{u\\in A\}\\\|Xu\\\|\_\{2\}\\geq\\xi\\sqrt\{n\}\\,\\mathsf\{Q\}\_\{2\\xi\}\(P,A\)\-2W\_\{n\}\(A;P\)\-\\xi t\.

For a standard Gaussian matrixG∈ℝn×pG\\in\\mathbb\{R\}^\{n\\times p\}, Gordon’s escape theorem gives the companion inequality

ℙ\(infu∈A∥Gu∥2≥𝔼∥gn∥2−w\(A\)−t\)≥1−e−t2/2,\\mathbb\{P\}\\left\(\\inf\_\{u\\in A\}\\\|Gu\\\|\_\{2\}\\geq\\mathbb\{E\}\\\|g\_\{n\}\\\|\_\{2\}\-w\(A\)\-t\\right\)\\geq 1\-e^\{\-t^\{2\}/2\},\(A\.1\)wheregn∼𝖭⁡\(0,In\)g\_\{n\}\\sim\\mathsf\{N\}\(0,I\_\{n\}\)\. We use the elementary estimate𝔼​‖gn‖2≥n−1\\mathbb\{E\}\\\|g\_\{n\}\\\|\_\{2\}\\geq\\sqrt\{n\-1\}\.

### A\.2Two geometric lemmas

###### Lemma 13\(From a finite cap to its cone\)\.

Letu⋆∈𝕊p−1u\_\{\\star\}\\in\\mathbb\{S\}^\{p\-1\}and let𝒰⊆𝕊p−1\\mathcal\{U\}\\subseteq\\mathbb\{S\}^\{p\-1\}be finite\. Suppose

maxu∈𝒰⁡‖u−u⋆‖2≤r<1\.\\max\_\{u\\in\\mathcal\{U\}\}\\\|u\-u\_\{\\star\}\\\|\_\{2\}\\leq r<1\.SetC=cone⁡\(𝒰\)C=\\operatorname\{cone\}\(\\mathcal\{U\}\)andA=C∩𝕊p−1A=C\\cap\\mathbb\{S\}^\{p\-1\}\. Then

w⁡\(A\)≤r​2​log⁡\|𝒰\|\+r22​p\.w\(A\)\\leq r\\sqrt\{2\\log\|\\mathcal\{U\}\|\}\+\\frac\{r^\{2\}\}\{2\}\\sqrt\{p\}\.\(A\.2\)Moreover, everyv∈Av\\in Asatisfies

‖v−u⋆‖2≤r\+r2/2\.\\\|v\-u\_\{\\star\}\\\|\_\{2\}\\leq r\+r^\{2\}/2\.\(A\.3\)

###### Proof\.

LetK=conv⁡\(𝒰\)K=\\operatorname\{conv\}\(\\mathcal\{U\}\)\. Every nonzero point inCCis a positive multiple of a point inKK, hence eachv∈Av\\in Acan be written asv=x/‖x‖2v=x/\\\|x\\\|\_\{2\}for somex∈Kx\\in K\. Since everyu∈𝒰u\\in\\mathcal\{U\}is a unit vector,

⟨u,u⋆⟩=1−12​‖u−u⋆‖22≥1−r2/2\.\\langle u,u\_\{\\star\}\\rangle=1\-\\frac\{1\}\{2\}\\\|u\-u\_\{\\star\}\\\|\_\{2\}^\{2\}\\geq 1\-r^\{2\}/2\.The same inequality holds forx∈Kx\\in K\. Also‖x‖2≤1\\\|x\\\|\_\{2\}\\leq 1, and therefore

‖x‖x‖2−x‖2=1−‖x‖2≤1−⟨x,u⋆⟩≤r2/2\.\\left\\\|\\frac\{x\}\{\\\|x\\\|\_\{2\}\}\-x\\right\\\|\_\{2\}=1\-\\\|x\\\|\_\{2\}\\leq 1\-\\langle x,u\_\{\\star\}\\rangle\\leq r^\{2\}/2\.This proves \([A\.3](https://arxiv.org/html/2609.03504#A1.E3)\)\. For the width, writeu=u⋆\+\(u−u⋆\)u=u\_\{\\star\}\+\(u\-u\_\{\\star\}\)and apply the Gaussian maximal inequality to the centered Gaussian family\{⟨g,u−u⋆⟩:u∈𝒰\}\\\{\\langle g,u\-u\_\{\\star\}\\rangle:u\\in\\mathcal\{U\}\\\}:

w⁡\(K\)=w⁡\(𝒰\)≤r​2​log⁡\|𝒰\|\.w\(K\)=w\(\\mathcal\{U\}\)\\leq r\\sqrt\{2\\log\|\\mathcal\{U\}\|\}\.For eachv=x/‖x‖2v=x/\\\|x\\\|\_\{2\}as above,

⟨g,v⟩≤⟨g,x⟩\+r22​‖g‖2\.\\langle g,v\\rangle\\leq\\langle g,x\\rangle\+\\frac\{r^\{2\}\}\{2\}\\\|g\\\|\_\{2\}\.Taking the supremum and expectation, and using𝔼​‖g‖2≤p\\mathbb\{E\}\\\|g\\\|\_\{2\}\\leq\\sqrt\{p\}, gives \([A\.2](https://arxiv.org/html/2609.03504#A1.E2)\)\. ∎

###### Lemma 14\(Cone realization\)\.

LetC⊂ℝpC\\subset\\mathbb\{R\}^\{p\}be a full\-dimensional pointed polyhedral cone generated byc1,…,cNc\_\{1\},\\ldots,c\_\{N\}\. There is a centrally symmetric full\-dimensional polytopeBB, a pointx⋆∈∂Bx^\{\\star\}\\in\\partial B, and a polyhedral normℛ\\mathcal\{R\}whose unit ball isBBsuch that

𝒟⁡\(ℛ,x⋆\)=C\.\\mathcal\{D\}\(\\mathcal\{R\},x^\{\\star\}\)=C\.The construction can be made explicit from the generators\.

###### Proof\.

Choosec∘∈int⁡\(C\)c\_\{\\circ\}\\in\\operatorname\{int\}\(C\)\. Since the interior is open and is preserved by positive scaling, for eachiiwe havec∘−ci/\(2​L\)∈int⁡\(C\)c\_\{\\circ\}\-c\_\{i\}/\(2L\)\\in\\operatorname\{int\}\(C\)onceLLis large enough\. Because there are finitely many generators, one may choose a commonL\>0L\>0such that

2​L​c∘−ci∈int⁡\(C\)\(i∈\[N\]\)\.2Lc\_\{\\circ\}\-c\_\{i\}\\in\\operatorname\{int\}\(C\)\\qquad\(i\\in\[N\]\)\.Setx⋆=−L​c∘x^\{\\star\}=\-Lc\_\{\\circ\}and

B=conv\(\{x⋆,x⋆\+ci:i∈\[N\]\}∪\{−x⋆,−x⋆−ci:i∈\[N\]\}\)\.B=\\operatorname\{conv\}\\bigl\(\\\{x^\{\\star\},x^\{\\star\}\+c\_\{i\}:i\\in\[N\]\\\}\\cup\\\{\-x^\{\\star\},\-x^\{\\star\}\-c\_\{i\}:i\\in\[N\]\\\}\\bigr\)\.The setBBis centrally symmetric and full dimensional because thecic\_\{i\}spanℝp\\mathbb\{R\}^\{p\}\. In particular, its center00lies in its interior, so the Minkowski functionalγB\\gamma\_\{B\}is a norm\. Every displacement fromx⋆x^\{\\star\}to a listed point ofBBis one of

ci,2​L​c∘,2​L​c∘−ci,c\_\{i\},\\qquad 2Lc\_\{\\circ\},\\qquad 2Lc\_\{\\circ\}\-c\_\{i\},and hence lies inCC\. Conversely, every generatorcic\_\{i\}occurs, so

cone\(B−x⋆\)=cone\{ci,2Lc∘,2Lc∘−ci:i∈\[N\]\}=C\.\\operatorname\{cone\}\(B\-x^\{\\star\}\)=\\operatorname\{cone\}\\\{c\_\{i\},2Lc\_\{\\circ\},2Lc\_\{\\circ\}\-c\_\{i\}:i\\in\[N\]\\\}=C\.\(A\.4\)To verify thatx⋆x^\{\\star\}is on the boundary, choose a linear functionalℓ∈int⁡\(C∗\)\\ell\\in\\operatorname\{int\}\(C^\{\\ast\}\)\. Pointedness and full dimensionality imply⟨ℓ,z⟩\>0\\langle\\ell,z\\rangle\>0for every nonzeroz∈Cz\\in C\. Every other listed pointyysatisfiesy−x⋆∈C∖\{0\}y\-x^\{\\star\}\\in C\\setminus\\\{0\\\}, hence⟨ℓ,y⟩\>⟨ℓ,x⋆⟩\\langle\\ell,y\\rangle\>\\langle\\ell,x^\{\\star\}\\rangle\. Thusx⋆x^\{\\star\}is an exposed vertex ofBBandγB​\(x⋆\)=1\\gamma\_\{B\}\(x^\{\\star\}\)=1\.

Finally, the definition of the gauge gives

𝒟⁡\(γB,x⋆\)=\{h:x⋆\+t​h∈B​for some​t\>0\}=cone⁡\(B−x⋆\)\.\\mathcal\{D\}\(\\gamma\_\{B\},x^\{\\star\}\)=\\\{h:x^\{\\star\}\+th\\in B\\text\{ for some \}t\>0\\\}=\\operatorname\{cone\}\(B\-x^\{\\star\}\)\.The second equality holds in both directions by writingh=t−1​\(y−x⋆\)h=t^\{\-1\}\(y\-x^\{\\star\}\)or choosingttas the reciprocal of the conic multiplier\. Combining this identity with \([A\.4](https://arxiv.org/html/2609.03504#A1.E4)\) proves the claim withℛ=γB\\mathcal\{R\}=\\gamma\_\{B\}\. ∎

### A\.3Range\-space estimates

We use two classical consequences of VC theory\. First, if a class𝒞\\mathscr\{C\}has VC dimension at mostddand everyC∈𝒞C\\in\\mathscr\{C\}has probability at leastβ\\beta, then

n≥C​d​log⁡\(2/β\)\+log⁡\(1/δ\)βn\\geq C\\frac\{d\\log\(2/\\beta\)\+\\log\(1/\\delta\)\}\{\\beta\}\(A\.5\)implies, with probability at least1−δ1\-\\delta,

infC∈𝒞μn​\(C\)≥β/2\.\\inf\_\{C\\in\\mathscr\{C\}\}\\mu\_\{n\}\(C\)\\geq\\beta/2\.This is a constant\-relative\-error specialization of relative approximation bounds\([Li et al\., 2001](https://arxiv.org/html/2609.03504#bib.bib23);[Har\-Peled and Sharir, 2011](https://arxiv.org/html/2609.03504#bib.bib24)\)\.

For a probability range space\(Ω,μ,𝒞\)\(\\Omega,\\mu,\\mathscr\{C\}\), a finite setS⊆ΩS\\subseteq\\Omegais aβ\\beta\-net if it intersects everyC∈𝒞C\\in\\mathscr\{C\}withμ⁡\(C\)≥β\\mu\(C\)\\geq\\beta\. Writefd​\(β\)f\_\{d\}\(\\beta\)for the supremum, over finite probability range spaces of VC dimension at mostdd, of the minimum cardinality of aβ\\beta\-net\. Theorem 2\.1 of[Komlós et al\. \(1992\)](https://arxiv.org/html/2609.03504#bib.bib21)implies

lim infβ↓0fd​\(β\)β−1​log⁡\(1/β\)≥d−2\+2d\+2\(d≥2\)\.\\liminf\_\{\\beta\\downarrow 0\}\\frac\{f\_\{d\}\(\\beta\)\}\{\\beta^\{\-1\}\\log\(1/\\beta\)\}\\geq d\-2\+\\frac\{2\}\{d\+2\}\\qquad\(d\\geq 2\)\.\(A\.6\)The following finite form is the interface needed below\.

###### Lemma 15\(Finiteβ\\beta\-net lower bound\)\.

There is a universalcnet\>0c\_\{\\mathrm\{net\}\}\>0such that, for every fixedd≥2d\\geq 2, there isβd\>0\\beta\_\{d\}\>0with the following property\. For each0<β≤βd0<\\beta\\leq\\beta\_\{d\}, there is a finite full\-support probability range space\(Ω,μ,𝒞\)\(\\Omega,\\mu,\\mathscr\{C\}\)of VC dimension at mostddsuch that every setS⊆ΩS\\subseteq\\Omegawith

\|S\|<cnet​dβ​log⁡1β\|S\|<c\_\{\\mathrm\{net\}\}\\frac\{d\}\{\\beta\}\\log\\frac\{1\}\{\\beta\}misses some rangeC∈𝒞C\\in\\mathscr\{C\}of massμ⁡\(C\)≥β\\mu\(C\)\\geq\\beta\.

###### Proof\.

The coefficient on the right of \([A\.6](https://arxiv.org/html/2609.03504#A1.E6)\) satisfies

d−2\+2/\(d\+2\)d≥14\(d≥2\)\.\\frac\{d\-2\+2/\(d\+2\)\}\{d\}\\geq\\frac\{1\}\{4\}\\qquad\(d\\geq 2\)\.Hence, for every fixeddd, the liminf statement gives the asserted order with a universal numerical constant onceβ\\betais below a thresholdβd\\beta\_\{d\}that may depend ondd\. Becausefdf\_\{d\}is a supremum, one chooses a finite range space whose minimum net size is, say, at least half the displayed lower bound; no attainment of the supremum is needed\. The constructions in the cited theorem use a finite ground set with the uniform measure, hence have full support\.

Our convention usesμ⁡\(C\)≥β\\mu\(C\)\\geq\\beta\. If the strict conventionμ⁡\(C\)\>ε\\mu\(C\)\>\\varepsilonis used in the cited formulation, apply it withε=2​β\\varepsilon=2\\betaand retain the ranges of mass greater than2​β2\\beta\. They all have mass at leastβ\\beta, their VC dimension cannot increase, and, after decreasingβd\\beta\_\{d\},

d2​β​log⁡12​β≥c​dβ​log⁡1β\.\\frac\{d\}\{2\\beta\}\\log\\frac\{1\}\{2\\beta\}\\geq c\\frac\{d\}\{\\beta\}\\log\\frac\{1\}\{\\beta\}\.This changes only the universal constant and proves the stated weak\-threshold form\. ∎

The thresholdβd\\beta\_\{d\}is not asserted to be uniform indd\.[Pach and Tardos \(2013\)](https://arxiv.org/html/2609.03504#bib.bib22)give a geometric VC\-two construction with the same logarithmic phenomenon\. For VC dimension one, deterministic net size alone does not contain this logarithm, but random sampling does, by the coupon\-collector argument in[AppendixE](https://arxiv.org/html/2609.03504#A5)\.

## Appendix BProof of the explicit counterexample

###### Proof\.

### B\.1The norm and its descent cone

Recall

Vm=\{\(t,y/m\):t∈ℝ,y∈ℝm,∑j=1myj=0\}V\_\{m\}=\\left\\\{\(t,y/m\):t\\in\\mathbb\{R\},\\ y\\in\\mathbb\{R\}^\{m\},\\ \\sum\_\{j=1\}^\{m\}y\_\{j\}=0\\right\\\}and

ℛm​\(t,y/m\)=max⁡\{\|t\|,maxj⁡\|t−yj\|,maxj⁡\|t\+yj\|\}\.\\mathcal\{R\}\_\{m\}\(t,y/m\)=\\max\\left\\\{\|t\|,\\max\_\{j\}\|t\-y\_\{j\}\|,\\max\_\{j\}\|t\+y\_\{j\}\|\\right\\\}\.This is the maximum of finitely many absolute linear functionals\. If it vanishes, thent=0t=0andt±yj=0t\\pm y\_\{j\}=0for everyjj, hencey=0y=0\. It is therefore a norm onVmV\_\{m\}\.

Letθm⋆=\(−1,0\)\\theta\_\{m\}^\{\\star\}=\(\-1,0\)and letv=\(t,y/m\)v=\(t,y/m\)\. Forλ\>0\\lambda\>0,

ℛm​\(θm⋆\+λ​v\)=max⁡\{\|−1\+λ​t\|,maxj⁡\|−1\+λ⁡\(t−yj\)\|,maxj⁡\|−1\+λ⁡\(t\+yj\)\|\}\.\\mathcal\{R\}\_\{m\}\(\\theta\_\{m\}^\{\\star\}\+\\lambda v\)=\\max\\left\\\{\|\-1\+\\lambda t\|,\\max\_\{j\}\|\-1\+\\lambda\(t\-y\_\{j\}\)\|,\\max\_\{j\}\|\-1\+\\lambda\(t\+y\_\{j\}\)\|\\right\\\}\.There exists a sufficiently smallλ\>0\\lambda\>0for which this maximum is at most one exactly when

t≥0,t−yj≥0,t\+yj≥0\(j∈\[m\]\)\.t\\geq 0,\\qquad t\-y\_\{j\}\\geq 0,\\qquad t\+y\_\{j\}\\geq 0\\quad\(j\\in\[m\]\)\.Thus

𝒟\(ℛm,θm⋆\)=Cm=\{\(t,y/m\):t≥0,\|yj\|≤t,∑jyj=0\}\.\\mathcal\{D\}\(\\mathcal\{R\}\_\{m\},\\theta\_\{m\}^\{\\star\}\)=C\_\{m\}=\\\{\(t,y/m\):t\\geq 0,\\ \|y\_\{j\}\|\\leq t,\\ \\sum\_\{j\}y\_\{j\}=0\\\}\.

### B\.2Uniform small\-ball bound

For

rj=e0\+m​ej−∑ℓ=1meℓr\_\{j\}=e\_\{0\}\+me\_\{j\}\-\\sum\_\{\\ell=1\}^\{m\}e\_\{\\ell\}andv=\(t,y/m\)∈Cmv=\(t,y/m\)\\in C\_\{m\}, direct calculation gives

⟨rj,v⟩=t\+yj\.\\langle r\_\{j\},v\\rangle=t\+y\_\{j\}\.Setaj=t\+yja\_\{j\}=t\+y\_\{j\}\. Then0≤aj≤2​t0\\leq a\_\{j\}\\leq 2tandm−1​∑jaj=tm^\{\-1\}\\sum\_\{j\}a\_\{j\}=t\. If fewer thanm/3m/3of theaja\_\{j\}were at leastt/2t/2, then

1m​∑jaj<13​\(2​t\)\+23​\(t/2\)=t,\\frac\{1\}\{m\}\\sum\_\{j\}a\_\{j\}<\\frac\{1\}\{3\}\(2t\)\+\\frac\{2\}\{3\}\(t/2\)=t,a contradiction\. Also

‖v‖22=t2\+1m2​∑jyj2≤t2\+1m​t2≤2​t2\.\\\|v\\\|\_\{2\}^\{2\}=t^\{2\}\+\\frac\{1\}\{m^\{2\}\}\\sum\_\{j\}y\_\{j\}^\{2\}\\leq t^\{2\}\+\\frac\{1\}\{m\}t^\{2\}\\leq 2t^\{2\}\.SinceL≥1L\\geq 1, forZm=σ​L​rJZ\_\{m\}=\\sigma Lr\_\{J\},

ℙ⁡\(\|⟨Zm,v⟩\|≥12​2​‖v‖2\)≥13\.\\mathbb\{P\}\\left\(\|\\langle Z\_\{m\},v\\rangle\|\\geq\\frac\{1\}\{2\\sqrt\{2\}\}\\\|v\\\|\_\{2\}\\right\)\\geq\\frac\{1\}\{3\}\.Homogeneity gives the claimed bound onAmA\_\{m\}\.

### B\.3Gaussian width

Forv=\(t,y/m\)∈Amv=\(t,y/m\)\\in A\_\{m\}, the cone constraints and‖v‖2=1\\\|v\\\|\_\{2\}=1imply0≤t≤10\\leq t\\leq 1and\|yj\|≤t\|y\_\{j\}\|\\leq t\. Letg=\(g0,g1,…,gm\)g=\(g\_\{0\},g\_\{1\},\\ldots,g\_\{m\}\)be standard Gaussian in the ambientℝm\+1\\mathbb\{R\}^\{m\+1\}\. Its orthogonal projection ontoVmV\_\{m\}is a standard Gaussian vector onVmV\_\{m\}, and inner products withv∈Vmv\\in V\_\{m\}are unchanged\. Hence

supv∈Am⟨g,v⟩≤\|g0\|\+1m​∑j=1m\|gj\|\.\\sup\_\{v\\in A\_\{m\}\}\\langle g,v\\rangle\\leq\|g\_\{0\}\|\+\\frac\{1\}\{m\}\\sum\_\{j=1\}^\{m\}\|g\_\{j\}\|\.Taking expectations yields

w⁡\(Am\)≤2​𝔼​\|g0\|=2​2/π\.w\(A\_\{m\}\)\\leq 2\\mathbb\{E\}\|g\_\{0\}\|=2\\sqrt\{2/\\pi\}\.

### B\.4Deterministic kernel and VC dimension

LetD⊆\[m\]D\\subseteq\[m\]denote the distinct indices observed amongJ1,…,JnJ\_\{1\},\\ldots,J\_\{n\}\. Ifn≤m/2n\\leq m/2, choose a setN⊆\[m\]N\\subseteq\[m\]of cardinalitym/2m/2withD⊆ND\\subseteq N, and definesj=−1s\_\{j\}=\-1onNNandsj=1s\_\{j\}=1offNN\. Thens∈\{−1,1\}ms\\in\\\{\-1,1\\\}^\{m\}and∑jsj=0\\sum\_\{j\}s\_\{j\}=0\. Therefore

us=\(1,s/m\)1\+1/m∈Am\.u\_\{s\}=\\frac\{\(1,s/m\)\}\{\\sqrt\{1\+1/m\}\}\\in A\_\{m\}\.For each row type,

⟨rj,us⟩=1\+sj1\+1/m\.\\langle r\_\{j\},u\_\{s\}\\rangle=\\frac\{1\+s\_\{j\}\}\{\\sqrt\{1\+1/m\}\}\.All observed rows have indices inD⊆ND\\subseteq N, henceX​us=0Xu\_\{s\}=0\. This proves \([6](https://arxiv.org/html/2609.03504#S3.E6)\) for every realization\.

To prove the VC lower bound, fix anyI⊆\[m\]I\\subseteq\[m\]of cardinalitym/2m/2and choose one support pointzj=ℓ0​rjz\_\{j\}=\\ell\_\{0\}r\_\{j\}for eachj∈Ij\\in I, whereℓ0\>1\\ell\_\{0\}\>1belongs to the support ofLL\. Given any label setB⊆IB\\subseteq I, prescribesj=1s\_\{j\}=1forj∈Bj\\in Bandsj=−1s\_\{j\}=\-1forj∈I∖Bj\\in I\\setminus B\. Among the remainingm/2m/2coordinates, choose signs so that the total sum is zero\. This is possible because the partial sum onIIhas the same parity asm/2m/2and lies between−m/2\-m/2andm/2m/2\. For the resulting balancedss,

𝟏\{\|⟨zj,us⟩\|≥1\}=𝟏\{sj=1\}\(j∈I\),\\mathbf\{1\}\\\{\|\\langle z\_\{j\},u\_\{s\}\\rangle\|\\geq 1\\\}=\\mathbf\{1\}\\\{s\_\{j\}=1\\\}\\qquad\(j\\in I\),since2​ℓ0/1\+1/m\>12\\ell\_\{0\}/\\sqrt\{1\+1/m\}\>1\. ThusIIis shattered andVC⁡\(𝒯1​\(Am\)\|supp⁡Pm\)≥m/2\\operatorname\{VC\}\(\\mathcal\{T\}\_\{1\}\(A\_\{m\}\)\|\_\{\\operatorname\{supp\}P\_\{m\}\}\)\\geq m/2\.

The random vector is centered because ofσ\\sigmaand has finite moments of every order becauseLLdoes\. To verify the spanning claim, observe thatm−1​∑jrj=e0m^\{\-1\}\\sum\_\{j\}r\_\{j\}=e\_\{0\}andrj−rm=m⁡\(ej−em\)r\_\{j\}\-r\_\{m\}=m\(e\_\{j\}\-e\_\{m\}\)forj<mj<m\. These vectors span the anchor coordinate and the zero\-sum subspace, hence all ofVmV\_\{m\}\. Therefore, for every nonzerov∈Vmv\\in V\_\{m\}, some⟨rj,v⟩\\langle r\_\{j\},v\\rangleis nonzero\. Conditioning onJ=jJ=jshows𝔼​es​\|⟨Zm,v⟩\|=∞\\mathbb\{E\}e^\{s\|\\langle Z\_\{m\},v\\rangle\|\}=\\inftyfor alls\>0s\>0\. ∎

## Appendix CExact range\-space representation

###### Proof\.

LetA=\{u1,…,uM\}A=\\\{u\_\{1\},\\ldots,u\_\{M\}\\\}andZZbe as in[Theorem3](https://arxiv.org/html/2609.03504#Thmtheorem3)\. The independent sign centersZZ\. SinceL\>1L\>1almost surely,

⟨Z,uj⟩=σL𝟏\{Y∈Cj\}\\langle Z,u\_\{j\}\\rangle=\\sigma L\\mathbf\{1\}\\\{Y\\in C\_\{j\}\\\}implies the claimed small\-ball inequality and \([9](https://arxiv.org/html/2609.03504#S4.E9)\)\. To justify the VC equality carefully, map a support pointzzto the incidence vectorI\(z\)=\(𝟏\{\|⟨z,uj⟩\|≥1\}\)j≤MI\(z\)=\(\\mathbf\{1\}\\\{\|\\langle z,u\_\{j\}\\rangle\|\\geq 1\\\}\)\_\{j\\leq M\}\. The displayed identity says that the set of incidence vectors onsupp⁡\(P\)\\operatorname\{supp\}\(P\)equals the set of incidence vectors\(𝟏\{y∈Cj\}\)j≤M\(\\mathbf\{1\}\\\{y\\in C\_\{j\}\\\}\)\_\{j\\leq M\}onsupp⁡\(μ\)\\operatorname\{supp\}\(\\mu\)\. By the full\-support convention in the theorem,supp⁡\(μ\)=Ω\\operatorname\{supp\}\(\\mu\)=\\Omega\. Repeated latent points, signs, and radial values only duplicate an incidence vector\. Choosing one representative from each nonempty incidence fiber transfers shattered sets in both directions, proving equality of the support\-restricted VC dimensions\.

For each sample and eachjj,

min\{1,⟨Zi,uj⟩2\}=𝟏\{Yi∈Cj\},\\min\\\{1,\\langle Z\_\{i\},u\_\{j\}\\rangle^\{2\}\\\}=\\mathbf\{1\}\\\{Y\_\{i\}\\in C\_\{j\}\\\},which proves \([10](https://arxiv.org/html/2609.03504#S4.E10)\)\. The untruncated sum in directionuju\_\{j\}is positive exactly when someYiY\_\{i\}belongs toCjC\_\{j\}\. Taking the minimum overjjproves the hitting equivalence\.

Finally,

supj≤M⟨g,uj⟩=g0\+ε​maxj≤M​gj1\+ε2\.\\sup\_\{j\\leq M\}\\langle g,u\_\{j\}\\rangle=\\frac\{g\_\{0\}\+\\varepsilon\\max\_\{j\\leq M\}g\_\{j\}\}\{\\sqrt\{1\+\\varepsilon^\{2\}\}\}\.The expectation ofg0g\_\{0\}is zero and𝔼​maxj​gj≤2​log⁡\(2​M\)\\mathbb\{E\}\\max\_\{j\}g\_\{j\}\\leq\\sqrt\{2\\log\(2M\)\}\. Hence the claimed width bound follows whenever

ε≤η2​log⁡\(2​M\)\.\\varepsilon\\leq\\frac\{\\eta\}\{\\sqrt\{2\\log\(2M\)\}\}\.This formula also coversM=1M=1and shows that the width can be sent to zero without altering the represented range system\. ∎

## Appendix DDescent\-cone range universality

###### Proof\.

The mapTεT\_\{\\varepsilon\}in \([12](https://arxiv.org/html/2609.03504#S4.E12)\) is injective, so

ℛε​\(Tε​a\)=‖a‖∞\\mathcal\{R\}\_\{\\varepsilon\}\(T\_\{\\varepsilon\}a\)=\\\|a\\\|\_\{\\infty\}defines a norm onVεV\_\{\\varepsilon\}\. Its unit ball isTε​\[−1,1\]MT\_\{\\varepsilon\}\[\-1,1\]^\{M\}, a centrally symmetric polytope inVεV\_\{\\varepsilon\}; henceℛε\\mathcal\{R\}\_\{\\varepsilon\}is a polyhedral norm\. Forh=Tε​ah=T\_\{\\varepsilon\}a,

ℛε\(−Tε𝟏\+th\)≤1⟺∥−𝟏\+ta∥∞≤1\.\\mathcal\{R\}\_\{\\varepsilon\}\(\-T\_\{\\varepsilon\}\\mathbf\{1\}\+th\)\\leq 1\\quad\\Longleftrightarrow\\quad\\\|\-\\mathbf\{1\}\+ta\\\|\_\{\\infty\}\\leq 1\.The latter holds for somet\>0t\>0if and only ifa≥0a\\geq 0coordinatewise\. This proves the cone identity in \([12](https://arxiv.org/html/2609.03504#S4.E12)\)\. Every nonzeroa≥0a\\geq 0can be written as\(𝟏⊤​a\)​q\(\\mathbf\{1\}^\{\\top\}a\)qwithq∈ΔMq\\in\\Delta\_\{M\}, and normalization gives the parametrization in \([12](https://arxiv.org/html/2609.03504#S4.E12)\)\.

Let

Z~=2​1\+ε2β​εσL∑j=1M𝟏\{Y∈Cj\}ej∈ℝM\+1,\\widetilde\{Z\}=\\frac\{2\\sqrt\{1\+\\varepsilon^\{2\}\}\}\{\\beta\\varepsilon\}\\sigma L\\sum\_\{j=1\}^\{M\}\\mathbf\{1\}\\\{Y\\in C\_\{j\}\\\}e\_\{j\}\\in\\mathbb\{R\}^\{M\+1\},and letZZbe its orthogonal projection ontoVεV\_\{\\varepsilon\}\. Inner products withu⁡\(q\)∈Vεu\(q\)\\in V\_\{\\varepsilon\}are unchanged, and

\|⟨Z,u⁡\(q\)⟩\|\\displaystyle\|\\langle Z,u\(q\)\\rangle\|=2​1\+ε2β​1\+ε2​‖q‖22​L​fq​\(Y\)\\displaystyle=\\frac\{2\\sqrt\{1\+\\varepsilon^\{2\}\}\}\{\\beta\\sqrt\{1\+\\varepsilon^\{2\}\\\|q\\\|\_\{2\}^\{2\}\}\}Lf\_\{q\}\(Y\)≥2β​fq​\(Y\)\.\\displaystyle\\geq\\frac\{2\}\{\\beta\}f\_\{q\}\(Y\)\.Because0≤fq≤10\\leq f\_\{q\}\\leq 1and𝔼​fq≥β\\mathbb\{E\}f\_\{q\}\\geq\\beta, ifpq=ℙ⁡\(fq≥β/2\)p\_\{q\}=\\mathbb\{P\}\(f\_\{q\}\\geq\\beta/2\), then

β≤𝔼​fq≤pq\+\(1−pq\)​β/2,\\beta\\leq\\mathbb\{E\}f\_\{q\}\\leq p\_\{q\}\+\(1\-p\_\{q\}\)\\beta/2,and thereforepq≥β/\(2−β\)p\_\{q\}\\geq\\beta/\(2\-\\beta\)\. This proves the uniform small\-ball bound\.

For the width, letg=\(g0,g′\)g=\(g\_\{0\},g^\{\\prime\}\)be standard Gaussian inℝM\+1\\mathbb\{R\}^\{M\+1\}\. Putdq=1\+ε2​‖q‖22d\_\{q\}=\\sqrt\{1\+\\varepsilon^\{2\}\\\|q\\\|\_\{2\}^\{2\}\}\. Ifg0≥0g\_\{0\}\\geq 0, theng0/dq≤g0g\_\{0\}/d\_\{q\}\\leq g\_\{0\}\. Ifg0<0g\_\{0\}<0, then

g0dq=g0\+\|g0\|\(1−1dq\)≤g0\+ε22​\|g0\|\.\\frac\{g\_\{0\}\}\{d\_\{q\}\}=g\_\{0\}\+\|g\_\{0\}\|\\left\(1\-\\frac\{1\}\{d\_\{q\}\}\\right\)\\leq g\_\{0\}\+\\frac\{\\varepsilon^\{2\}\}\{2\}\|g\_\{0\}\|\.Also

ε​⟨g′,q⟩dq≤ε​max⁡\{0,g1,…,gM\}\.\\frac\{\\varepsilon\\langle g^\{\\prime\},q\\rangle\}\{d\_\{q\}\}\\leq\\varepsilon\\max\\\{0,g\_\{1\},\\ldots,g\_\{M\}\\\}\.Consequently,

w⁡\(Aε\)≤ε​𝔼​max⁡\{0,g1,…,gM\}\+ε22​𝔼​\|g0\|≤ε​2​log⁡\(2​M\)\+ε22​π\.w\(A\_\{\\varepsilon\}\)\\leq\\varepsilon\\mathbb\{E\}\\max\\\{0,g\_\{1\},\\ldots,g\_\{M\}\\\}\+\\frac\{\\varepsilon^\{2\}\}\{2\}\\mathbb\{E\}\|g\_\{0\}\|\\leq\\varepsilon\\sqrt\{2\\log\(2M\)\}\+\\frac\{\\varepsilon^\{2\}\}\{\\sqrt\{2\\pi\}\}\.Choosingε\\varepsilonsmall gives any prescribedη\\eta\. Finally, if the latent sample missesCjC\_\{j\}, thenfej​\(Yi\)=0f\_\{e\_\{j\}\}\(Y\_\{i\}\)=0for allii, henceX​u​\(ej\)=0Xu\(e\_\{j\}\)=0\. ∎

## Appendix ESharp threshold\-complexity law

###### Proof\.

The definition of𝖭RE\\mathsf\{N\}\_\{\\mathrm\{RE\}\}asks for a threshold valid for every larger sample size\. If the universal conclusion fails at someN0N\_\{0\}, then non≤N0n\\leq N\_\{0\}satisfies the definition, and hence𝖭RE≥N0\+1\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\\geq N\_\{0\}\+1\. Each upper bound below applies marginally at every larger sample size\.

#### Upper bound\.

Apply the relative VC estimate \([A\.5](https://arxiv.org/html/2609.03504#A1.E5)\) to the support\-restricted threshold class𝒯1​\(A\)\\mathcal\{T\}\_\{1\}\(A\)\. For everyN≥C⁡\[d​log⁡\(2/β\)\+log⁡\(1/δ\)\]/βN\\geq C\[d\\log\(2/\\beta\)\+\\log\(1/\\delta\)\]/\\beta, with probability at least1−δ1\-\\delta,q^N,1​\(A\)≥β/2\\widehat\{q\}\_\{N,1\}\(A\)\\geq\\beta/2\. The deterministic inequality \([8](https://arxiv.org/html/2609.03504#S4.E8)\) then givesΛN​\(X,A\)≥β/2\\Lambda\_\{N\}\(X;A\)\\geq\\beta/2\.

#### A universald/βd/\\betalower bound\.

Assume first that0<β≤1/40<\\beta\\leq 1/4\. LetN0=⌊d/β⌋N\_\{0\}=\\lfloor d/\\beta\\rfloorand put the uniform measure on\[N0\]\[N\_\{0\}\]\. Take as ranges alldd\-element subsets\. Each range has massd/N0≥βd/N\_\{0\}\\geq\\beta, and the class has VC dimension exactlydd: it shatters a fixeddd\-set, using points outside that set to complete each trace to cardinalitydd, and no\(d\+1\)\(d\+1\)\-set can be shattered\. Any hitting set must have at leastN0−d\+1N\_\{0\}\-d\+1points, since the complement of a smaller set contains add\-range\. Therefore every sample with fewer thanN0−d\+1≥c​d/βN\_\{0\}\-d\+1\\geq cd/\\betadistinct points misses a range\. The exact representation theorem converts this deterministic miss intoΛn=0\\Lambda\_\{n\}=0while preserving threshold VC dimension\. This proves𝖭RE≥c​d/β\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\\geq cd/\\beta\.

For reference, the precedingd/βd/\\betaconstruction has no hidden endpoint loss: withn0=N0−dn\_\{0\}=N\_\{0\}\-d, every sample of sizen0n\_\{0\}misses a range, so

𝖭RE​\(d,β,δ\)≥n0\+1=N0−d\+1≥34​dβ\.\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\(d,\\beta,\\delta\)\\geq n\_\{0\}\+1=N\_\{0\}\-d\+1\\geq\\frac\{3\}\{4\}\\frac\{d\}\{\\beta\}\.Here⌊d/β⌋\+1≥d/β\\lfloor d/\\beta\\rfloor\+1\\geq d/\\betaandβ≤1/4\\beta\\leq 1/4give the last inequality\.

#### The coupon\-collector term, includingd=1d=1\.

For0<β≤1/160<\\beta\\leq 1/16, letM=⌊1/\(2​β\)⌋M=\\lfloor 1/\(2\\beta\)\\rfloorpoints each have massβ\\beta, put the remaining mass on one extra point, and let the ranges be theMMsingletons\. This class has VC dimension one\. LetUUbe the number of singleton ranges missed bynnindependent observations\. Then

𝔼​U=M​\(1−β\)n,Var⁡\(U\)≤𝔼​U,\\mathbb\{E\}U=M\(1\-\\beta\)^\{n\},\\qquad\\operatorname\{Var\}\(U\)\\leq\\mathbb\{E\}U,\(E\.1\)because two missing indicators have covariance\(1−2​β\)n−\(1−β\)2​n≤0\(1\-2\\beta\)^\{n\}\-\(1\-\\beta\)^\{2n\}\\leq 0\. Ifn≤\(4​β\)−1​log⁡Mn\\leq\(4\\beta\)^\{\-1\}\\log M, then\(1−β\)n≥e−2​β​n≥M−1/2\(1\-\\beta\)^\{n\}\\geq e^\{\-2\\beta n\}\\geq M^\{\-1/2\}, so𝔼​U≥M\\mathbb\{E\}U\\geq\\sqrt\{M\}\. Chebyshev’s inequality yieldsP\{U=0\}≤Var\(U\)/\(𝔼U\)2≤M−1/2P\\\{U=0\\\}\\leq\\operatorname\{Var\}\(U\)/\(\\mathbb\{E\}U\)^\{2\}\\leq M^\{\-1/2\}\. HereM≥8M\\geq 8, so the probability of hitting every singleton is strictly below3/43/4\. Moreover,M≥1/\(4​β\)M\\geq 1/\(4\\beta\)and hencelog⁡M≥c​log⁡\(2/β\)\\log M\\geq c\\log\(2/\\beta\)on0<β≤1/160<\\beta\\leq 1/16\. The exact representation therefore gives the claimed order on this interval\. For1/16<β≤1/41/16<\\beta\\leq 1/4, a single range of massβ\\betais missed at sample size one with probability1−β≥3/41\-\\beta\\geq 3/4, whileβ−1​log⁡\(2/β\)≤16​log⁡32\\beta^\{\-1\}\\log\(2/\\beta\)\\leq 16\\log 32\. Decreasing the same universal constant covers this remaining interval and yields

𝖭RE​\(d,β,1/4\)≥c​log⁡\(2/β\)β\(d≥1\)\.\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\(d,\\beta,1/4\)\\geq c\\,\\frac\{\\log\(2/\\beta\)\}\{\\beta\}\\qquad\(d\\geq 1\)\.\(E\.2\)Indeed, on the first interval one may taken0=⌊\(4​β\)−1​log⁡M⌋n\_\{0\}=\\lfloor\(4\\beta\)^\{\-1\}\\log M\\rfloor; the probability of success atn0n\_\{0\}is below3/43/4, whence𝖭RE≥n0\+1\>\(4​β\)−1​log⁡M\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\\geq n\_\{0\}\+1\>\(4\\beta\)^\{\-1\}\\log M\. This makes the integer reduction explicit\. This is why the random\-sample problem retains a logarithm for VC dimension one, even though a smallest deterministic net need not\. Since𝖭RE\\mathsf\{N\}\_\{\\mathrm\{RE\}\}is nonincreasing asδ\\deltaincreases, \([E\.2](https://arxiv.org/html/2609.03504#A5.E2)\) also holds for everyδ≤1/4\\delta\\leq 1/4\.

#### The confidence term\.

An explicit range space isΩ=\{a,b\}\\Omega=\\\{a,b\\\}withμ⁡\(a\)=β\\mu\(a\)=\\betaand𝒞=\{\{a\}\}\\mathscr\{C\}=\\\{\\\{a\\\}\\\}; it has full support and VC dimension zero\. Take one range of mass exactlyβ\\beta\. It is missed with probability\(1−β\)n≥e−2​β​n\(1\-\\beta\)^\{n\}\\geq e^\{\-2\\beta n\}forβ≤1/4\\beta\\leq 1/4\. Consequently, every integern<\(2​β\)−1​log⁡\(1/δ\)n<\(2\\beta\)^\{\-1\}\\log\(1/\\delta\)has failure probability strictly larger thanδ\\delta\. Accounting for the integer endpoint only changes a universal constant, and therefore

𝖭RE​\(d,β,δ\)≥c​1β​log⁡1δ\.\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\(d,\\beta,\\delta\)\\geq c\\frac\{1\}\{\\beta\}\\log\\frac\{1\}\{\\delta\}\.\(E\.3\)More precisely, setT=\(2​β\)−1​log⁡\(1/δ\)T=\(2\\beta\)^\{\-1\}\\log\(1/\\delta\)andn0=⌈T⌉−1<Tn\_\{0\}=\\lceil T\\rceil\-1<T\. Failure atn0n\_\{0\}gives𝖭RE≥n0\+1=⌈T⌉≥T\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\\geq n\_\{0\}\+1=\\lceil T\\rceil\\geq T\. The maximum of the three lower bounds above is at least one third of their sum\. This proves the left side of \([13](https://arxiv.org/html/2609.03504#S4.E13)\)\.

#### Sharp fixed\-ddlow\-mass regime\.

Fixd≥2d\\geq 2and take the finite full\-support range space supplied by[Lemma15](https://arxiv.org/html/2609.03504#Thmtheorem15); decreaseβd\\beta\_\{d\}if necessary so thatβd≤1/4\\beta\_\{d\}\\leq 1/4\. Removing any ranges of mass belowβ\\betacannot increase VC dimension\. By the lemma, every subset ofΩ\\Omegawith fewer thancnet​\(d/β\)​log⁡\(1/β\)c\_\{\\mathrm\{net\}\}\(d/\\beta\)\\log\(1/\\beta\)points misses a retained range of mass at leastβ\\beta\. The distinct support of a multiset sample has cardinality at most the sample size, so every sample path below this threshold misses such a range\. Applying[Theorem3](https://arxiv.org/html/2609.03504#Thmtheorem3)givesΛn=0\\Lambda\_\{n\}=0on every path while preserving the support\-restricted VC dimension\. Ford=1d=1, \([E\.2](https://arxiv.org/html/2609.03504#A5.E2)\) gives the same order\. Finally,log⁡\(1/β\)≍log⁡\(2/β\)\\log\(1/\\beta\)\\asymp\\log\(2/\\beta\)on this range\. Combining this term with \([E\.3](https://arxiv.org/html/2609.03504#A5.E3)\) proves \([14](https://arxiv.org/html/2609.03504#S4.E14)\) for every fixedddand all0<β≤βd0<\\beta\\leq\\beta\_\{d\}\. For the strict inequality in[Lemma15](https://arxiv.org/html/2609.03504#Thmtheorem15), putTβ=cnet​\(d/β\)​log⁡\(1/β\)T\_\{\\beta\}=c\_\{\\mathrm\{net\}\}\(d/\\beta\)\\log\(1/\\beta\)andn0=⌈Tβ⌉−1<Tβn\_\{0\}=\\lceil T\_\{\\beta\}\\rceil\-1<T\_\{\\beta\}\. Every size\-n0n\_\{0\}sample then fails pathwise, so𝖭RE≥n0\+1=⌈Tβ⌉≥Tβ\\mathsf\{N\}\_\{\\mathrm\{RE\}\}\\geq n\_\{0\}\+1=\\lceil T\_\{\\beta\}\\rceil\\geq T\_\{\\beta\}\. ∎

## Appendix FThe anchored isotropic frame

###### Proof\.

We use the probabilistic method\. The proof has four steps\. We first control the empirical covariance, then establish a uniform slab lower bound, and next condition every row submatrix of sizeO⁡\(p/log⁡p\)O\(p/\\log p\)\. A final whitening step makes the frame exactly tight while preserving the common anchor and the three preceding estimates\. LetM=p4M=p^\{4\}and let

aj=\(1,ξj\)∈ℝ×ℝp−1,j∈\[M\],a\_\{j\}=\(1,\\xi\_\{j\}\)\\in\\mathbb\{R\}\\times\\mathbb\{R\}^\{p\-1\},\\qquad j\\in\[M\],where theξj\\xi\_\{j\}are independent vectors with independent Rademacher coordinates\. Define

Σ=1M​∑j=1Maj​aj⊤\.\\Sigma=\\frac\{1\}\{M\}\\sum\_\{j=1\}^\{M\}a\_\{j\}a\_\{j\}^\{\\top\}\.We establish three simultaneous events of positive probability\.

### F\.1Covariance control

The vectorsaja\_\{j\}are isotropic in the sense that𝔼​aj​aj⊤=Ip\\mathbb\{E\}a\_\{j\}a\_\{j\}^\{\\top\}=I\_\{p\}and satisfy‖aj‖22=p\\\|a\_\{j\}\\\|\_\{2\}^\{2\}=pdeterministically\. Matrix Bernstein, applied toaj​aj⊤−Ipa\_\{j\}a\_\{j\}^\{\\top\}\-I\_\{p\}, yields

ℙ\(∥Σ−Ip∥op\>1/4\)≤2pexp\(−cM/p\)\.\\mathbb\{P\}\\left\(\\\|\\Sigma\-I\_\{p\}\\\|\_\{\\mathrm\{op\}\}\>1/4\\right\)\\leq 2p\\exp\(\-cM/p\)\.\(F\.1\)For completeness, ifYj=aj​aj⊤−IpY\_\{j\}=a\_\{j\}a\_\{j\}^\{\\top\}\-I\_\{p\}, then‖Yj‖op≤p\+1≤2​p\\\|Y\_\{j\}\\\|\_\{\\mathrm\{op\}\}\\leq p\+1\\leq 2pand

𝔼​Yj2=\(p−1\)​Ip\.\\mathbb\{E\}Y\_\{j\}^\{2\}=\(p\-1\)I\_\{p\}\.The self\-adjoint matrix Bernstein inequality\([Tropp, 2015a](https://arxiv.org/html/2609.03504#bib.bib8), Theorem 6\.1\.1\), applied at deviation levelM/4M/4, has variance proxyM⁡\(p−1\)M\(p\-1\)and range bound2​p2p\. Substitution gives an exponent at most−cM/p\-cM/p, proving the displayed estimate\. In particular, on the complementary event

34​Ip⪯Σ⪯54​Ip\.\\frac\{3\}\{4\}I\_\{p\}\\preceq\\Sigma\\preceq\\frac\{5\}\{4\}I\_\{p\}\.\(F\.2\)

### F\.2A uniform empirical slab bound

For fixedv=\(v0,v′\)∈𝕊p−1v=\(v\_\{0\},v^\{\\prime\}\)\\in\\mathbb\{S\}^\{p\-1\}anda=\(1,ξ\)a=\(1,\\xi\), putS=⟨a,v⟩=v0\+⟨ξ,v′⟩S=\\langle a,v\\rangle=v\_\{0\}\+\\langle\\xi,v^\{\\prime\}\\rangle\. Then

and a direct fourth\-moment expansion gives

𝔼​S4=v04\+6​v02​‖v′‖22\+3​‖v′‖24−2​∑ℓ=1p−1vℓ4≤3\.\\mathbb\{E\}S^\{4\}=v\_\{0\}^\{4\}\+6v\_\{0\}^\{2\}\\\|v^\{\\prime\}\\\|\_\{2\}^\{2\}\+3\\\|v^\{\\prime\}\\\|\_\{2\}^\{4\}\-2\\sum\_\{\\ell=1\}^\{p\-1\}v\_\{\\ell\}^\{4\}\\leq 3\.Paley–Zygmund applied toS2S^\{2\}gives

ℙ⁡\(\|⟨a,v⟩\|≥1/2\)≥1/12\.\\mathbb\{P\}\\bigl\(\|\\langle a,v\\rangle\|\\geq 1/\\sqrt\{2\}\\bigr\)\\geq 1/12\.\(F\.3\)The class of two\-sided homogeneous slabs

\{x:\|⟨x,v⟩\|≥‖v‖2/2\},v≠0,\\bigl\\\{x:\|\\langle x,v\\rangle\|\\geq\\\|v\\\|\_\{2\}/\\sqrt\{2\}\\bigr\\\},\\qquad v\\neq 0,has VC dimension at mostC0​pC\_\{0\}p\. Indeed, it is a subclass of unions of two affine halfspaces\. OnNNpoints the halfspace growth function is at most\(e​N/\(p\+1\)\)p\+1\(eN/\(p\+1\)\)^\{p\+1\}by Sauer’s lemma, so the growth function of two\-fold unions is at most its square\. For a sufficiently large numericalC0C\_\{0\}, this is smaller than2N2^\{N\}wheneverN\>C0​pN\>C\_\{0\}p, proving the claim\. We use the following explicit form of the VC uniform law\([Boucheron et al\., 2013](https://arxiv.org/html/2609.03504#bib.bib27)\)\. For a class of sets with VC dimensionvvandM≥vM\\geq v, symmetrization, Hoeffding’s inequality, and Sauer’s lemma give

ℙ\{supC\|μM\(C\)−μ\(C\)\|\>r\}≤8\(2​e​Mv\)ve−Mr2/32\.\\mathbb\{P\}\\left\\\{\\sup\_\{C\}\|\\mu\_\{M\}\(C\)\-\\mu\(C\)\|\>r\\right\\\}\\leq 8\\left\(\\frac\{2eM\}\{v\}\\right\)^\{v\}e^\{\-Mr^\{2\}/32\}\.Takev=C0​pv=C\_\{0\}pandr=1/24r=1/24\. SinceM=p4M=p^\{4\}, the right side is at moste−c​Me^\{\-cM\}for all sufficiently largepp\. Combining this event with \([F\.3](https://arxiv.org/html/2609.03504#A6.E3)\) gives

infv≠01M​\|\{j:\|⟨aj,v⟩\|≥‖v‖2/2\}\|≥1/24\.\\inf\_\{v\\neq 0\}\\frac\{1\}\{M\}\\left\|\\left\\\{j:\|\\langle a\_\{j\},v\\rangle\|\\geq\\\|v\\\|\_\{2\}/\\sqrt\{2\}\\right\\\}\\right\|\\geq 1/24\.\(F\.4\)

### F\.3All small row submatrices are well conditioned

FixD⊆\[M\]D\\subseteq\[M\]withs=\|D\|s=\|D\|and writeΞD∈ℝ\(p−1\)×s\\Xi\_\{D\}\\in\\mathbb\{R\}^\{\(p\-1\)\\times s\}for the matrix whose columns areξj\\xi\_\{j\},j∈Dj\\in D\. For fixedx∈𝕊s−1x\\in\\mathbb\{S\}^\{s\-1\}, the coordinatesYℓ=∑j∈Dxj​ξj​ℓY\_\{\\ell\}=\\sum\_\{j\\in D\}x\_\{j\}\\xi\_\{j\\ell\}ofΞD​x\\Xi\_\{D\}xare independent, mean\-zero, and variance\-one\. Hoeffding’s lemma gives‖Yℓ‖ψ2≤C​‖x‖2=C\\\|Y\_\{\\ell\}\\\|\_\{\\psi\_\{2\}\}\\leq C\\\|x\\\|\_\{2\}=C, so‖Yℓ2−1‖ψ1≤C′\\\|Y\_\{\\ell\}^\{2\}\-1\\\|\_\{\\psi\_\{1\}\}\\leq C^\{\\prime\}\. Bernstein’s inequality for these centered squared values gives

ℙ⁡\(\|‖ΞD​x‖22−\(p−1\)\|\>\(p−1\)/2\)≤2​e−c​p\.\\mathbb\{P\}\\left\(\\left\|\\\|\\Xi\_\{D\}x\\\|\_\{2\}^\{2\}\-\(p\-1\)\\right\|\>\(p\-1\)/2\\right\)\\leq 2e^\{\-cp\}\.\(F\.5\)A1/81/8\-net𝒩\\mathcal\{N\}of𝕊s−1\\mathbb\{S\}^\{s\-1\}has cardinality at most17s17^\{s\}\([Vershynin, 2018](https://arxiv.org/html/2609.03504#bib.bib28)\)\. To spell out the net step, putH=ΞD⊤​ΞD−\(p−1\)​IsH=\\Xi\_\{D\}^\{\\top\}\\Xi\_\{D\}\-\(p\-1\)I\_\{s\}\. For every symmetricHHand everyε\\varepsilon\-net withε<1/2\\varepsilon<1/2,

‖H‖op≤11−2​ε​maxx∈𝒩​\|x⊤​H​x\|\.\\\|H\\\|\_\{\\mathrm\{op\}\}\\leq\\frac\{1\}\{1\-2\\varepsilon\}\\max\_\{x\\in\\mathcal\{N\}\}\|x^\{\\top\}Hx\|\.This follows by choosing, for a maximizing unit vectoryy, a net pointxxwith‖x−y‖≤ε\\\|x\-y\\\|\\leq\\varepsilonand bounding\|y⊤​H​y−x⊤​H​x\|≤2​ε​‖H‖op\|y^\{\\top\}Hy\-x^\{\\top\}Hx\|\\leq 2\\varepsilon\\\|H\\\|\_\{\\mathrm\{op\}\}\. Apply \([F\.5](https://arxiv.org/html/2609.03504#A6.E5)\) to everyx∈𝒩x\\in\\mathcal\{N\}\. On the resulting event, the last display withε=1/8\\varepsilon=1/8puts all eigenvalues ofΞD⊤​ΞD\\Xi\_\{D\}^\{\\top\}\\Xi\_\{D\}between absolute multiples ofpp\. Hence

ℙ⁡\(c​p​Is⋠ΞD⊤​ΞD​or​ΞD⊤​ΞD⋠C​p​Is\)≤2​exp⁡\(−c′​p\+C​s\)\.\\mathbb\{P\}\\left\(cpI\_\{s\}\\npreceq\\Xi\_\{D\}^\{\\top\}\\Xi\_\{D\}\\text\{ or \}\\Xi\_\{D\}^\{\\top\}\\Xi\_\{D\}\\npreceq CpI\_\{s\}\\right\)\\leq 2\\exp\(\-c^\{\\prime\}p\+Cs\)\.\(F\.6\)There are at most\(e​M/s\)s\(eM/s\)^\{s\}subsets of cardinalityss\. Thus the total failure probability for all sets of a fixed sizessis at most

2​exp⁡\{−c′​p\+C​s\+s​log⁡\(e​M/s\)\}\.2\\exp\\\{\-c^\{\\prime\}p\+Cs\+s\\log\(eM/s\)\\\}\.ForM=p4M=p^\{4\}ands≤smax=⌊c0​p/log⁡p⌋s\\leq s\_\{\\max\}=\\lfloor c\_\{0\}p/\\log p\\rfloor, the two positive terms are at most6​c0​p6c\_\{0\}pfor largepp\. Choosec0<c′/12c\_\{0\}<c^\{\\prime\}/12\. The failure probability for each sizes≤smaxs\\leq s\_\{\\max\}is then at most2e−c′p/22e^\{\-c^\{\\prime\}p/2\}, and summing over the at mostsmax≤ps\_\{\\max\}\\leq ppossible sizes gives

2smaxe−c′p/2≤e−c′′​p2s\_\{\\max\}e^\{\-c^\{\\prime\}p/2\}\\leq e^\{\-c^\{\\prime\\prime\}p\}for all sufficiently largepp\. Thus, with probability at least1−e−c′′​p1\-e^\{\-c^\{\\prime\\prime\}p\},

c​p​I\|D\|⪯ΞD⊤​ΞD⪯C​p​I\|D\|for every​\|D\|≤c0​p/log⁡p,cpI\_\{\|D\|\}\\preceq\\Xi\_\{D\}^\{\\top\}\\Xi\_\{D\}\\preceq CpI\_\{\|D\|\}\\qquad\\text\{for every \}\|D\|\\leq c\_\{0\}p/\\log p,\(F\.7\)
LetADA\_\{D\}be the matrix with rowsaj⊤a\_\{j\}^\{\\top\},j∈Dj\\in D\. Forx∈ℝDx\\in\\mathbb\{R\}^\{D\},

‖AD⊤​x‖22=\(𝟏⊤​x\)2\+‖ΞD​x‖22\.\\\|A\_\{D\}^\{\\top\}x\\\|\_\{2\}^\{2\}=\(\\mathbf\{1\}^\{\\top\}x\)^\{2\}\+\\\|\\Xi\_\{D\}x\\\|\_\{2\}^\{2\}\.The lower inequality in \([F\.7](https://arxiv.org/html/2609.03504#A6.E7)\) is unchanged, while\(𝟏⊤​x\)2≤s​‖x‖22≤c0​p​‖x‖22/log⁡p\(\\mathbf\{1\}^\{\\top\}x\)^\{2\}\\leq s\\\|x\\\|\_\{2\}^\{2\}\\leq c\_\{0\}p\\\|x\\\|\_\{2\}^\{2\}/\\log p\. Thus \([F\.7](https://arxiv.org/html/2609.03504#A6.E7)\) implies

c​p​I\|D\|⪯AD​AD⊤⪯C​p​I\|D\|cpI\_\{\|D\|\}\\preceq A\_\{D\}A\_\{D\}^\{\\top\}\\preceq CpI\_\{\|D\|\}\(F\.8\)for all suchDD\.

### F\.4Whitening

The covariance, slab, and restricted\-Gram failure probabilities are at most2​p​e−c​p32pe^\{\-cp^\{3\}\},e−c​p4e^\{\-cp^\{4\}\}, ande−c′′​pe^\{\-c^\{\\prime\\prime\}p\}, respectively\. Their sum is below one for all sufficiently largepp\. Fix a realization on the three events and define

bj=Σ−1/2aj,u⋆=Σ1/2e0\.b\_\{j\}=\\Sigma^\{\-1/2\}a\_\{j\},\\qquad u\_\{\\star\}=\\Sigma^\{1/2\}e\_\{0\}\.Then

1M​∑jbj​bj⊤=Ip\.\\frac\{1\}\{M\}\\sum\_\{j\}b\_\{j\}b\_\{j\}^\{\\top\}=I\_\{p\}\.Also

‖u⋆‖22=e0⊤​Σ​e0=1,⟨bj,u⋆⟩=⟨aj,e0⟩=1\.\\\|u\_\{\\star\}\\\|\_\{2\}^\{2\}=e\_\{0\}^\{\\top\}\\Sigma e\_\{0\}=1,\\qquad\\langle b\_\{j\},u\_\{\\star\}\\rangle=\\langle a\_\{j\},e\_\{0\}\\rangle=1\.For a unit vectorvv, setq=Σ−1/2vq=\\Sigma^\{\-1/2\}v\. By \([F\.2](https://arxiv.org/html/2609.03504#A6.E2)\),‖q‖2≥4/5\\\|q\\\|\_\{2\}\\geq\\sqrt\{4/5\}\. Applying \([F\.4](https://arxiv.org/html/2609.03504#A6.E4)\) toqqgives at leastM/24M/24indices with

\|⟨bj,v⟩\|=\|⟨aj,q⟩\|≥‖q‖2/2≥2/5\.\|\\langle b\_\{j\},v\\rangle\|=\|\\langle a\_\{j\},q\\rangle\|\\geq\\\|q\\\|\_\{2\}/\\sqrt\{2\}\\geq\\sqrt\{2/5\}\.Thus one may takea0=1/2a\_\{0\}=1/2andb0=1/24b\_\{0\}=1/24\. Finally,

BD​BD⊤=AD​Σ−1​AD⊤,B\_\{D\}B\_\{D\}^\{\\top\}=A\_\{D\}\\Sigma^\{\-1\}A\_\{D\}^\{\\top\},and \([F\.2](https://arxiv.org/html/2609.03504#A6.E2)\), \([F\.8](https://arxiv.org/html/2609.03504#A6.E8)\) give \([16](https://arxiv.org/html/2609.03504#S5.E16)\)\. ∎

## Appendix GThe isotropic separation

###### Proof\.

Fix the frame from[Lemma6](https://arxiv.org/html/2609.03504#Thmtheorem6), choose the theorem constantc≤c0c\\leq c\_\{0\}, and assume1≤k≤c​p/log⁡p1\\leq k\\leq cp/\\log p\. Throughout this proof,D⊆\[M\]D\\subseteq\[M\]ranges only over\|D\|≤k\|D\|\\leq k, andBDB\_\{D\}denotes the corresponding row submatrix\. IfD≠∅D\\neq\\varnothing, \([16](https://arxiv.org/html/2609.03504#S5.E16)\) makesGD=BD​BD⊤G\_\{D\}=B\_\{D\}B\_\{D\}^\{\\top\}positive definite, and we set

PD=BD⊤​GD−1​BD\.P\_\{D\}=B\_\{D\}^\{\\top\}G\_\{D\}^\{\-1\}B\_\{D\}\.ForD=∅D=\\varnothing, setPD=0P\_\{D\}=0andsD=0s\_\{D\}=0\. In either casePDP\_\{D\}is the orthogonal projector onto the row span ofBDB\_\{D\}\. We first quantify the normalized residualuDu\_\{D\}, then control its generated cone, and finally verify the distributional claims\. SinceBD​u⋆=𝟏B\_\{D\}u\_\{\\star\}=\\mathbf\{1\}for nonemptyDD,

‖PD​u⋆‖22=𝟏⊤​GD−1​𝟏\.\\\|P\_\{D\}u\_\{\\star\}\\\|\_\{2\}^\{2\}=\\mathbf\{1\}^\{\\top\}G\_\{D\}^\{\-1\}\\mathbf\{1\}\.\(G\.1\)The Gram bounds imply, ford=\|D\|≥1d=\|D\|\\geq 1,

dC1​p≤sD2:⁣=∥PDu⋆∥22=𝟏⊤GD−1𝟏≤dc1​p\.\\frac\{d\}\{C\_\{1\}p\}\\leq s\_\{D\}^\{2\}\\mathrel\{:=\}\\\|P\_\{D\}u\_\{\\star\}\\\|\_\{2\}^\{2\}=\\mathbf\{1\}^\{\\top\}G\_\{D\}^\{\-1\}\\mathbf\{1\}\\leq\\frac\{d\}\{c\_\{1\}p\}\.\(G\.2\)ForD=∅D=\\varnothing, the same bounds hold withd=sD=0d=s\_\{D\}=0\. For all sufficiently largepp, the upper bound is at mostc/\(c1​log⁡p\)≤1/2c/\(c\_\{1\}\\log p\)\\leq 1/2\. Thus\(I−PD\)​u⋆≠0\(I\-P\_\{D\}\)u\_\{\\star\}\\neq 0and everyuDu\_\{D\}used in the construction is well defined\.

Since\(I−PD\)​u⋆\(I\-P\_\{D\}\)u\_\{\\star\}is orthogonal toPD​u⋆P\_\{D\}u\_\{\\star\},

⟨uD,u⋆⟩=1−sD2\\langle u\_\{D\},u\_\{\\star\}\\rangle=\\sqrt\{1\-s\_\{D\}^\{2\}\}and

‖uD−u⋆‖22=2​\(1−1−sD2\)=2​sD21\+1−sD2\.\\\|u\_\{D\}\-u\_\{\\star\}\\\|\_\{2\}^\{2\}=2\\left\(1\-\\sqrt\{1\-s\_\{D\}^\{2\}\}\\right\)=\\frac\{2s\_\{D\}^\{2\}\}\{1\+\\sqrt\{1\-s\_\{D\}^\{2\}\}\}\.\(G\.3\)In particular,sD2≤‖uD−u⋆‖22≤2​sD2s\_\{D\}^\{2\}\\leq\\\|u\_\{D\}\-u\_\{\\star\}\\\|\_\{2\}^\{2\}\\leq 2s\_\{D\}^\{2\}whensD2≤1/2s\_\{D\}^\{2\}\\leq 1/2, so \([G\.2](https://arxiv.org/html/2609.03504#A7.E2)\) gives‖uD−u⋆‖22≍d/p\\\|u\_\{D\}\-u\_\{\\star\}\\\|\_\{2\}^\{2\}\\asymp d/pwith explicit absolute constants\. AlsoBD​uD=0B\_\{D\}u\_\{D\}=0\.

### G\.1Geometry and width of the cone

Let

𝒰p,k=\{uD:\|D\|≤k\}\.\\mathcal\{U\}\_\{p,k\}=\\\{u\_\{D\}:\|D\|\\leq k\\\}\.Its cardinality satisfies

\|𝒰p,k\|≤∑d=0k\(Md\)≤2​\(e​Mk\)k\|\\mathcal\{U\}\_\{p,k\}\|\\leq\\sum\_\{d=0\}^\{k\}\\binom\{M\}\{d\}\\leq 2\\left\(\\frac\{eM\}\{k\}\\right\)^\{k\}\(G\.4\)for1≤k≤M/21\\leq k\\leq M/2\. By \([G\.3](https://arxiv.org/html/2609.03504#A7.E3)\), all generators lie in a cap of radius

aboutu⋆u\_\{\\star\}\. Sincek≤c​p/log⁡pk\\leq cp/\\log p, choosingccsmall andpplarge ensuresr<1r<1, as required by[Lemma13](https://arxiv.org/html/2609.03504#Thmtheorem13)\. Applying that lemma withM=p4M=p^\{4\}gives

w⁡\(Ap,k\)\\displaystyle w\(A\_\{p,k\}\)≤C​kp​k​log⁡\(e​M/k\)\+C​kp\\displaystyle\\leq C\\sqrt\{\\frac\{k\}\{p\}\}\\sqrt\{k\\log\(eM/k\)\}\+C\\frac\{k\}\{\\sqrt\{p\}\}≤C⁡\[k​log⁡pp\+kp\]\.\\displaystyle\\leq C\\left\[k\\sqrt\{\\frac\{\\log p\}\{p\}\}\+\\frac\{k\}\{\\sqrt\{p\}\}\\right\]\.
The cone is full dimensional\. Indeed,u∅=u⋆u\_\{\\varnothing\}=u\_\{\\star\}, and forD=\{j\}D=\\\{j\\\}the vectoru\{j\}u\_\{\\\{j\\\}\}is a nonzero normalization of

u⋆−1‖bj‖22​bj\.u\_\{\\star\}\-\\frac\{1\}\{\\\|b\_\{j\}\\\|\_\{2\}^\{2\}\}b\_\{j\}\.Thus everybjb\_\{j\}belongs to the linear span ofu⋆u\_\{\\star\}andu\{j\}u\_\{\\\{j\\\}\}\. The tight\-frame identity implies that thebjb\_\{j\}spanℝp\\mathbb\{R\}^\{p\}\. The cone is pointed because

inf\|D\|≤k⟨uD,u⋆⟩≥1/2\>0\.\\inf\_\{\|D\|\\leq k\}\\langle u\_\{D\},u\_\{\\star\}\\rangle\\geq 1/\\sqrt\{2\}\>0\.It is polyhedral because it has finitely many generators\.[Lemma14](https://arxiv.org/html/2609.03504#Thmtheorem14)therefore realizes it as the descent cone of a polyhedral norm\.

### G\.2Heavy\-tailed design

LetJJbe uniform on\[M\]\[M\], letσ\\sigmabe a Rademacher sign independent of\(J,L\)\(J,L\), and set

ρ=L/𝔼​L2,Z𝖧=σ​ρ​bJ\.\\rho=L/\\sqrt\{\\mathbb\{E\}L^\{2\}\},\\qquad Z\_\{\\mathsf\{H\}\}=\\sigma\\rho b\_\{J\}\.Then

𝔼​Z𝖧=0,𝔼​Z𝖧​Z𝖧⊤=𝔼​ρ2​1M​∑jbj​bj⊤=Ip\.\\mathbb\{E\}Z\_\{\\mathsf\{H\}\}=0,\\qquad\\mathbb\{E\}Z\_\{\\mathsf\{H\}\}Z\_\{\\mathsf\{H\}\}^\{\\top\}=\\mathbb\{E\}\\rho^\{2\}\\frac\{1\}\{M\}\\sum\_\{j\}b\_\{j\}b\_\{j\}^\{\\top\}=I\_\{p\}\.Sinceρ≥\(𝔼L2\)−1/2\\rho\\geq\(\\mathbb\{E\}L^\{2\}\)^\{\-1/2\}and the slab property in \([15](https://arxiv.org/html/2609.03504#S5.E15)\) holds,

infv∈𝕊p−1ℙ⁡\(\|⟨Z𝖧,v⟩\|≥a0/𝔼​L2\)≥b0\.\\inf\_\{v\\in\\mathbb\{S\}^\{p\-1\}\}\\mathbb\{P\}\\left\(\|\\langle Z\_\{\\mathsf\{H\}\},v\\rangle\|\\geq a\_\{0\}/\\sqrt\{\\mathbb\{E\}L^\{2\}\}\\right\)\\geq b\_\{0\}\.For the Gaussian law,⟨G,v⟩∼𝖭⁡\(0,1\)\\langle G,v\\rangle\\sim\\mathsf\{N\}\(0,1\)for every unitvv\. Thus the explicit common choice

α0=min⁡\{a0𝔼​L2,12\},β0=min⁡\{b0,ℙ⁡\(\|G1\|≥α0\)\}\\alpha\_\{0\}=\\min\\left\\\{\\frac\{a\_\{0\}\}\{\\sqrt\{\\mathbb\{E\}L^\{2\}\}\},\\frac\{1\}\{2\}\\right\\\},\\qquad\\beta\_\{0\}=\\min\\left\\\{b\_\{0\},\\mathbb\{P\}\(\|G\_\{1\}\|\\geq\\alpha\_\{0\}\)\\right\\\}gives \([18](https://arxiv.org/html/2609.03504#S5.E18)\) for both designs\.

The law ofZ𝖧Z\_\{\\mathsf\{H\}\}has finite moments of every order\. Ifv≠0v\\neq 0, the tight\-frame identity gives

1M​∑j⟨bj,v⟩2=‖v‖22\>0,\\frac\{1\}\{M\}\\sum\_\{j\}\\langle b\_\{j\},v\\rangle^\{2\}=\\\|v\\\|\_\{2\}^\{2\}\>0,so some row type has nonzero inner product withvv\. Conditioning on that type shows

𝔼​es​\|⟨Z𝖧,v⟩\|=∞\(s\>0\)\.\\mathbb\{E\}e^\{s\|\\langle Z\_\{\\mathsf\{H\}\},v\\rangle\|\}=\\infty\\qquad\(s\>0\)\.
Given any sample of sizen≤kn\\leq k, letDDbe the set of distinct values amongJ1,…,JnJ\_\{1\},\\ldots,J\_\{n\}\. ThenuD∈Ap,ku\_\{D\}\\in A\_\{p,k\}and

⟨Z𝖧,i,uD⟩=σi​ρi​⟨bJi,uD⟩=0\\langle Z\_\{\\mathsf\{H\},i\},u\_\{D\}\\rangle=\\sigma\_\{i\}\\rho\_\{i\}\\langle b\_\{J\_\{i\}\},u\_\{D\}\\rangle=0for everyii\. This proves deterministic failure\. The Gaussian claim follows directly from \([A\.1](https://arxiv.org/html/2609.03504#A1.E1)\)\.

### G\.3Constant\-width Gaussian specialization

Fix a sufficiently small absolutea\>0a\>0and take

k=⌊a​plog⁡p⌋\.k=\\left\\lfloor a\\sqrt\{\\frac\{p\}\{\\log p\}\}\\right\\rfloor\.For all sufficiently largepp, thiskkis admissible in[Theorem7](https://arxiv.org/html/2609.03504#Thmtheorem7), and \([17](https://arxiv.org/html/2609.03504#S5.E17)\) gives

w⁡\(Ap,k\)≤C⁡\(a\+alog⁡p\)≤C⋆w\(A\_\{p,k\}\)\\leq C\\left\(a\+\\frac\{a\}\{\\sqrt\{\\log p\}\}\\right\)\\leq C\_\{\\star\}for an absoluteC⋆C\_\{\\star\}\. Lett=2​log⁡\(1/δ\)t=\\sqrt\{2\\log\(1/\\delta\)\}\. If

n≥max⁡\{2,16​C⋆2,32​log⁡\(1/δ\)\},n\\geq\\max\\\{2,16C\_\{\\star\}^\{2\},32\\log\(1/\\delta\)\\\},thenn−1≥n/2\\sqrt\{n\-1\}\\geq\\sqrt\{n/2\},C⋆≤n/4C\_\{\\star\}\\leq\\sqrt\{n\}/4, andt≤n/4t\\leq\\sqrt\{n\}/4\. Therefore \([19](https://arxiv.org/html/2609.03504#S5.E19)\) yields

1n​infu∈Ap,k‖X𝖦​u‖2≥12−12=:c⋆\>0\\frac\{1\}\{\\sqrt\{n\}\}\\inf\_\{u\\in A\_\{p,k\}\}\\\|X\_\{\\mathsf\{G\}\}u\\\|\_\{2\}\\geq\\frac\{1\}\{\\sqrt\{2\}\}\-\\frac\{1\}\{2\}=:c\_\{\\star\}\>0with probability at least1−δ1\-\\delta\. HenceΛn​\(X𝖦,Ap,k\)≥c⋆2\\Lambda\_\{n\}\(X\_\{\\mathsf\{G\}\};A\_\{p,k\}\)\\geq c\_\{\\star\}^\{2\}\. Enlarging one universal constant converts the displayed condition onnnton≥CG​\[1\+log⁡\(1/δ\)\]n\\geq C\_\{G\}\[1\+\\log\(1/\\delta\)\]\. The heavy\-tailed failure holds on every path forn≤kn\\leq k, and, after reducingaaby a factor of two to absorb the floor,k≥cH​p/log⁡pk\\geq c\_\{H\}\\sqrt\{p/\\log p\}\. This proves[Corollary8](https://arxiv.org/html/2609.03504#Thmtheorem8)\.

### G\.4Radius and affine dimension

The radius upper bound follows from \([A\.3](https://arxiv.org/html/2609.03504#A1.E3)\):

r⁡\(Ap,k\)≤C​k/p\.r\(A\_\{p,k\}\)\\leq C\\sqrt\{k/p\}\.Choose a setDDof cardinalitykk\. By \([G\.3](https://arxiv.org/html/2609.03504#A7.E3)\),

‖uD−u⋆‖2≥c​k/p,\\\|u\_\{D\}\-u\_\{\\star\}\\\|\_\{2\}\\geq c\\sqrt\{k/p\},so every enclosing ball has radius at least half this distance\. Therefore

r​\(Ap,k\)2≍k/p\.r\(A\_\{p,k\}\)^\{2\}\\asymp k/p\.The coneCp,kC\_\{p,k\}is full dimensional\. Its intersection with the sphere therefore contains a nonempty open spherical patch\. If this patch lay in a proper affine hyperplane\{x:⟨a,x⟩=b\}\\\{x:\\langle a,x\\rangle=b\\\}, then the affine functionx↦⟨a,x⟩−bx\\mapsto\\langle a,x\\rangle\-bwould vanish on an open subset of the sphere\. Differentiating along all tangent directions on that subset forcesaato be parallel to every point in the patch, which is impossible unlessa=0a=0and thenb=0b=0\. Hence no proper affine hyperplane contains the patch, andq⁡\(Ap,k\)=pq\(A\_\{p,k\}\)=p\. ∎

## Appendix HSmooth\-density robustness

###### Proof\.

The convolution in \([20](https://arxiv.org/html/2609.03504#S5.E20)\) is centered and isotropic\. Writecτ=1\+τ2c\_\{\\tau\}=\\sqrt\{1\+\\tau^\{2\}\}and letϕτ\\phi\_\{\\tau\}be the density ofτ​H\\tau H\. The smoothed row has density

fτ​\(x\)=cτp​𝔼​ϕτ​\(cτ​x−Z𝖧\),f\_\{\\tau\}\(x\)=c\_\{\\tau\}^\{p\}\\mathbb\{E\}\\phi\_\{\\tau\}\(c\_\{\\tau\}x\-Z\_\{\\mathsf\{H\}\}\),which is strictly positive for everyx∈ℝpx\\in\\mathbb\{R\}^\{p\}\. Every derivative of a Gaussian density is a polynomial times that density and is bounded onℝp\\mathbb\{R\}^\{p\}\. Dominated differentiation under the expectation therefore givesfτ∈C∞​\(ℝp\)f\_\{\\tau\}\\in C^\{\\infty\}\(\\mathbb\{R\}^\{p\}\)\. Polynomial moments remain finite\.

We also verify the stronger directional heavy\-tail claim\. Fixv≠0v\\neq 0\. Tightness of the frame provides ajjwithcj=⟨bj,v⟩≠0c\_\{j\}=\\langle b\_\{j\},v\\rangle\\neq 0\. Conditional onJ=jJ=j, and on the independent event\|τ​⟨H,v⟩\|≤1\|\\tau\\langle H,v\\rangle\|\\leq 1, which has positive probability,

\|σ​ρ​cj\+τ⁡⟨H,v⟩\|≥\|cj\|​ρ−1\.\|\\sigma\\rho c\_\{j\}\+\\tau\\langle H,v\\rangle\|\\geq\|c\_\{j\}\|\\rho\-1\.The event is independent ofρ\\rho\. Hence, after the harmless factor1/1\+τ21/\\sqrt\{1\+\\tau^\{2\}\}, every positive exponential moment of\|⟨Z𝖧,τ,v⟩\|\|\\langle Z\_\{\\mathsf\{H\},\\tau\},v\\rangle\|is infinite\.

Letα0,β0\\alpha\_\{0\},\\beta\_\{0\}be global small\-ball constants forZ𝖧Z\_\{\\mathsf\{H\}\}\. Chooseτ0\>0\\tau\_\{0\}\>0such that

ℙ⁡\(\|τ​H1\|≤α0/2\)≥1/2\(0<τ≤τ0\)\.\\mathbb\{P\}\(\|\\tau H\_\{1\}\|\\leq\\alpha\_\{0\}/2\)\\geq 1/2\\qquad\(0<\\tau\\leq\\tau\_\{0\}\)\.For a unitvv, the heavy and Gaussian components are independent\. On the event

\|⟨Z𝖧,v⟩\|≥α0,\|τ⁡⟨H,v⟩\|≤α0/2,\|\\langle Z\_\{\\mathsf\{H\}\},v\\rangle\|\\geq\\alpha\_\{0\},\\qquad\|\\tau\\langle H,v\\rangle\|\\leq\\alpha\_\{0\}/2,one has

\|⟨Z𝖧,τ,v⟩\|≥α02​1\+τ02\.\|\\langle Z\_\{\\mathsf\{H\},\\tau\},v\\rangle\|\\geq\\frac\{\\alpha\_\{0\}\}\{2\\sqrt\{1\+\\tau\_\{0\}^\{2\}\}\}\.Thus one may takeα¯=α0/\(2​1\+τ02\)\\bar\{\\alpha\}=\\alpha\_\{0\}/\(2\\sqrt\{1\+\\tau\_\{0\}^\{2\}\}\)andβ¯=β0/2\\bar\{\\beta\}=\\beta\_\{0\}/2\.

For each fixed sample sizen≤kn\\leq k, letDDbe its latent row\-type set\. The directionuDu\_\{D\}depends only on theJiJ\_\{i\}and is independent of the Gaussian perturbations\. Since the heavy component is annihilated,

Λn​\(X𝖧,τ,Ap,k\)≤1n​∑i=1n⟨Z𝖧,τ,i,uD⟩2=τ21\+τ2​1n​∑i=1n⟨Hi,uD⟩2\.\\Lambda\_\{n\}\(X\_\{\\mathsf\{H\},\\tau\};A\_\{p,k\}\)\\leq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\langle Z\_\{\\mathsf\{H\},\\tau,i\},u\_\{D\}\\rangle^\{2\}=\\frac\{\\tau^\{2\}\}\{1\+\\tau^\{2\}\}\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\langle H\_\{i\},u\_\{D\}\\rangle^\{2\}\.Conditionally on\(J1,…,Jn\)\(J\_\{1\},\\ldots,J\_\{n\}\), the final sum has theχn2\\chi\_\{n\}^\{2\}law\. Thusχn2≤2​n\\chi\_\{n\}^\{2\}\\leq 2nimpliesΛn≤2​τ2\\Lambda\_\{n\}\\leq 2\\tau^\{2\}\. For completeness, Markov’s inequality and𝔼​eχn2/4=2n/2\\mathbb\{E\}e^\{\\chi\_\{n\}^\{2\}/4\}=2^\{n/2\}give

ℙ\(χn2\>2n\)≤e−n/22n/2=exp\[−1−log⁡22n\]\.\\mathbb\{P\}\(\\chi\_\{n\}^\{2\}\>2n\)\\leq e^\{\-n/2\}2^\{n/2\}=\\exp\\left\[\-\\frac\{1\-\\log 2\}\{2\}n\\right\]\.This proves \([21](https://arxiv.org/html/2609.03504#S5.E21)\) withcs=\(1−log⁡2\)/2c\_\{s\}=\(1\-\\log 2\)/2\. ∎

## Appendix IThe dimension–radius bound

###### Proof\.

Choose a countable dense subsetA0⊆AA\_\{0\}\\subseteq A\. For every matrixXXand everyh∈ℝph\\in\\mathbb\{R\}^\{p\}, continuity gives

infu∈A0‖X​u‖2=infu∈A‖X​u‖2,supu∈A0⟨h,u⟩=supu∈A⟨h,u⟩\.\\inf\_\{u\\in A\_\{0\}\}\\\|Xu\\\|\_\{2\}=\\inf\_\{u\\in A\}\\\|Xu\\\|\_\{2\},\\qquad\\sup\_\{u\\in A\_\{0\}\}\\langle h,u\\rangle=\\sup\_\{u\\in A\}\\langle h,u\\rangle\.Moreover,𝖰α​\(P,A0\)≥𝖰α​\(P,A\)≥β\\mathsf\{Q\}\_\{\\alpha\}\(P,A\_\{0\}\)\\geq\\mathsf\{Q\}\_\{\\alpha\}\(P,A\)\\geq\\beta\. We may therefore apply the countable, measurable form of the small\-ball lemma toA0A\_\{0\}; the displayed identities transfer its conclusion back toAA\.

BecauseAAis bounded and the ambient space is finite dimensional, the continuous coercive functiona↦supu∈A‖u−a‖2a\\mapsto\\sup\_\{u\\in A\}\\\|u\-a\\\|\_\{2\}attains its minimum \(passing to the closure ofAAdoes not change the supremum\)\. Orthogonally projecting any minimizer ontoaff⁡\(A\)\\operatorname\{aff\}\(A\)cannot increase its distance to anyu∈Au\\in A\. We may therefore choose a minimum enclosing centera∈aff⁡\(A\)a\\in\\operatorname\{aff\}\(A\)\. Let

LA=span⁡\(A−a\),dimLA=q⁡\(A\)\.L\_\{A\}=\\operatorname\{span\}\(A\-a\),\\qquad\\dim L\_\{A\}=q\(A\)\.For

Hn=1n​∑i=1nεi​Zi,H\_\{n\}=\\frac\{1\}\{\\sqrt\{n\}\}\\sum\_\{i=1\}^\{n\}\\varepsilon\_\{i\}Z\_\{i\},the Rademacher signs give𝔼​Hn=0\\mathbb\{E\}H\_\{n\}=0\. For each realization,supu∈A⟨Hn,u⟩=⟨Hn,a⟩\+supu∈A⟨Hn,u−a⟩\\sup\_\{u\\in A\}\\langle H\_\{n\},u\\rangle=\\langle H\_\{n\},a\\rangle\+\\sup\_\{u\\in A\}\\langle H\_\{n\},u\-a\\rangle, and𝔼​⟨Hn,a⟩=0\\mathbb\{E\}\\langle H\_\{n\},a\\rangle=0\. Hence

Wn​\(A,P\)\\displaystyle W\_\{n\}\(A;P\)=𝔼​supu∈A⟨Hn,u⟩=𝔼​supu∈A⟨Hn,u−a⟩\\displaystyle=\\mathbb\{E\}\\sup\_\{u\\in A\}\\langle H\_\{n\},u\\rangle=\\mathbb\{E\}\\sup\_\{u\\in A\}\\langle H\_\{n\},u\-a\\rangle≤r⁡\(A\)​𝔼​‖PLA​Hn‖2\\displaystyle\\leq r\(A\)\\mathbb\{E\}\\\|P\_\{L\_\{A\}\}H\_\{n\}\\\|\_\{2\}≤r⁡\(A\)​𝔼​‖PLA​Hn‖22\.\\displaystyle\\leq r\(A\)\\sqrt\{\\mathbb\{E\}\\\|P\_\{L\_\{A\}\}H\_\{n\}\\\|\_\{2\}^\{2\}\}\.Isotropy gives𝔼​Hn​Hn⊤=Ip\\mathbb\{E\}H\_\{n\}H\_\{n\}^\{\\top\}=I\_\{p\}, and therefore

𝔼​‖PLA​Hn‖22=tr⁡\(PLA\)=q⁡\(A\)\.\\mathbb\{E\}\\\|P\_\{L\_\{A\}\}H\_\{n\}\\\|\_\{2\}^\{2\}=\\operatorname\{tr\}\(P\_\{L\_\{A\}\}\)=q\(A\)\.Thus

Wn​\(A,P\)≤r⁡\(A\)​q⁡\(A\)\.W\_\{n\}\(A;P\)\\leq r\(A\)\\sqrt\{q\(A\)\}\.Apply[Lemma12](https://arxiv.org/html/2609.03504#Thmtheorem12)withξ=α/2\\xi=\\alpha/2\. Since𝖰α​\(P,A\)≥β\\mathsf\{Q\}\_\{\\alpha\}\(P,A\)\\geq\\beta, this yields \([22](https://arxiv.org/html/2609.03504#S5.E22)\)\.

To derive \([23](https://arxiv.org/html/2609.03504#S5.E23)\), chooset=2​log⁡\(1/δ\)t=\\sqrt\{2\\log\(1/\\delta\)\}and require separately

2​r​\(A\)​q⁡\(A\)≤α​β8​n,α​t2≤α​β8​n\.2r\(A\)\\sqrt\{q\(A\)\}\\leq\\frac\{\\alpha\\beta\}\{8\}\\sqrt\{n\},\\qquad\\frac\{\\alpha t\}\{2\}\\leq\\frac\{\\alpha\\beta\}\{8\}\\sqrt\{n\}\.Under the resulting sample\-size condition, the right side of \([22](https://arxiv.org/html/2609.03504#S5.E22)\) is at leastα​β​n/4\\alpha\\beta\\sqrt\{n\}/4, soΛn​\(X,A\)≥α2​β2/16\\Lambda\_\{n\}\(X;A\)\\geq\\alpha^\{2\}\\beta^\{2\}/16\.

Finally, Gaussian width is always at most the dimension–radius scale\. Indeed,

w⁡\(A\)=𝔼​supu∈A⟨g,u−a⟩≤r⁡\(A\)​𝔼​‖PLA​g‖2≤r⁡\(A\)​q⁡\(A\)\.w\(A\)=\\mathbb\{E\}\\sup\_\{u\\in A\}\\langle g,u\-a\\rangle\\leq r\(A\)\\mathbb\{E\}\\\|P\_\{L\_\{A\}\}g\\\|\_\{2\}\\leq r\(A\)\\sqrt\{q\(A\)\}\.The matching identities forAp,kA\_\{p,k\}were proved in the preceding appendix\. ∎

## Appendix JConvex\-recovery consequences

###### Proof\.

SupposeA=𝒟⁡\(ℛ,θ⋆\)∩𝕊p−1A=\\mathcal\{D\}\(\\mathcal\{R\},\\theta^\{\\star\}\)\\cap\\mathbb\{S\}^\{p\-1\}andX​u=0Xu=0for someu∈Au\\in A\. By the definition of the descent cone, there ist\>0t\>0such that

ℛ⁡\(θ⋆\+t​u\)≤ℛ⁡\(θ⋆\)\.\\mathcal\{R\}\(\\theta^\{\\star\}\+tu\)\\leq\\mathcal\{R\}\(\\theta^\{\\star\}\)\.At the same timeX⁡\(θ⋆\+t​u\)=X​θ⋆X\(\\theta^\{\\star\}\+tu\)=X\\theta^\{\\star\}\. Henceθ⋆\\theta^\{\\star\}cannot be the unique solution of \([25](https://arxiv.org/html/2609.03504#S6.E25)\)\. This proves the exact\-recovery statements in[Section6](https://arxiv.org/html/2609.03504#S6)\.

For the smoothed construction, \([21](https://arxiv.org/html/2609.03504#S5.E21)\) supplies a unit descent directionuuwith‖X​u‖2≤2​τ​n\\\|Xu\\\|\_\{2\}\\leq\\sqrt\{2\}\\tau\\sqrt\{n\}\. In normalized units,

κn​\(X,A\):=1n​infv∈A‖X​v‖2=Λn​\(X,A\)≤2​τ\.\\kappa\_\{n\}\(X;A\):=\\frac\{1\}\{\\sqrt\{n\}\}\\inf\_\{v\\in A\}\\\|Xv\\\|\_\{2\}=\\sqrt\{\\Lambda\_\{n\}\(X;A\)\}\\leq\\sqrt\{2\}\\tau\.Equivalently, the realized\-design inverse modulus

Kn​\(X,A\):=1κn​\(X,A\)K\_\{n\}\(X;A\):=\\frac\{1\}\{\\kappa\_\{n\}\(X;A\)\}is at least1/\(2​τ\)1/\(\\sqrt\{2\}\\tau\), with the convention1/0=∞1/0=\\infty, and the quadratic modulus1/Λn1/\\Lambda\_\{n\}is at least1/\(2​τ2\)1/\(2\\tau^\{2\}\)\. This conclusion is deterministic afterXXis realized\. In particular, the witnessuuand a descending comparison pointθ1=θ⋆\+s​u\\theta\_\{1\}=\\theta^\{\\star\}\+sumay depend on that realization\. Their normalized observation distance is at most2​τ​s\\sqrt\{2\}\\tau s, so the statement controls the conditioning of the realized inverse problem; it does not assert a minimax lower bound for two parameters fixed before sampling\. ∎