quadratic_neumann_first_index_distinct_mean_coefficient_entry_bound
DisprovedRole. It belongs to the golfing/Neumann-series certificate branch, where the certificate is decomposed into linear and quadratic sampling terms.
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 has rank , entries are observed, and . Recovery means nuclear-norm minimization: minimize among matrices agreeing with on the observed entries. Probability notation. is the fixed-cardinality success probability: is chosen uniformly among all subsets of entries with , and the event is that the convex program uniquely returns . In Bernoulli nodes, or means each entry is sampled independently with probability , usually . Coherence notation. The object records SVD/singular-vector data for . The hypotheses and are the Candes-Recht incoherence assumptions: measures how spread out the singular vector spaces are, and measures the largest entry of the sign matrix . The parameter controls polynomial failure probabilities such as . For certificate nodes, is the tangent space at , and are the tangent and normal projections, and keeps only observed entries. The Neumann-series estimates control the dual certificate used to prove uniqueness of nuclear-norm recovery.
Claim. Lemma 6.8 in rectangular form: the deterministic coefficient matrix for the mean term has small entry sup norm. The displayed A0-only scale uses the crude A0-implied sign-matrix entry bound.
Lecture-note formulation:
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 3 subclaims: quadratic Neumann first index distinct mean coefficient as scaled off diagonal response; quadratic Neumann first index distinct mean off diagonal response entry sup norm bound; quadratic Neumann first index distinct mean coefficient from off diagonal response bound.
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
theorem quadratic_neumann_first_index_distinct_mean_coefficient_entry_bound :
∃ Ccoef : ℝ, 0 < Ccoef ∧
∀ (n₁ n₂ r : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₀ : ℝ) (S : SVD M r) (p : ℝ),
0 < n₁ → 0 < n₂ → 0 < r → 0 < p →
1 ≤ μ₀ → A0 S μ₀ →
entrySupNorm (quadraticFirstIndexDistinctMeanCoefficientMatrix S p) ≤
Ccoef * μ₀ ^ 2 *
(((r : ℝ) / (↑(max n₁ n₂))) ^ 2) * p⁻¹ := by
sorry