A tall matrix with independent standard normal entries is, with high probability, a near-isometry: all its singular values lie in up to Gaussian fluctuations. This is Gordon's theorem together with Gaussian concentration (Vershynin 2012, Theorem 5.32 and Corollary 5.35), the non-asymptotic counterpart of the Bai–Yin law and the model result for the whole theory of non-asymptotic random matrices. In randomized numerical linear algebra the same two ingredients give the expected spectral norm of (Halko–Martinsson–Tropp 2011, Proposition 10.1 (10.2)), its second moment (Tropp–Webber 2023, Lemma B.1), and the lower tail of of a Gaussian sketch, which controls the inverse moments that appear in the analysis of sketching algorithms with rank truncation. None of these results is available in Mathlib; this mission proves them.
A standard Gaussian matrix has independent entries; its law is . Its extreme singular values are
the infimum and supremum over the unit sphere of (); is the spectral norm. For a wide matrix , , the usual is . The Frobenius norm is ; a function on matrices is -Lipschitz if . A chi-square variable with degrees of freedom is for independent standard normals . The letter denotes Euler's number.
For every , with probability at least ,
This is the goal because it is the statement users of Gaussian matrices quote: a quantitative near-isometry with explicit sub-Gaussian deviations. It follows from the expectation bounds (Gordon) and concentration, both of which are milestones.
The results. Gordon's theorem is sharp: and are pinned to within of the Bai–Yin limits for every . Gaussian concentration upgrades it to tail bounds with the optimal sub-Gaussian rate, and the Chevet-type bound is the same mechanism for , where it yields the expected spectral error of the randomized SVD. The small-ball bound covers the other regime, , with polynomial decay of the exact order ; together the two tails make every negative moment , , finite and explicitly bounded, which is what the early-truncated analysis needs.
Formalizing them. Mathlib has the standard Gaussian measure on finite-dimensional inner product spaces but neither Gaussian concentration for Lipschitz functions, nor Slepian's or Gordon's comparison inequalities, nor any result on singular values of random matrices. These are foundational pieces of high-dimensional probability whose formalization would be reused far beyond this series.
The upper bound in Gordon's theorem is proved by Slepian's comparison lemma for the Gaussian process on , and the lower bound by Gordon's minimax comparison inequality for ; both require a theory of Gaussian processes indexed by continuous parameter sets, or at least a discretization argument with careful limits. Gaussian concentration (Tsirelson–Ibragimov–Sudakov) is usually proved through the Gaussian logarithmic Sobolev inequality or the Ornstein–Uhlenbeck semigroup, with a smoothing step to pass from smooth to Lipschitz functions. Both are long developments with no Mathlib support. The elementary alternatives do not reach the stated constants: an -net argument bounds by with , and a union bound over rows for the small-ball estimate is exactly how the stated bound is obtained, but it needs the fact that the distance from a Gaussian vector to a fixed -dimensional subspace is a variable, which again rests on rotational invariance.
Matrices are sampled from the product measure on arrays. is sMin, the real infimum over the unit sphere of ; is assumed so the sphere is nonempty, and is not assumed for Gordon's theorem (for one has and the lower bound is trivial, as in the source). is Mathlib's operator norm. Expectation bounds are stated together with integrability of their integrands, so the Lean convention that non-integrable functions integrate to cannot trivialize them. Probabilities are measures in compared with of the real bound; the goal's lower bound uses truncated subtraction and is vacuous for , exactly as in the source. Gaussian concentration is stated with and , which the sources leave implicit (for or the event has probability one). Results that the sketching literature states for wide matrices are stated here for tall matrices via , with .
Welcome contributions: Gaussian concentration for Lipschitz functions on (any proof), Slepian's and Gordon's inequalities, the -Lipschitz property of and , the chi-square Chernoff bounds, and the law of the distance from a Gaussian vector to a subspace.
Shared definitions: the items of this mission import Definitions.Def_GaussianMatrix_basic, a draft of Mission I; submit that proposal first so the import resolves at compile time.
Series: I. Rotation Invariance and Moment Identities · II. Inverse Moments of the Pseudoinverse · III. Extreme Singular Values and Concentration. All three missions share the definition bundle GaussianMatrix_basic, published with Mission I, and the namespace GaussianMatrix.
namespace GaussianMatrix
theorem extreme_singular_values_deviation {N n : ℕ} (hn : 1 ≤ n) (t : ℝ) (ht : 0 ≤ t) :
1 - ENNReal.ofReal (2 * Real.exp (-t ^ 2 / 2))
≤ (gaussianMatrix N n) {A | Real.sqrt N - Real.sqrt n - t ≤ sMin (Matrix.of A) ∧
specNorm (Matrix.of A) ≤ Real.sqrt N + Real.sqrt n + t} := by sorry
end GaussianMatrixLet , , be a matrix whose entries are independent standard normal random variables. Then for every , with probability at least ,
where and is the spectral norm.
This is Vershynin's Corollary 5.35, the non-asymptotic Gaussian analogue of the Bai–Yin law with explicit sub-Gaussian deviations. It follows from Gordon's expectation bounds and Gaussian concentration, since and are -Lipschitz functions of the matrix in the Frobenius norm. It is the standard tool for showing that a Gaussian sketch is a near-isometry, and for lower-bounding of the head block in randomized low-rank approximation.
Formalization Note. The probability is a measure in and the lower bound is computed with truncated subtraction, so the statement is vacuous when , i.e. , exactly as in the source. The inequality is not part of the event (it is immediate).
No open leaves. Every sub-goal is proved or awaiting decomposition.