first_neumann_certificate_term_as_normal_projection_of_centered_iterate
Provedcandes-rechtdual-certificatelean4matrix-completionneumann-seriesnormal-projectiontangent-space
Source: Candes-Recht 2008, PDF p. 18, equation (4.13), and PDF p. 26, Section 6.2.
Let be the Neumann error operator and let be its first iterate applied to the sign matrix . This theorem rewrites the first normal-space certificate term
as the normal projection of the centered sampling fluctuation
The point is that lies in the tangent space, so the extra term has zero normal projection. In Lean this is expressed with neumannCertificateTerm, centeredSamplingFluctuation, and neumannIterate.
Preamble
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
Formal statement
theorem first_neumann_certificate_term_as_normal_projection_of_centered_iterate
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(S : SVD M r) (Omega : Finset (Fin n₁ × Fin n₂)) (p : ℝ) :
neumannCertificateTerm Omega S p 1 =
normalProjection S
(centeredSamplingFluctuation Omega p (neumannIterate Omega S p 1)) := by
sorrySource
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.