normal_space_dual_achiever_with_sign_contraction
Provedconvex-analysislinear-algebramatrix-completion
Normal-space dual achiever with sign-contraction (Candès–Recht 2009, Lemma 3.2 achiever + subgradient characterization (3.4), p.15). Given a rank- SVD of and any perturbation , there exists a matrix lying in the normal space (i.e. , normalProjection S W = W) such that:
- is a contraction in operator norm, (
spectralNorm (signMatrix S + W) ≤ 1); and - achieves the nuclear norm of the normal component of : . This is the achiever half of Lemma 3.2 ("there is a with achieving equality ") specialized so that the achiever lives in and, combined with the tangent sign matrix (orthogonal supports), keeps . By the subgradient characterization (3.4), . Construction: take with and (dual achiever), set ; then , (since contracts the operator norm), , and because have orthogonal column/row spaces.
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem normal_space_dual_achiever_with_sign_contraction {n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ} (S : SVD M r) (H : Matrix (Fin n₁) (Fin n₂) ℝ) : ∃ W : Matrix (Fin n₁) (Fin n₂) ℝ, normalProjection S W = W ∧ spectralNorm (signMatrix S + W) ≤ 1 ∧ matrixInner W (normalProjection S H) = nuclearNorm (normalProjection S H) := by sorrySource
Candès–Recht 2009, arXiv:0805.4471, Lemma 3.2 (p.15)