Proof of Theorem 1.3, p. 8 — adding vectors can only decrease
ProvedPropVolSampling.Reduction.paddinglinear-algebraoptimal-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and such that is positive definite. Then
This is why step 4 of Algorithm 1, which pads a sampled set of size with arbitrary vectors, cannot hurt the guarantee.
Formalization Note Positive definiteness of the smaller Gram matrix is assumed; otherwise the page's objective is and the claim is trivial, while Lean's inverse is the junk .
Preamble
import Mathlib import Definitions.Def_PropVolSampling_Reduction_Model
Formal statement
namespace PropVolSampling.Reduction
open Matrix Finset
theorem padding {d n : ℕ} (V : Matrix (Fin d) (Fin n) ℝ) (S S' : Finset (Fin n)) (hSS' : S ⊆ S')
(hpd : (gram V S).PosDef) :
aObj (gram V S') ≤ aObj (gram V S) := by sorry
end PropVolSampling.Reduction
Source
Nikolov, Singh, Tantipongpipat, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, arXiv:1802.08318v5, p. 8, proof of Theorem 1.3, sentence after (5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.