Chen–Dongarra tail bound for :
OpenGaussianMatrix.pinv_spectral_tailLet be a standard Gaussian matrix with , and let . For every ,
Since , this is a small-ball estimate for the smallest singular value of a Gaussian matrix with polynomial decay of order . It is the source of both the expected-norm bound and the large-deviation bound (10.6) for the spectral error of the randomized SVD. The exponent is sharp.
Formalization Note. The event is with pinvR as ; real powers are Mathlib's rpow, with . The bound is a real number converted to .
import Definitions.Def_GaussianMatrix_basic open MeasureTheory ProbabilityTheory open scoped Matrix
namespace GaussianMatrix
theorem pinv_spectral_tail {r k : ℕ} (hr : 2 ≤ r) (hrk : r ≤ k) (t : ℝ) (ht : 0 < t) :
(gaussianMatrix r k) {G | t < specNorm (pinvR (Matrix.of G))}
≤ ENNReal.ofReal ((1 / Real.sqrt (2 * Real.pi * ((k : ℝ) - r + 1)))
* (Real.exp 1 * Real.sqrt k / ((k : ℝ) - r + 1)) ^ ((k : ℝ) - r + 1)
* t ^ (-((k : ℝ) - r + 1))) := by sorry
end GaussianMatrixRead-back
What the Lean code literally says, in plain math · claude-fable-5-1
Throughout, denotes the measure called gaussianMatrix r k: the product measure on the function space in which every one of the coordinates is an independent standard normal ; it is a probability measure, and a sample is viewed as the real matrix with entries . Matrix inversion is Mathlib's total inverse on square real matrices: it is the usual inverse when the determinant is nonzero and is the zero matrix otherwise. For an matrix , write , a real matrix (the bundle's pinvR; it is the zero matrix when is singular), and let denote the bundle's specNorm, Mathlib's operator norm (largest singular value).
Statement. Let be natural numbers with and , and let be a real number with . Put (computed in after casting; ). The theorem asserts the single inequality of extended non-negative reals
where , is the real square root, the two powers and are real powers (real exponent and respectively), and sends a real number to (negative inputs map to ). The left-hand side is the outer measure applied to the set of samples whose has spectral norm strictly greater than .
Edge cases. Since , we have , , and , so the base is positive, is an ordinary positive real, and the argument of is positive (no clipping at occurs). The case is allowed, giving and bound . Because is a probability measure, the left side is at most , so the inequality is automatically true whenever the right side is (e.g. for small ). Nothing is claimed for or for . Samples with singular have and are not in the set.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.