Proof of Lemma 8.2, p. 12 — some unit x′ has ‖Ax′‖ ≤ √|f^A_{[n]−i}(i)|
ProvedCurvatureSubmod.CSSP.exists_unit_smallcolumn-subset-selectioncondition-numbercurvaturep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix with columns , and let be the column-subset selection objective. For every there is a unit vector , , with
A small marginal gain at therefore forces to be small. This is the other estimate behind Lemma 8.2.
Formalization Note No independence of the columns is assumed; the paper's argument does not use it.
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- Proof of Lemma 8.2, p. 12: some unit vector `x' ∈ ℝⁿ` has `‖Ax'‖ ≤ √|f^A_{[n]−i}(i)|`. -/
theorem exists_unit_small {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m)) (i : Fin n) :
∃ x : EuclideanSpace ℝ (Fin n), ‖x‖ = 1 ∧
‖applyA c x‖ ≤ Real.sqrt |marg (fA c) (Finset.univ.erase i) i| := 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, construction of x′
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.