(B.6) — μξ < 1/6 makes the γ-range of Theorem 2 nonempty
ProvedRankSparsity.Recovery.eq_B_6convex-relaxationmatrix-decompositionnuclear-normp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-plus-low-rank
Throughout, are real square matrices, is a compact singular value decomposition with having orthonormal columns and , is the space of matrices supported inside , , and are the incoherence quantities (1.2) and (1.1), is the spectral norm and the largest entry in magnitude.
If and , then
So the interval of trade-off parameters in Theorem 2 is nonempty.
Formalization Note The hypothesis is added because the right-hand side divides by ; in Lean . It holds whenever .
Preamble
import Definitions.Def_matrix_completion_tangent import Definitions.Def_RankSparsity_Recovery_Setup open MatrixCompletion
Formal statement
namespace RankSparsity.Recovery
/-- (B.6), p. 18: if `ξ(B⋆) μ(A⋆) < 1/6` (and `μ(A⋆) > 0`) the range of `γ` in
Theorem 2 is nonempty. -/
theorem eq_B_6 {n r : ℕ} (Astar Bstar : RealMatrix n n) (S : SVD Bstar r)
(h : xi S * mu Astar < 1 / 6) (hmu : 0 < mu Astar) :
xi S / (1 - 4 * xi S * mu Astar) < (1 - 3 * xi S * mu Astar) / mu Astar := by sorry
end RankSparsity.Recovery
Source
Chandrasekaran, Sanghavi, Parrilo, Willsky, Rank-Sparsity Incoherence for Matrix Decomposition, arXiv:0906.2220v1, Appendix B, proof of Theorem 2, (B.6), p. 18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.