Proof of Lemma 8.2, p. 12 — |f^A_{[n]−i}(i)| = ‖c_i − proj_{[n]−i}(c_i)‖²
ProvedCurvatureSubmod.CSSP.abs_marg_topcolumn-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 satisfies
the squared distance from to the span of the other columns.
This is the second step of the proof of Lemma 8.2: the last column's gain is its distance to the other columns.
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- Proof of Lemma 8.2, p. 12: `|f^A_{[n]−i}(i)| = ‖c_i − proj_{[n]−i}(c_i)‖²`. -/
theorem abs_marg_top {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m)) (i : Fin n) :
|marg (fA c) (Finset.univ.erase i) i| =
‖c i - proj c (Finset.univ.erase i) (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. 12, proof of Lemma 8.2, display for f^A_{[n]−i}(i)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.