second_neumann_certificate_term_as_normal_projection_of_quadratic_correction
Provedcandes-rechtlean4matrix-completionneumann-seriessection-6-3spectral-norm
This is the algebraic identification of the second Neumann certificate term with the normal projection of the unprojected quadratic correction.
The proof of Lemma 4.6 expands the quadratic correction into five mutually exclusive index-coincidence classes:
In the Lean interface these are, respectively,
quadraticNeumannAllEqualContribution,
quadraticNeumannFirstIndexDistinctContribution,
quadraticNeumannMiddleIndexDistinctContribution,
quadraticNeumannLastIndexDistinctContribution, and
quadraticNeumannAllDistinctContribution.
The theorem states that
Source: Candes-Recht 2008, PDF p. 30, Section 6.3, equation (6.20).
Preamble
import Definitions.Def_matrix_completion_neumann open MatrixCompletion
Formal statement
theorem second_neumann_certificate_term_as_normal_projection_of_quadratic_correction
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(S : SVD M r) (Omega : Finset (Fin n₁ × Fin n₂)) (p : ℝ) :
neumannCertificateTerm Omega S p 2 =
normalProjection S
((((quadraticNeumannAllEqualContribution Omega S p +
quadraticNeumannFirstIndexDistinctContribution Omega S p) +
quadraticNeumannMiddleIndexDistinctContribution Omega S p) +
quadraticNeumannLastIndexDistinctContribution Omega S p) +
quadraticNeumannAllDistinctContribution Omega S p) := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.