quadratic_neumann_all_equal_base_entry_sup_norm_bound_from_a1_min_dim
ProvedA1-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 be rank- SVD data for an matrix satisfying the incoherence hypotheses and . Let . In the all-equal case of Section 6.3, equation (6.21) uses the fixed matrix
represented in Lean by quadraticNeumannAllEqualBaseMatrix S. The A1 assumption gives the sign-matrix entry scale
and Lemma 6.4 gives the corrected rectangular diagonal tangent-kernel scale
Therefore this node asserts the source-corrected A1-sharp entry bound
Here , , , , , and the SVD/incoherence hypotheses are explicit. The Bernoulli rate , , 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 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.
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
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