Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.1 — matrix Gaussian and Rademacher series: P{λmax(Σ ξ_k A_k) ≥ t} ≤ d·e^{−t²/2σ²}, σ² = ‖Σ A_k²‖

Proved
MatrixTail.Gaussian.theorem4_1

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

gaussianmatrix-concentrationp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-matricestail-bound

Let A1,…,AnA_1,\dots,A_nA1​,…,An​ be fixed self-adjoint complex d×dd\times dd×d matrices (d≥1d\ge1d≥1), and let ξ1,…,ξn\xi_1,\dots,\xi_nξ1​,…,ξn​ be independent random variables that are either all standard normal or all Rademacher. Define the variance parameter

σ2:=∥∑kAk2∥.\sigma^2 := \Big\|\sum_k A_k^2\Big\|.σ2:=​k∑​Ak2​​.

Then for every t≥0t\ge 0t≥0:

  1. P{λmax⁡(∑kξkAk)≥t}≤d⋅e−t2/2σ2\displaystyle \mathbb P\Big\{\lambda_{\max}\Big(\sum_k \xi_k A_k\Big)\ge t\Big\}\le d\cdot e^{-t^2/2\sigma^2}P{λmax​(k∑​ξk​Ak​)≥t}≤d⋅e−t2/2σ2;
  2. P{∥∑kξkAk∥≥t}≤2d⋅e−t2/2σ2\displaystyle \mathbb P\Big\{\Big\|\sum_k \xi_k A_k\Big\|\ge t\Big\}\le 2d\cdot e^{-t^2/2\sigma^2}P{​k∑​ξk​Ak​​≥t}≤2d⋅e−t2/2σ2.

This is the noncommutative extension of the scalar Gaussian series bound P{∑kγkak≥t}≤e−t2/2σ2\mathbb P\{\sum_k\gamma_ka_k\ge t\}\le e^{-t^2/2\sigma^2}P{∑k​γk​ak​≥t}≤e−t2/2σ2 with σ2=∑kak2\sigma^2=\sum_k a_k^2σ2=∑k​ak2​. The variance parameter is the norm of the sum of the squares, not the sum of their norms, and the price of the matrix setting is only the dimensional factor ddd.

Formalization Note ∥⋅∥\|\cdot\|∥⋅∥ is the spectral norm. The two laws are two alternative hypotheses (all Gaussian, or all Rademacher), not a mixture. When σ2=0\sigma^2=0σ2=0 Lean's convention x/0=0x/0=0x/0=0 makes the right-hand sides ddd and 2d2d2d, a valid (trivial) bound; no positivity hypothesis on σ2\sigma^2σ2 is imposed.

Preamble
import Mathlib
import Definitions.Def_MatrixTail_Gaussian_Model

open MeasureTheory ProbabilityTheory
open scoped MatrixOrder ComplexOrder ENNReal
Formal statement
namespace MatrixTail.Gaussian

/-- **Theorem 4.1** (Matrix Gaussian and Rademacher Series), Tropp, arXiv:1004.4389v7, p. 14, displays
(4.2)–(4.4). Let `A₀, …, A_{n-1}` be fixed self-adjoint `d × d` matrices and `ξ₀, …, ξ_{n-1}` independent
scalar random variables that are either all standard normal or all Rademacher. With the variance parameter
`σ² := ‖Σ_k A_k²‖` (4.2), for all `t ≥ 0`:
* (4.3) `P{λmax(Σ_k ξ_k A_k) ≥ t} ≤ d · e^{−t²/2σ²}`;
* (4.4) `P{‖Σ_k ξ_k A_k‖ ≥ t} ≤ 2d · e^{−t²/2σ²}`.

Formalization Note.
* Complex Hermitian matrices; `‖·‖` is the spectral norm `specNorm`; `[NeZero d]` (at `d = 0` the right
  sides vanish while the probability at `t = 0` is `1`).
* "Gaussian or Rademacher" is the disjunction of two universal statements: the paper's sequence is all
  standard normal or all Rademacher, never a mixture.
* σ² is the norm of the sum, `specNorm (∑ k, A k ^ 2)`, not the sum of the norms.
* Boundary `σ² = 0`: Lean's `x / 0 = 0` makes the right sides `d` and `2d`, which are valid (and, at
  `t = 0`, the paper's values); for `t > 0` the paper's convention `e^{−∞} = 0` would give `0`, so at this
  degenerate point (all `A_k = 0`) the Lean bound is the trivial one. No positivity hypothesis is added. -/
theorem theorem4_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    {n d : ℕ} [NeZero d] (A : Fin n → Matrix (Fin d) (Fin d) ℂ) (hAherm : ∀ k, (A k).IsHermitian)
    (ξ : Fin n → Ω → ℝ) (hindep : iIndepFun ξ P)
    (hlaw : (∀ k, IsStdGaussian P (ξ k)) ∨ (∀ k, IsRademacher P (ξ k))) :
    ∀ t : ℝ, 0 ≤ t →
      P.real {ω | t ≤ MatrixTail.Master.lambdaMax (∑ k, ξ k ω • A k)} ≤
          d * Real.exp (-t ^ 2 / (2 * specNorm (∑ k, A k ^ 2))) ∧
        P.real {ω | t ≤ specNorm (∑ k, ξ k ω • A k)} ≤
          2 * d * Real.exp (-t ^ 2 / (2 * specNorm (∑ k, A k ^ 2))) := by sorry

end MatrixTail.Gaussian
Source
Tropp, User-Friendly Tail Bounds for Sums of Random Matrices, arXiv:1004.4389v7, p. 14, Theorem 4.1, displays (4.2)–(4.4)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me