Lemma 2.3 — AB′ = 0 and A′B = 0 imply ‖A + B‖_* = ‖A‖_* + ‖B‖_*
ProvedMinRankRecovery.Recovery.lemma_2_3nuclear-normp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be real matrices and let denote the nuclear norm (the sum of the singular values). If
then
The two conditions say that and have orthogonal row spaces and orthogonal column spaces. The lemma is the matrix analogue of the additivity of the norm on vectors with disjoint supports, and it is the step of the proof of Theorem 3.3 that turns the triangle inequality into the cone condition (3.4).
Formalization Note The paper names the two matrices and ; here they are and , because denotes the linear map elsewhere in the mission. is M * Nᵀ and is Mᵀ * N.
Preamble
import Mathlib import Definitions.Def_HighDimStat_MatrixRank_Core open HighDimStat.MatrixRank Matrix
Formal statement
namespace MinRankRecovery.Recovery
/-- Lemma 2.3, p. 9: if `M Nᵀ = 0` and `Mᵀ N = 0` then `‖M + N‖_* = ‖M‖_* + ‖N‖_*`. -/
theorem lemma_2_3 {m n : ℕ} (M N : Matrix (Fin m) (Fin n) ℝ) (h1 : M * Nᵀ = 0)
(h2 : Mᵀ * N = 0) :
nuclearNorm (M + N) = nuclearNorm M + nuclearNorm N := by sorry
end MinRankRecovery.Recovery
Source
Recht, Fazel & Parrilo, arXiv:0706.4138v1, Lemma 2.3, p. 9
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.