quadratic_neumann_middle_index_distinct_mean_prefactor_bound_from_coefficient_bound
ProvedRole. 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. Raw Frobenius comparison for the mean part of the quadratic term: the coefficient-sum representation, the Frobenius norm of the sign matrix, and a uniform coefficient bound imply the unabsorbed scalar prefactor.
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. This node is currently a leaf problem in the decomposition tree, intended to be proved directly by later agents.
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
theorem quadratic_neumann_middle_index_distinct_mean_prefactor_bound_from_coefficient_bound :
∃ Cpref : ℝ, 0 < Cpref ∧
∀ (β lam : ℝ), 2 < β → 1 ≤ lam →
∀ (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 μ₁ →
let p : ℝ := (m : ℝ) / ((n₁ : ℝ) * (n₂ : ℝ))
∀ Omega : Finset (Fin n₁ × Fin n₂),
quadraticNeumannMiddleIndexDistinctMeanContribution Omega S p =
(p⁻¹ * (1 - p)) •
∑ w1 : Fin n₁ × Fin n₂,
(signMatrix S w1.1 w1.2 *
quadraticMiddleIndexDistinctMeanCoefficient Omega S p w1) •
coordinateMatrix w1.1 w1.2 →
frobeniusNorm (signMatrix S) ≤ Real.sqrt (r : ℝ) →
∀ Ccoef : ℝ, 0 < Ccoef →
let coeffScale : ℝ :=
Ccoef * Real.sqrt (β * Real.log (↑(max n₁ n₂))) *
Real.rpow
((μ₀ * (↑(max n₁ n₂)) * (r : ℝ)) / (m : ℝ))
((3 : ℝ) / 2)
QuadraticMiddleIndexDistinctMeanCoefficientBound Omega S p coeffScale →
spectralNorm
(quadraticNeumannMiddleIndexDistinctMeanContribution Omega S p) ≤
(Cpref * Ccoef) *
(p⁻¹ * (1 - p)) *
Real.sqrt (r : ℝ) *
Real.sqrt (β * Real.log (↑(max n₁ n₂))) *
Real.rpow
((μ₀ * (↑(max n₁ n₂)) * (r : ℝ)) / (m : ℝ))
((3 : ℝ) / 2) := by
sorry