Lemma 8.1, p. 11 (monotone part) — S ↦ ‖proj_S(v)‖² is monotone increasing
ProvedCurvatureSubmod.CSSP.lemma_8_1_monotonelinear-algebramonotonep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1projectionsubmodular
Let be vectors in and let be arbitrary. For let be the orthogonal projection of onto . Then the set function
is monotone increasing: for all and .
This is the monotonicity half of Lemma 8.1. Enlarging enlarges the subspace, so the projection captures at least as much of .
Formalization Note Lemma 8.1 as printed also asserts that is submodular. That half is false and is not stated: with , in and one gets . Monotonicity is the marginal form of §2.1.
Preamble
import Mathlib import Definitions.Def_CurvatureSubmod_CSSP_Setting
Formal statement
namespace CurvatureSubmod.CSSP
/-- Lemma 8.1, p. 11, its monotonicity half: `S ↦ ‖proj_S(v)‖²` is monotone increasing.
The printed submodularity half is false (columns `e₁, e₁ + e₂`, `v = e₂`) and is not stated. -/
theorem lemma_8_1_monotone {m n : ℕ} (c : Fin n → EuclideanSpace ℝ (Fin m))
(v : EuclideanSpace ℝ (Fin m)) :
MonoInc (fun S : Finset (Fin n) => ‖proj c S v‖ ^ 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. 11, Lemma 8.1 (monotonicity part)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.