Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

matrix_completion_gram_schatten

Definition

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

khintchinematrix-completionschatten

Diagonal-Gram Schatten norms for the coordinate Rademacher series of Candes-Recht 2009 Section 6.1. For the coordinate sampled matrices Aij=p−1δijXijeiej⊤A_{ij} = p^{-1}\delta_{ij} X_{ij} e_i e_j^\topAij​=p−1δij​Xij​ei​ej⊤​ the Gram sums are diagonal, so the Schatten-qqq norm of (∑AA⊤)1/2(\sum A A^\top)^{1/2}(∑AA⊤)1/2 (resp. (∑A⊤A)1/2(\sum A^\top A)^{1/2}(∑A⊤A)1/2) equals the ℓq\ell_qℓq​ norm of the diagonal entries p−1rowEnergyip^{-1}\sqrt{\mathrm{rowEnergy}_i}p−1rowEnergyi​​ (resp. p−1colEnergyjp^{-1}\sqrt{\mathrm{colEnergy}_j}p−1colEnergyj​​), where rowEnergyi=∑jδijXij2\mathrm{rowEnergy}_i=\sum_j \delta_{ij} X_{ij}^2rowEnergyi​=∑j​δij​Xij2​ and colEnergyj=∑iδijXij2\mathrm{colEnergy}_j=\sum_i \delta_{ij} X_{ij}^2colEnergyj​=∑i​δij​Xij2​. sampledRowGramSchatten and sampledColumnGramSchatten package these two ℓq\ell_qℓq​ quantities as reusable vocabulary.

Definition code
import Definitions.Def_matrix_completion_rademacher

/-!
Diagonal-Gram Schatten norms for the coordinate Rademacher series of Section 6.1.

For the coordinate sampled matrices `A_ij = p⁻¹ δ_ij X_ij e_i e_jᵀ` appearing in the
noncommutative Khintchine inequality (Candès–Recht 2009, §6.1, Lemma 6.1), the Gram sums
are diagonal:
  `∑_{(i,j)} A_ij A_ijᵀ = diag_i (p⁻² · rowEnergy_i)`,
  `∑_{(i,j)} A_ijᵀ A_ij = diag_j (p⁻² · colEnergy_j)`,
where `rowEnergy_i = ∑_j δ_ij X_ij²` and `colEnergy_j = ∑_i δ_ij X_ij²`. Consequently the
Schatten-`q` norm of `(∑ A Aᵀ)^{1/2}` (resp. `(∑ Aᵀ A)^{1/2}`) equals the `ℓ_q` norm of the
diagonal entries `p⁻¹ √(rowEnergy_i)` (resp. `p⁻¹ √(colEnergy_j)`). These definitions package
those two `ℓ_q` quantities as reusable vocabulary, so the Khintchine right-hand side and its
`ℓ_q → ℓ_∞` comparison can both be stated directly.
-/

namespace MatrixCompletion

open scoped Classical BigOperators

/-- `ℓ_q`-norm of the per-row sampled Gram values `p⁻¹ √(rowEnergy_i)`; equals the Schatten-`q`
norm of the diagonal matrix `(∑_{(i,j)} A_ij A_ijᵀ)^{1/2}` for the coordinate sampled matrices
`A_ij = p⁻¹ δ_ij X_ij e_i e_jᵀ`. -/
noncomputable def sampledRowGramSchatten {n1 n2 : Nat}
    (Omega : Finset (Fin n1 × Fin n2)) (p : Real)
    (X : RealMatrix n1 n2) (q : Real) : Real :=
  Real.rpow
    (∑ i : Fin n1,
      Real.rpow (p⁻¹ * Real.sqrt (∑ j : Fin n2, if (i, j) ∈ Omega then X i j ^ 2 else 0)) q)
    q⁻¹

/-- `ℓ_q`-norm of the per-column sampled Gram values `p⁻¹ √(colEnergy_j)`; equals the
Schatten-`q` norm of the diagonal matrix `(∑_{(i,j)} A_ijᵀ A_ij)^{1/2}`. -/
noncomputable def sampledColumnGramSchatten {n1 n2 : Nat}
    (Omega : Finset (Fin n1 × Fin n2)) (p : Real)
    (X : RealMatrix n1 n2) (q : Real) : Real :=
  Real.rpow
    (∑ j : Fin n2,
      Real.rpow (p⁻¹ * Real.sqrt (∑ i : Fin n1, if (i, j) ∈ Omega then X i j ^ 2 else 0)) q)
    q⁻¹

end MatrixCompletion
Source
Candes, Recht, Exact matrix completion via convex optimization, arXiv:0805.4471, Section 6.1, Lemma 6.1, p.24.

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