Theorem 9.4.2 — The bound:
DisprovedHighDimProb.Deviations.m_star_bound_v2This is the bound, a direct geometric consequence of the matrix deviation inequality: the expected diameter of the intersection of a fixed set with a random subspace of codimension at most is controlled by the Gaussian width of .
There is an absolute constant such that the following holds. Let be a bounded set with Gaussian width (gaussianWidth), and let be an random matrix () whose rows are independent, isotropic, sub-gaussian random vectors with , where is the sub-gaussian norm of a random vector (companion definition subgaussianVectorNorm, valued in , finite exactly for sub-gaussian random vectors). Then the random subspace satisfies
the expectation being finite.
Formalization Note. The retired version was disproved because its real-valued sub-gaussian norm returned the junk value for a heavy-tailed row, so an isotropic but non-sub-gaussian row satisfied the hypothesis with and the right-hand side collapsed to . The new statement uses the corrected ℝ≥0∞-valued subgaussianVectorNorm (built on the corrected scalar norm) with (ℝ≥0), so now says that every row is a sub-gaussian random vector with norm at most , as the book's "sub-gaussian random vectors … " does (any upper bound is what the proof uses). Everything else is as before: at a sample point is ; Metric.diam is guarded by Bornology.IsBounded T (an unbounded has , so nothing is lost); is given by an explicit real witness since gaussianWidth is EReal-valued ( makes the book's bound trivial, is degenerate); " is bounded" is stated as Integrable ∧ ∫ ≤ …; because the conclusion divides by (the book's "dividing by "); is existentially quantified before every other object; isotropy is IsIsotropic (Definition 3.2.1 via Lemma 3.2.3).
import Mathlib import Definitions.Def_HighDimProb_Deviations_IsIsotropic import Definitions.Def_HighDimProb_Deviations_SubgaussianVectorNorm_v2 import Definitions.Def_HighDimProb_Deviations_GaussianWidth open MeasureTheory ProbabilityTheory open scoped ENNReal NNReal
namespace HighDimProb.Deviations
/-- **Theorem 9.4.2** (`M*` bound), Vershynin, *High-Dimensional Probability* (2018), p. 241
(PDF p. 249).
"Consider a set `T ⊂ ℝⁿ`. Let `A` be an `m × n` matrix whose rows `Aᵢ` are independent, isotropic
and sub-gaussian random vectors in `ℝⁿ`. Then the random subspace `E = ker A` satisfies
`E diam(T ∩ E) ≤ CK²w(T)/√m`, where `K = maxᵢ‖Aᵢ‖_{ψ2}`."
`ker A` at a sample point `ω` is `{x | ∀ i, ⟨Aᵢ(ω), x⟩ = 0}`; `diam` is `Metric.diam`;
`Bornology.IsBounded T` guards `Metric.diam`'s junk value `0` on unbounded sets (an unbounded `T`
has `w(T) = +∞` anyway, so nothing is lost); `Integrable … ∧ ∫ … ≤ …` states that
`E diam(T ∩ E)` is finite and bounded; `w(T)` is an explicit real witness with
`gaussianWidth T = (w : EReal)`; `hm : 0 < m` because the conclusion divides by `√m` (the book's
"dividing by `√m`" presupposes `m ≥ 1`).
Corrected version (`_v2`): the sub-gaussian bound uses the corrected `ℝ≥0∞`-valued
`subgaussianVectorNorm` (`⊤` for a non-sub-gaussian row) and `K : ℝ≥0`, so
`∀ i, ‖Aᵢ‖_{ψ₂} ≤ K` now states that every row *is* sub-gaussian with norm at most `K`. The
retired version's real-valued norm returned `0` for a heavy-tailed row, so an isotropic
non-sub-gaussian row satisfied the hypothesis with `K = 0` and the right-hand side collapsed to
`0`. -/
theorem m_star_bound_v2 :
∃ C : ℝ, 0 < C ∧
∀ {Ω : Type} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
{m n : ℕ} (hm : 0 < m) (A : Fin m → Ω → EuclideanSpace ℝ (Fin n)),
iIndepFun A P →
(∀ i, IsIsotropic P (A i)) →
∀ (K : ℝ≥0), (∀ i, subgaussianVectorNorm P (A i) ≤ K) →
∀ (T : Set (EuclideanSpace ℝ (Fin n))), Bornology.IsBounded T →
∀ (w : ℝ), gaussianWidth T = (w : EReal) →
Integrable
(fun ω => Metric.diam (T ∩ {x | ∀ i, inner (𝕜 := ℝ) (A i ω) x = 0})) P ∧
∫ ω, Metric.diam (T ∩ {x | ∀ i, inner (𝕜 := ℝ) (A i ω) x = 0}) ∂P ≤
C * K ^ 2 * w / Real.sqrt (m : ℝ) := by sorry
end HighDimProb.Deviations