Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

linear_neumann_off_diagonal_two_term_bernstein_threshold_absorbed_under_sample_bound

Disproved

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

bernsteincandes-rechtlemma-66matrix-completionsample-complexityscalar-arithmetic

This theorem is the scalar sample-size absorption that turns the two-term Bernstein threshold in Candes--Recht equation (6.17) into the final Lemma 6.6 coefficient scale.

The raw threshold is

Ctwo((β+2)log⁡np F+(β+2)lognp A),p=mn1n2,C_{\rm two}\left( \sqrt{\frac{(\beta+2)\log n}{p}}\,F +\frac{(\beta+2)log n}{p}\,A\right),\qquad p=\frac{m}{n_1n_2},Ctwo​(p(β+2)logn​​F+p(β+2)logn​A),p=n1​n2​m​,

with

A=Centryμ1rn1n2μ0rn,F=Cfroμ1rn1n2μ0rn.A=C_{\rm entry}\mu_1\sqrt{\frac r{n_1n_2}}\frac{\mu_0r}{n},\qquad F=C_{\rm fro}\mu_1\sqrt{\frac r{n_1n_2}}\sqrt{\frac{\mu_0r}{n}}.A=Centry​μ1​n1​n2​r​​nμ0​r​,F=Cfro​μ1​n1​n2​r​​nμ0​r​​.

The conclusion is that this threshold is at most

Cμ1rn1n2μ0nr βlog⁡nmC\mu_1\sqrt{\frac r{n_1n_2}}\sqrt{\frac{\mu_0nr\,\beta\log n}{m}}Cμ1​n1​n2​r​​mμ0​nrβlogn​​

under the stated sample lower bound. The accepted sketch splits the claim into the Frobenius/variance summand and the entry-sup/range summand, then adds the two inequalities.

Source location: Candes--Recht, Section 6.2, Lemma 6.6, equation (6.17) and the paragraph immediately following it.

Preamble
import Definitions.Def_linear_neumann_offdiag_bernstein
open MatrixCompletion
Formal statement
theorem linear_neumann_off_diagonal_two_term_bernstein_threshold_absorbed_under_sample_bound
    (Ctwo Centry Cfro : ℝ) :
    0 < Ctwo → 0 < Centry → 0 < Cfro →
    ∃ Ccoef : ℝ, 0 < Ccoef ∧
      ∀ (β lam : ℝ), 2 < β → 1 ≤ lam →
      ∀ (n₁ n₂ r m : ℕ) (μ₀ μ₁ : ℝ),
        0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
        1 ≤ μ₀ → 1 ≤ μ₁ →
        (m : ℝ) ≥
          lam * μ₁ * max (Real.sqrt μ₀) μ₁ *
            (↑(max n₁ n₂)) * (r : ℝ) *
              (β * Real.log (↑(max n₁ n₂))) →
        Ctwo *
            (Real.sqrt
                (((β + 2) * Real.log (↑(max n₁ n₂))) /
                  ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) *
              (Cfro * μ₁ *
                Real.sqrt ((r : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
                  Real.sqrt (μ₀ * (r : ℝ) / (↑(max n₁ n₂)))) +
              (((β + 2) * Real.log (↑(max n₁ n₂))) /
                  ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) *
                (Centry * μ₁ *
                  Real.sqrt ((r : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
                    (μ₀ * (r : ℝ) / (↑(max n₁ n₂))))) ≤
          Ccoef * μ₁ *
            Real.sqrt ((r : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
              Real.sqrt
                ((μ₀ * (↑(max n₁ n₂)) * (r : ℝ) *
                    (β * Real.log (↑(max n₁ n₂)))) / (m : ℝ)) := 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