Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

quadratic_neumann_section63_all_distinct_decoupled_case_bound_under_general_sample_bound

Proved

by Harry_Xu · Jul 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

bernoulli-samplingcandes-rechtdecouplinglean4matrix-completionneumann-correctionsection-6-3

This is the fully decoupled three-copy estimate for the all-distinct index case of the five-way partition (6.20) of the second quadratic Neumann correction, from Candes-Recht Section 6.3 (PDF pp. 33-34).

After the triple decoupling argument, the all-distinct contribution is controlled at the Section 6.3 summary scale Phi. Concretely, with p = m/(n1 n2), N = max(n1,n2), R = r, and the sampling condition

m≥C′⋅max⁡(μ12, μ0 μ1, μ0N1/4)⋅NR βlog⁡N,m \ge C' \cdot \max(\mu_1^2,\ \sqrt{\mu_0}\,\mu_1,\ \mu_0 N^{1/4}) \cdot N R\,\beta\log N,m≥C′⋅max(μ12​, μ0​​μ1​, μ0​N1/4)⋅NRβlogN,

the operator norm of the decoupled three-sample contribution obeys, with probability at least 1 - c N^{-beta},

∥S∥≤C Φ,Φ=μ02μ1NRβlog⁡Nm(NRm)2+μ02(NRm)2+βlog⁡N(NRm)3/2μ02R+(μ0μ1NRβlog⁡Nm)3/2.\|S\| \le C\,\Phi,\quad \Phi = \mu_0^2\mu_1\sqrt{\tfrac{NR\beta\log N}{m}}\Big(\tfrac{NR}{m}\Big)^2 + \mu_0^2\Big(\tfrac{NR}{m}\Big)^2 + \sqrt{\beta\log N}\Big(\tfrac{NR}{m}\Big)^{3/2}\mu_0^2 R + \Big(\tfrac{\mu_0\mu_1 NR\beta\log N}{m}\Big)^{3/2}.∥S∥≤CΦ,Φ=μ02​μ1​mNRβlogN​​(mNR​)2+μ02​(mNR​)2+βlogN​(mNR​)3/2μ02​R+(mμ0​μ1​NRβlogN​)3/2.

The proof of this node follows equation (6.23): control the inner G-coefficients via Lemma 6.6, then the middle H-coefficients via a second Lemma 6.6-type estimate, and finally apply Theorem 6.3 in the outer sample.

Source: Candes-Recht 2008, PDF pp. 33-34, Section 6.3, all-distinct case, equation (6.23) and the summary display.

Preamble
import Definitions.Def_matrix_completion_neumann
open MatrixCompletion
Formal statement
theorem quadratic_neumann_section63_all_distinct_decoupled_case_bound_under_general_sample_bound :
    ∃ Cdec cdec : ℝ, 0 < Cdec ∧ 0 < cdec ∧
      ∀ C' : ℝ, Cdec ≤ C' →
      ∀ (β : ℝ), 2 < β →
      ∀ (n₁ n₂ r m : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
        (μ₀ μ₁ : ℝ) (S : SVD M r),
        0 < n₁ → 0 < n₂ → 0 < r → m ≤ n₁ * n₂ →
        1 ≤ μ₀ → 1 ≤ μ₁ →
        A0 S μ₀ → A1 S μ₁ →
        (m : ℝ) ≥
          C' * max (max (μ₁ ^ 2) (Real.sqrt μ₀ * μ₁))
                  (μ₀ * Real.rpow (↑(max n₁ n₂)) ((1 : ℝ) / 4))
            * (↑(max n₁ n₂)) * (r : ℝ) *
              (β * Real.log (↑(max n₁ n₂))) →
        bernoulliTripleEventProb ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))
            (fun Omega1 Omega2 Omega3 =>
              spectralNorm
                (quadraticNeumannAllDistinctDecoupledContribution
                  Omega1 Omega2 Omega3 S
                  ((m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ)))) ≤
                (let N : ℝ := ↑(max n₁ n₂)
                 let R : ℝ := (r : ℝ)
                 let Mobs : ℝ := (m : ℝ)
                 let logN : ℝ := Real.log N
                 Cdec *
                   ((μ₀ ^ 2 * μ₁) *
                      Real.sqrt ((N * R * (β * logN)) / Mobs) *
                        ((N * R) / Mobs) ^ 2 +
                    μ₀ ^ 2 * ((N * R) / Mobs) ^ 2 +
                    Real.sqrt (β * logN) *
                        Real.rpow ((N * R) / Mobs) ((3 : ℝ) / 2) *
                          (μ₀ ^ 2 * R) +
                    Real.rpow
                      ((μ₀ * μ₁ * N * R * (β * logN)) / Mobs)
                      ((3 : ℝ) / 2)))) ≥
          1 - cdec * 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