§2, p. 7 —
ProvedPropVolSampling.Reduction.cp_le_optconvex-relaxationoptimal-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and let be an optimal solution of the relaxation
with finite value . Then for every with and positive definite,
In particular .
The relaxation is a lower bound for the A-optimal design problem; it is the benchmark against which Theorem 1.3 measures the sampled set.
Formalization Note is the minimum of over -sets, with value on sets with singular ; the statement quantifies over the -sets with positive definite Gram matrix instead of taking an infimum, which avoids Lean's junk value of the inverse.
Preamble
import Mathlib import Definitions.Def_PropVolSampling_Reduction_Model
Formal statement
namespace PropVolSampling.Reduction
open Matrix Finset
theorem cp_le_opt {d n : ℕ} (V : Matrix (Fin d) (Fin n) ℝ) (k : ℕ) (x : Fin n → ℝ)
(hx : IsRelaxOptimal V k x) (S : Finset (Fin n)) (hS : S.card = k) (hpd : (gram V S).PosDef) :
aObj (weightedGram V x) ≤ 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. 7, §2, "CP ≤ OPT" (after (1)–(3))
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.