by Harry_Xu · Jun 22, 2026 · Mathlib 0df444a (Lean v4.33.1)
khintchinematrix-completionschatten
The ℓq→ℓ∞ Gram comparison plus window collapse of Candes-Recht 2009, Section 6.1, p.24 (the displayed bound ∥X∥≤∥X∥Sq≤e∥X∥ for q≥logn, and the 'after a little algebra' step). For nonnegative reals, (∑i∈[N]aiq)1/q≤N1/qmaxiai; applied to the diagonal Gram entries this gives
In the window q≥βlog(max(n1,n2)) with β>2 the polynomial factor collapses to an absolute constant: (maxn)1/q≤e1/β≤e1/2. Hence the diagonal-Gram Schatten norms are bounded by e1/2⋅rademacherSampledVarianceScale. Here rademacherSampledVarianceScale=p−1max(sampledRowEnergyMax,sampledColumnEnergyMax) is the ℓ∞ variance scale. Hypotheses: 0≤p, β>2, 1≤q, q≥βlog(max(n1,n2)).
Preamble
import Definitions.Def_matrix_completion_gram_schatten
import Mathlib.Analysis.SpecialFunctions.Pow.Real
import Mathlib.Analysis.SpecialFunctions.Log.Basic
open MatrixCompletion
Formal statement
theorem gram_schatten_le_exp_half_variance_scale {n1 n2 : Nat}
(Omega : Finset (Fin n1 × Fin n2)) (p : Real) (X : Matrix (Fin n1) (Fin n2) ℝ)
(q β : Real) (hp : 0 ≤ p) (hβ : 2 < β) (hq : 1 ≤ q)
(hqlog : q ≥ β * Real.log (↑(max n1 n2))) :
max (sampledRowGramSchatten Omega p X q) (sampledColumnGramSchatten Omega p X q) ≤
Real.exp (1 / 2) * rademacherSampledVarianceScale Omega p X := by
sorry