right_singular_projection_minus_two_sided_spectral_norm_le_original
Provedcandes-rechtlean4matrix-completionspectral-normtangent-space
This is the spectral-norm contraction of the second tangent-projection summand.
With and denoting the column and row singular-space orthogonal projections,
Both and are orthogonal projections, hence left and right multiplication by them do not increase the matrix operator norm. Therefore
In Lean this is rightSingularProjection S X - twoSidedSingularProjection S X.
Source: Candes-Recht 2008, PDF p. 15, Section 3, equation (3.5), the formula for and .
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem right_singular_projection_minus_two_sided_spectral_norm_le_original
{n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ}
(S : SVD M r) (X : Matrix (Fin n₁) (Fin n₂) ℝ) :
spectralNorm (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.