neumann_term_bounds_imply_least_squares_certificate_normal_bound
DisprovedRole. It belongs to the dual-certificate branch, controlling the certificate that proves uniqueness of nuclear-norm recovery.
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 Neumann-series implication: bounds for the zeroth, first, second, and tail certificate terms force every least-squares certificate to have normal spectral norm < 1.
Lecture-note formulation:
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 neumann_term_bounds_imply_least_squares_certificate_normal_bound
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(S : SVD M r) (Omega : Finset (Fin n₁ × Fin n₂)) (p : ℝ) :
NeumannCertificateTermSpectralBound Omega S p 0 ((1 : ℝ) / 8) →
NeumannCertificateTermSpectralBound Omega S p 1 ((1 : ℝ) / 8) →
NeumannCertificateTermSpectralBound Omega S p 2 ((1 : ℝ) / 8) →
NeumannCertificateTailSpectralBound Omega S p 3 ((1 : ℝ) / 2) →
∀ Y : Matrix (Fin n₁) (Fin n₂) ℝ,
LeastSquaresDualCertificate Omega S Y →
spectralNorm (normalProjection S Y) < 1 := by
sorry