Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

scalar_centered_sampling_bernstein_tail_with_inner_scale_from_entry_frobenius_bounds

Proved

by Shuze Chen · Jun 14, 2026 · Mathlib c5ea003 (Lean v4.30.0)

bernsteincandes-rechtcentered-samplingconvex-optimizationlean4matrix-completionprobabilityscale-absorptiontail-bounds

Role. It is a centered-sampling fluctuation estimate, one of the reusable concentration interfaces used repeatedly by the Neumann-term bounds.

Problem and notation. Exact matrix completion asks when an unknown low-rank real matrix can be recovered from a random subset of its entries. Here M∈Rn1×n2M\in\mathbb R^{n_1\times n_2}M∈Rn1​×n2​ has rank rrr, mmm entries are observed, and n=max⁡(n1,n2)n=\max(n_1,n_2)n=max(n1​,n2​). Recovery means nuclear-norm minimization: minimize ∥X∥∗\|X\|_*∥X∥∗​ among matrices XXX agreeing with MMM on the observed entries. Probability notation. successProb⁡(m,M)\operatorname{successProb}(m,M)successProb(m,M) is the fixed-cardinality success probability: Ω\OmegaΩ is chosen uniformly among all subsets of n1n2n_1n_2n1​n2​ entries with ∣Ω∣=m|\Omega|=m∣Ω∣=m, and the event is that the convex program uniquely returns MMM. In Bernoulli nodes, Pp(E)\mathbb P_p(E)Pp​(E) or bernoulliEventProb⁡(p,E)\operatorname{bernoulliEventProb}(p,E)bernoulliEventProb(p,E) means each entry is sampled independently with probability ppp, usually p=m/(n1n2)p=m/(n_1n_2)p=m/(n1​n2​). Coherence notation. The object SSS records SVD/singular-vector data for MMM. The hypotheses A0(S,μ0)A0(S,\mu_0)A0(S,μ0​) and A1(S,μ1)A1(S,\mu_1)A1(S,μ1​) are the Candes-Recht incoherence assumptions: μ0\mu_0μ0​ measures how spread out the singular vector spaces are, and μ1\mu_1μ1​ measures the largest entry of the sign matrix UV⊤UV^\topUV⊤. The parameter β>2\beta>2β>2 controls polynomial failure probabilities such as n−βn^{-\beta}n−β.

Claim. Generic conditional scalar Bernstein estimate for the all-distinct middle coefficient scale. If the base matrix entry and Frobenius bounds carry an already-proved inner coefficient factor Cinner λ−1/2C_{\mathrm{inner}}\,\lambda^{-1/2}Cinner​λ−1/2, the next scalar centered-sampling Bernstein step gives the Cinner λ−1C_{\mathrm{inner}}\,\lambda^{-1}Cinner​λ−1 tail.

Lecture-note formulation:

∥a∥∞≤a∞,∥a∥2≤a2⟹Pp ⁣(∣∑(δij−p)aij∣≤C inner Bernstein scale)≥1−cn−β.\|a\|_\infty\le a_\infty,\qquad \|a\|_2\le a_2 \Longrightarrow \mathbb P_p\!\left(\left|\sum(\delta_{ij}-p)a_{ij}\right| \le C\,\text{inner Bernstein scale}\right)\ge 1-cn^{-\beta}.∥a∥∞​≤a∞​,∥a∥2​≤a2​⟹Pp​(​∑(δij​−p)aij​​≤Cinner Bernstein scale)≥1−cn−β.

The constants in this node are universal existential constants; the theorem asserts that some positive constants with these roles exist.

Decomposition status. A corresponding proof sketch reduces this node to smaller mathematical subclaims. The checked reduction uses 4 subclaims: scalar centered sampling bernstein tail from entry Frobenius scales; inner scaled scalar bernstein lambda scale absorption; Bernoulli event probability mono; sample ratio between zero and one.

Preamble
import Definitions.Def_matrix_completion_neumann
open MatrixCompletion
Formal statement
theorem scalar_centered_sampling_bernstein_tail_with_inner_scale_from_entry_frobenius_bounds
    (Centry Cfro : ℝ) :
    0 < Centry → 0 < Cfro →
    ∃ Cpoint cpoint : ℝ, 0 < Cpoint ∧ 0 < cpoint ∧
      ∀ (β lam : ℝ), 2 < β → 1 ≤ lam →
      ∀ (n₁ n₂ r m : ℕ) (μ₀ Cinner : ℝ),
        0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
        1 ≤ μ₀ → 0 < Cinner →
        (m : ℝ) ≥
          lam * Real.rpow μ₀ ((4 : ℝ) / 3) *
            (↑(max n₁ n₂)) * Real.rpow (r : ℝ) ((4 : ℝ) / 3) *
              (β * Real.log (↑(max n₁ n₂))) →
        ∀ (Coeff : Finset (Fin n₁ × Fin n₂) → ℝ)
          (B : Matrix (Fin n₁) (Fin n₂) ℝ),
        (∀ Omega : Finset (Fin n₁ × Fin n₂),
          Coeff Omega =
            matrixEntrySum
              (centeredSamplingFluctuation Omega
                ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) B)) →
        entrySupNorm B ≤
          Centry * (Cinner * Real.rpow lam (-((1 : ℝ) / 2))) *
            μ₀ * ((r : ℝ) / (↑(max n₁ n₂))) →
        frobeniusNorm B ≤
          Cfro * (Cinner * Real.rpow lam (-((1 : ℝ) / 2))) *
            Real.sqrt (μ₀ * ((r : ℝ) / (↑(max n₁ n₂)))) →
        bernoulliEventProb ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
            (fun Omega =>
              |Coeff Omega| ≤
                (Cpoint * Cinner) * Real.rpow lam (-1)) ≥
          1 - cpoint * Real.rpow (↑(max n₁ n₂)) (-β) := by
  sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.

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