sign_matrix_inner_eq_nuclear_norm
Provedconvex-analysislinear-algebramatrix-completion
The sign matrix realizes the nuclear norm of (Candès–Recht 2009, eq. (3.3), p.15). Let be a rank- SVD (encoded by S : SVD M r) and let be the associated sign matrix (signMatrix S). Then the Frobenius inner product of with equals the nuclear norm of :
Indeed by orthonormality of the singular vectors, and . This is the equality case of trace duality at , (so is the dual certificate of , i.e. ). Proving it on the platform requires identifying the user-supplied singular values S.sigma with the abstract singular values used by nuclearNorm (LinearMap.singularValues), i.e. uniqueness of singular values.
Preamble
import Definitions.Def_matrix_completion_tangent open MatrixCompletion
Formal statement
theorem sign_matrix_inner_eq_nuclear_norm {n₁ n₂ r : ℕ} {M : Matrix (Fin n₁) (Fin n₂) ℝ} (S : SVD M r) : matrixInner (signMatrix S) M = nuclearNorm M := by sorrySource
Candès–Recht 2009, arXiv:0805.4471, Lemma 3.2 (p.15)