quadratic_neumann_last_index_distinct_response_operator_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. Deterministic Lemma 6.4-style bound for the off-diagonal response operator appearing in the mean term. The diagonal tangent multiplier contributes the scale, while the remaining tangent projection is measured by the spectral norm of the input matrix.
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_last_index_distinct_response_operator_bound :
∃ Cresp : ℝ, 0 < Cresp ∧
∀ (n₁ n₂ r : ℕ) (M : Matrix (Fin n₁) (Fin n₂) ℝ)
(μ₀ : ℝ) (S : SVD M r),
0 < n₁ → 0 < n₂ → 0 < r →
1 ≤ μ₀ → A0 S μ₀ →
∀ X : Matrix (Fin n₁) (Fin n₂) ℝ,
spectralNorm (quadraticLastIndexDistinctOffDiagonalResponse S X) ≤
Cresp * μ₀ * ((r : ℝ) / (↑(max n₁ n₂))) * spectralNorm X := by
sorry