§8, p. 11 — f^A(S) = Σ_i (‖c_i‖² − ‖proj_S(c_i)‖²)
ProvedCurvatureSubmod.CSSP.fA_eq_sum_subcolumn-subset-selectionlinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projection
Let be the columns of a matrix , let denote the orthogonal projection onto , and let . Then for every ,
This rewrites the residual form of the column-subset selection objective as total squared column norm minus the captured squared norm, which is how the paper passes from to the projection functions of Lemma 8.1.
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- §8, p. 11, second line of the display defining `f^A`:
`f^A(S) = Σ_i (‖c_i‖² − ‖proj_S(c_i)‖²)`. -/
theorem fA_eq_sum_sub {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m)) (S : Finset (Fin n)) :
fA c S = ∑ i, (‖c i‖ ^ 2 - ‖proj c S (c i)‖ ^ 2) := by sorry
end CurvatureSubmod.CSSP
Source
Sviridenko, Vondrák, Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature (SODA 2015 version, Oct. 9, 2014), p. 11, §8, display defining f^A
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.