sign_plus_normal_projection_operator_norm_le_one
ProvedSign matrix plus a normal-space contraction is a contraction (Candès–Recht 2009, arXiv:0805.4471, Lemma 3.2 achiever, p.15). Let be the tangent sign matrix of a rank- SVD of , so has column space inside the left singular span and row space inside the right singular span . For any matrix with operator norm , the normal projection lies in (its column space is orthogonal to and its row space orthogonal to ) and satisfies ( is an operator-norm contraction). Because and have orthogonal column spaces and orthogonal row spaces, acts blockwise and . This is exactly the construction guaranteeing in the subgradient characterization (3.4).
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem sign_plus_normal_projection_operator_norm_le_one {n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ} (S : SVD M r) (Z : Matrix (Fin n₁) (Fin n₂) ℝ) (hZ : spectralNorm Z ≤ 1) : spectralNorm (signMatrix S + normalProjection S Z) ≤ 1 := by sorrySource
Candès–Recht 2009, arXiv:0805.4471, Lemma 3.2 (p.15)