Proof of Lemma 8.2, p. 11 — |f^A_∅(i)| = Σ_j ‖proj_{i}(c_j)‖²
ProvedCurvatureSubmod.CSSP.abs_marg_emptycolumn-subset-selectioncurvaturep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projection
Let have columns and let be the column-subset selection objective. For every , the marginal value of at the empty set satisfies
where is the orthogonal projection onto the line spanned by .
This is the first step of the proof of Lemma 8.2: the gain of the first column equals the total squared mass of the columns along .
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- Proof of Lemma 8.2, p. 11, first display: `|f^A_∅(i)| = Σ_j ‖proj_{i}(c_j)‖²`. -/
theorem abs_marg_empty {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m)) (i : Fin n) :
|marg (fA c) ∅ i| = ∑ j, ‖proj c {i} (c j)‖ ^ 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, proof of Lemma 8.2, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.