§8, p. 11 (monotone part of the claim before Lemma 8.1) — f^A is monotone decreasing
ProvedCurvatureSubmod.CSSP.fA_monoDeccolumn-subset-selectionlinear-algebramonotonep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix with columns and let be the column-subset selection objective. Then is monotone decreasing:
Adding a column to the selected set can only shrink the residual. Monotonicity is what makes the total curvature of (Lemma 8.2) meaningful.
Formalization Note The paper's sentence also claims that is supermodular. That half is false and is not stated: with columns in , , and perturbing the last column to in gives a counterexample with independent columns.
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- §8, p. 11, sentence before Lemma 8.1, its monotonicity half: `f^A` is monotone decreasing.
The printed supermodularity half is false (columns `e₁, e₁ + e₂, 2e₂`) and is not stated. -/
theorem fA_monoDec {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m)) :
MonoDec (fA c) := 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, §8, sentence before Lemma 8.1 (monotonicity part)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.