Proof of Lemma 8.2, p. 12 — some unit x has ‖Ax‖ ≥ √|f^A_∅(i)|
ProvedCurvatureSubmod.CSSP.exists_unit_largecolumn-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 large marginal gain at the empty set therefore forces to be large. This is one of the two estimates that combine into Lemma 8.2.
Formalization Note The statement is existential. The paper exhibits a specific , with proportional to , and its displayed computation uses , which fails when . The existential claim is true for every (choose with the sign of ). The index forces , so unit vectors exist.
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- Proof of Lemma 8.2, pp. 11–12: some unit vector `x ∈ ℝⁿ` has `‖Ax‖ ≥ √|f^A_∅(i)|`. -/
theorem exists_unit_large {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m)) (i : Fin n) :
∃ x : EuclideanSpace ℝ (Fin n), ‖x‖ = 1 ∧
Real.sqrt |marg (fA c) ∅ i| ≤ ‖applyA c x‖ := 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), pp. 11–12, proof of Lemma 8.2, Cauchy–Schwarz step
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.