Proof of Theorem 1.3, p. 9 — as a ratio of -weighted Cauchy–Binet sums
ProvedPropVolSampling.Reduction.relaxation_ratiodeterminantsoptimal-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , a real matrix and with such that is positive definite. Then
This is the right-hand side of (7): the relaxation's objective at in the same Cauchy–Binet form as the expected objective of proportional volume sampling.
Formalization Note Positive definiteness of is assumed: otherwise the page's objective is while Lean's inverse is the junk . is the page's ; is added because is natural-number subtraction.
Preamble
import Mathlib import Definitions.Def_PropVolSampling_Reduction_Model
Formal statement
namespace PropVolSampling.Reduction
open Matrix Finset
theorem relaxation_ratio {d n : ℕ} (hd : 1 ≤ d) (V : Matrix (Fin d) (Fin n) ℝ) (x : Fin n → ℝ)
(hx : ∀ i, 0 ≤ x i) (hpd : (weightedGram V x).PosDef) :
aObj (weightedGram V x) =
(∑ T ∈ powersetCard (d - 1) (univ : Finset (Fin n)),
((colSub V T)ᵀ * colSub V T).det * xPow x T) /
(∑ R ∈ powersetCard d (univ : Finset (Fin n)),
((colSub V R)ᵀ * colSub V R).det * xPow x R) := by sorry
end PropVolSampling.Reduction
Source
Nikolov, Singh, Tantipongpipat, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, arXiv:1802.08318v5, p. 9, proof of Theorem 1.3, third display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.