Proof of Lemma 8.2, p. 12 — κ²(A) ≥ f^A_∅(i)/f^A_{[n]−i}(i) for each i ∈ [n]
ProvedCurvatureSubmod.CSSP.condNum_sq_gecolumn-subset-selectioncondition-numbercurvaturep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix with linearly independent columns , let be the column-subset selection objective, and let be its condition number. Then for each ,
Both marginal values are negative, so the left side is the ratio of their absolute values. The denominator is nonzero because, under independence, is not in the span of the other columns. This is the inequality from which the curvature bound of Lemma 8.2 is read off.
Formalization Note The quotient is real division. Independence of the columns (the page's "non-singular") makes the denominator strictly negative, so Lean's convention never applies.
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- Proof of Lemma 8.2, p. 12, conclusion: for independent columns,
`κ²(A) ≥ f^A_∅(i) / f^A_{[n]−i}(i)` for each `i ∈ [n]` (the denominator is `< 0`). -/
theorem condNum_sq_ge {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m))
(hc : LinearIndependent ℝ c) (i : Fin n) :
marg (fA c) ∅ i / marg (fA c) (Finset.univ.erase i) i ≤ condNum c ^ 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, last paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.