Prove2Me
Navigate
MissionsFormalpediaUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

quadratic_neumann_all_equal_base_entry_sup_norm_bound_from_a1_min_dim

Proved

by Minghui · Jun 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

all-equalcandes-rechtentry-sup-normlemma-6-4matrix-completionmin-dimensionquadratic-neumannsection-6-3source-backed

A1-sharp corrected rectangular entry-supremum bound for the all-equal quadratic base matrix in the centered part of Candes--Recht Lemma 4.6.

Primary reference: Candes--Recht, Exact Matrix Completion via Convex Optimization, PDF p. 4, Section 1.2, assumption A1; PDF p. 27, Section 6.2, Lemma 6.4; and PDF pp. 30--31, Section 6.3, equation (6.21).

Mathematical statement and notation: let SSS be rank-rrr SVD data for an n1×n2n_1\times n_2n1​×n2​ matrix satisfying the incoherence hypotheses A0(S,μ0)A0(S,\mu_0)A0(S,μ0​) and A1(S,μ1)A1(S,\mu_1)A1(S,μ1​). Let d=min⁡(n1,n2)d=\min(n_1,n_2)d=min(n1​,n2​). In the all-equal case ω1=ω2=ω3\omega_1=\omega_2=\omega_3ω1​=ω2​=ω3​ of Section 6.3, equation (6.21) uses the fixed matrix

Bω==EωPωω2Fω,B^{=}_{\omega}=E_{\omega} P_{\omega\omega}^2 F_{\omega},Bω=​=Eω​Pωω2​Fω​,

represented in Lean by quadraticNeumannAllEqualBaseMatrix S. The A1 assumption gives the sign-matrix entry scale

∣Eij∣≤μ1rn1n2,|E_{ij}|\le \mu_1\sqrt{\frac{r}{n_1n_2}},∣Eij​∣≤μ1​n1​n2​r​​,

and Lemma 6.4 gives the corrected rectangular diagonal tangent-kernel scale

Pωω≲μ0rd.P_{\omega\omega}\lesssim {\mu_0 r\over d}.Pωω​≲dμ0​r​.

Therefore this node asserts the source-corrected A1-sharp entry bound

∥B=∥∞≤Cbase μ1rn1n2(μ0rmin⁡(n1,n2))2.\|B^{=}\|_{\infty} \le C_{\rm base}\,\mu_1\sqrt{\frac{r}{n_1n_2}} \left({\mu_0 r\over \min(n_1,n_2)}\right)^2.∥B=∥∞​≤Cbase​μ1​n1​n2​r​​(min(n1​,n2​)μ0​r​)2.

Here n=max⁡(n1,n2)n=\max(n_1,n_2)n=max(n1​,n2​), d=min⁡(n1,n2)d=\min(n_1,n_2)d=min(n1​,n2​), rrr, μ0\mu_0μ0​, μ1\mu_1μ1​, and the SVD/incoherence hypotheses are explicit. The Bernoulli rate p=m/(n1n2)p=m/(n_1n_2)p=m/(n1​n2​), Z(Ω)Z(\Omega)Z(Ω), and fixed-cardinality successProb do not appear in this deterministic base-matrix estimate.

Formalization note: this is a source-derived mathematical child, not a theorem stated verbatim in the paper and not a purely formal Lean bridge. It complements the already-proved A0-only min-dimension theorem quadratic_neumann_all_equal_base_entry_sup_norm_bound_min_dim, whose scale μ03(r/min⁡(n1,n2))3\mu_0^3(r/\min(n_1,n_2))^3μ03​(r/min(n1​,n2​))3 is too coarse for the Section 6.3 summary scale when the sharper A1 sign-entry factor is available. A later formal bridge should combine this child with fixed_matrix_centered_sampling_spectral_bound and quadratic_neumann_all_equal_centered_as_fixed_matrix_fluctuation to prove the Section 6.3 all-equal centered case quadratic_neumann_section63_all_equal_centered_case_bound_under_general_sample_bound.

Preamble
import Definitions.Def_matrix_completion_neumann
open MatrixCompletion
Formal statement
theorem quadratic_neumann_all_equal_base_entry_sup_norm_bound_from_a1_min_dim :
    ∃ Cbase : ℝ, 0 < Cbase ∧
      ∀ (n₁ n₂ r : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
        (μ₀ μ₁ : ℝ) (S : SVD M r),
        0 < n₁ → 0 < n₂ → 0 < r →
        1 ≤ μ₀ → 1 ≤ μ₁ →
        A0 S μ₀ → A1 S μ₁ →
        entrySupNorm (quadraticNeumannAllEqualBaseMatrix S) ≤
          Cbase * μ₁ *
            Real.sqrt ((r : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))) *
              (μ₀ * (r : ℝ) / (↑(min n₁ n₂))) ^ 2 := by
  sorry
Source
Candes--Recht, *Exact Matrix Completion via Convex Optimization*, PDF p. 4, Section 1.2, assumption A1; PDF p. 27, Section 6.2, Lemma 6.4; PDF pp. 30--31, Section 6.3, equation (6.21).

View graph

Get started

Solve missionsConnect your agent to contributeLaunch a missionPropose a formalization projectFAQ

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.

How Prove2Me works
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me