Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

rademacher_sampled_matrix_noncommutative_khintchine_diagonal_gram_bound_q2

Proved

by Harry_Xu · Jun 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

khintchinematrix-completionprobabilityschatten

Corrected (q≥2) noncommutative Khintchine / Lust-Picquard–Pisier–Buchholz bound for the Rademacher coordinate sum Sε=p−1∑(i,j)∈ΩεijXijeiej⊤S_\varepsilon=p^{-1}\sum_{(i,j)\in\Omega}\varepsilon_{ij}X_{ij}e_ie_j^\topSε​=p−1∑(i,j)∈Ω​εij​Xij​ei​ej⊤​. There is an absolute constant C>0C>0C>0 such that for every β>2\beta>2β>2 and every qqq with q≥2q\ge 2q≥2 and q≥βlog⁡(max⁡(n1,n2))q\ge\beta\log(\max(n_1,n_2))q≥βlog(max(n1​,n2​)), the qqq-th Schatten moment satisfies Eε ∥Sε∥Sqq≤(Cq max⁡(Grow,Gcol))q\mathbb{E}_\varepsilon\,\|S_\varepsilon\|_{S_q}^q \le (C\sqrt q\,\max(G_{\mathrm{row}},G_{\mathrm{col}}))^qEε​∥Sε​∥Sq​q​≤(Cq​max(Grow​,Gcol​))q, where Grow,GcolG_{\mathrm{row}},G_{\mathrm{col}}Grow​,Gcol​ are the diagonal Gram Schatten-qqq norms ∥(∑ijAijAij⊤)1/2∥Sq\|(\sum_{ij}A_{ij}A_{ij}^\top)^{1/2}\|_{S_q}∥(∑ij​Aij​Aij⊤​)1/2∥Sq​​ and ∥(∑ijAij⊤Aij)1/2∥Sq\|(\sum_{ij}A_{ij}^\top A_{ij})^{1/2}\|_{S_q}∥(∑ij​Aij⊤​Aij​)1/2∥Sq​​ of the coordinate matrices Aij=p−1[(i,j)∈Ω]Xijeiej⊤A_{ij}=p^{-1}[(i,j)\in\Omega]X_{ij}e_ie_j^\topAij​=p−1[(i,j)∈Ω]Xij​ei​ej⊤​. This is the corrected form of the q≥1q\ge 1q≥1 node: the noncommutative Khintchine inequality (Lust-Picquard–Pisier; Buchholz, constant 2−1/4π/e2^{-1/4}\sqrt{\pi/e}2−1/4π/e​) is valid for Schatten exponents 2≤q<∞2\le q<\infty2≤q<∞, so the genuine hypothesis is q≥2q\ge 2q≥2 (Candès–Recht 2009, arXiv:0805.4471, Lemma 6.1, §6.1, p.24).

Preamble
import Definitions.Def_matrix_completion_gram_schatten
open MatrixCompletion
Formal statement
theorem rademacher_sampled_matrix_noncommutative_khintchine_diagonal_gram_bound_q2 :
    ∃ C : ℝ, 0 < C ∧
      ∀ (β : ℝ), 2 < β →
      ∀ (n₁ n₂ m q : ℕ)
        (Omega : Finset (Fin n₁ × Fin n₂))
        (X : Matrix (Fin n₁) (Fin n₂) ℝ),
        2 ≤ q →
        (q : ℝ) ≥ β * Real.log (↑(max n₁ n₂)) →
        rademacherExpectation
            (fun eps =>
              schattenNorm (q : ℝ)
                (rademacherSampledMatrix Omega eps
                  ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X) ^ q) ≤
          (C * Real.sqrt (q : ℝ) *
            max (sampledRowGramSchatten Omega
                  ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X (q : ℝ))
                (sampledColumnGramSchatten Omega
                  ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) X (q : ℝ))) ^ q := by
  sorry
Source
Candès–Recht 2009, arXiv:0805.4471, Lemma 6.1 (§6.1, p.24); Lust-Picquard–Pisier / Buchholz noncommutative Khintchine inequality (valid for 2≤q<∞).

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me