singular_projection_inclusion_exclusion_spectral_norm_le_original
Provedcandes-rechtlean4matrix-completionnormal-projectionspectral-normtangent-space
This is the operator-norm contraction of the two-sided orthogonal complement projection.
For every matrix ,
Written in the Lean inclusion-exclusion notation, the left-hand side is
The mathematical reason is that and are orthogonal projections, hence have operator norm at most , and the matrix operator norm is submultiplicative.
Source: Candes-Recht 2008, PDF p. 24, Section 6.1, immediately before equation (6.5), where the proof uses .
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem singular_projection_inclusion_exclusion_spectral_norm_le_original
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(S : SVD M r) (X : Matrix (Fin n₁) (Fin n₂) ℝ) :
spectralNorm
(X - leftSingularProjection S X - rightSingularProjection S X +
twoSidedSingularProjection S X) ≤
spectralNorm X := by
sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact matrix completion via convex optimization." Communications of the ACM 55.6 (2012): 111-119.