Standard Gaussian matrices: law, Frobenius and spectral norms, smallest singular value, pseudoinverse
DefinitionGaussianMatrix_basicThis bundle fixes the shared vocabulary of the Gaussian Random Matrices mission series (namespace GaussianMatrix).
The Gaussian matrix law. For , denotes the law of a matrix whose entries are independent standard normal random variables. It is realized as the product measure on the function space ; a sample is turned into a matrix by the identity map . It is a probability measure (instance provided).
Norms. For a real matrix ,
where (the spectral norm, i.e. the largest singular value) is Mathlib's operator norm (Matrix.Norms.L2Operator).
Smallest singular value. For a (tall) matrix ,
so that is the -th singular value when , and when . For a wide matrix the usual is .
Pseudoinverse of a full-row-rank matrix. For ,
which is the Moore–Penrose pseudoinverse whenever is invertible (i.e. has full row rank).
These are the objects appearing in the Gaussian moment identities of Halko–Martinsson–Tropp and Tropp–Webber and in Gordon's theorem on extreme singular values.
Formalization Note. Mathlib's matrix inverse is total: when is singular, so on that null set. The infimum defining is over the unit sphere of ; for the sphere is empty and the real-valued infimum is by Lean's convention. Sample spaces are function types rather than Matrix types because Mathlib equips the former, not the latter, with the product -algebra.
import Mathlib
/-!
# Standard Gaussian matrices: basic definitions
Shared vocabulary for the "Gaussian Random Matrices" mission series.
* `GaussianMatrix.gaussianMatrix p m` — the law of a `p × m` matrix with independent
standard normal entries, as the product measure on `Fin p → Fin m → ℝ`. A sample `G` is
viewed as a matrix via `Matrix.of G`.
* `GaussianMatrix.frobSq`, `frobNorm` — squared Frobenius norm `∑ᵢⱼ Aᵢⱼ²` and its square root.
* `GaussianMatrix.specNorm` — the spectral norm (largest singular value), i.e. Mathlib's
`ℓ₂ → ℓ₂` operator norm `Matrix.Norms.L2Operator`.
* `GaussianMatrix.sMin` — the smallest singular value of a tall `N × n` matrix,
`inf { ‖A x‖₂ : ‖x‖₂ = 1 }` (for a wide matrix apply it to the transpose).
* `GaussianMatrix.pinvR` — `Gᵀ (G Gᵀ)⁻¹`, the Moore–Penrose pseudoinverse of a matrix with
full row rank (Mathlib's `⁻¹` is total, returning `0` on a singular input).
-/
open MeasureTheory ProbabilityTheory
open scoped Matrix Matrix.Norms.L2Operator
namespace GaussianMatrix
/-- The law of a `p × m` standard Gaussian matrix: independent `N(0,1)` entries, as a product
measure on `Fin p → Fin m → ℝ`. `Matrix.of G` is the matrix view of a sample `G`. -/
noncomputable def gaussianMatrix (p m : ℕ) : Measure (Fin p → Fin m → ℝ) :=
Measure.pi fun _ : Fin p => Measure.pi fun _ : Fin m => gaussianReal 0 1
instance gaussianMatrix_isProbabilityMeasure (p m : ℕ) :
IsProbabilityMeasure (gaussianMatrix p m) := by
unfold gaussianMatrix; infer_instance
/-- Squared Frobenius norm `‖A‖_F² = ∑ᵢ ∑ⱼ Aᵢⱼ²`. -/
def frobSq {m n : Type*} [Fintype m] [Fintype n] (A : Matrix m n ℝ) : ℝ :=
∑ i, ∑ j, A i j ^ 2
/-- Frobenius norm `‖A‖_F = √(∑ᵢⱼ Aᵢⱼ²)`. -/
noncomputable def frobNorm {m n : Type*} [Fintype m] [Fintype n] (A : Matrix m n ℝ) : ℝ :=
Real.sqrt (frobSq A)
/-- Spectral norm `‖A‖ = max_{‖x‖₂ = 1} ‖A x‖₂` (largest singular value): Mathlib's
`ℓ₂ → ℓ₂` operator norm of a real matrix. -/
noncomputable def specNorm {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]
(A : Matrix m n ℝ) : ℝ := ‖A‖
/-- Smallest singular value of a tall matrix `A : Matrix N n`:
`σ_min(A) = inf { ‖A x‖₂ : x ∈ ℝⁿ, ‖x‖₂ = 1 }` (equal to `0` when `n = 0`, by the real
convention `inf ∅ = 0`). For a wide matrix use `sMin Aᵀ`. -/
noncomputable def sMin {N n : Type*} [Fintype N] [Fintype n] (A : Matrix N n ℝ) : ℝ :=
⨅ x : {x : n → ℝ // x ⬝ᵥ x = 1}, Real.sqrt ((A *ᵥ x.1) ⬝ᵥ (A *ᵥ x.1))
/-- Right pseudoinverse `G† = Gᵀ (G Gᵀ)⁻¹` of a matrix `G : Matrix m n`; it is the Moore–Penrose
pseudoinverse whenever `G Gᵀ` is invertible (full row rank), and `0` otherwise. -/
noncomputable def pinvR {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m]
(G : Matrix m n ℝ) : Matrix n m ℝ :=
Gᵀ * (G * Gᵀ)⁻¹
end GaussianMatrix
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1
This bundle introduces six pieces of vocabulary; nothing is proved beyond one typeclass fact.
Gaussian matrix law. For natural numbers (either may be ), (written gaussianMatrix p m) is a measure on the space of functions , i.e. on real arrays indexed by , . It is the product measure
where is Mathlib's Gaussian measure on with mean and variance . The sigma-algebra is the product (coordinatewise Borel) sigma-algebra. The bundle also records that is a probability measure. An array is identified with a matrix via the type-level bijection Matrix.of (and back via its inverse); this bijection does not change the underlying data. Edge case: if or , the underlying space has exactly one point (the empty array) and is the unit point mass on it.
Squared Frobenius norm. For finite index types and a real matrix ,
If or is empty this is the empty sum, .
Frobenius norm. , using Mathlib's real square root (which returns on negative input; the argument here is a sum of squares, so this never bites).
Spectral norm. For finite index types with decidable equality and , where is Mathlib's operator norm on matrices (the scoped instance Matrix.Norms.L2Operator): the operator norm of regarded as a linear map from Euclidean to Euclidean , i.e. , which is the largest singular value of . It is when or is empty.
Smallest singular value (tall convention). For finite index types and ,
where is the dot product and the matrix–vector product. The infimum is Lean's real infimum over the subtype of vectors with : when is empty, the only vector is and , so the index set is empty and, by the convention in , . When is nonempty the set of values is nonempty and bounded below by , so this is the genuine infimum. When is empty (and is not), every is the empty vector, so . No decidable-equality assumptions are needed. (The docstring says to apply this to for wide matrices; the definition itself does nothing special for wide inputs.)
Right pseudoinverse. For finite index types with decidable equality on and ,
where is Mathlib's total matrix inverse on square matrices: it equals the true inverse when and is the zero matrix otherwise. Hence whenever is singular (in particular whenever does not have full row rank, e.g. when is nonempty but , or when ). Edge cases: if is empty, is the matrix, whose determinant is and whose inverse is the (empty) identity, and is the unique matrix; if is empty, is the unique matrix.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.