Proof of Theorem 1.3, p. 9 — expected objective under proportional volume sampling as a ratio of Cauchy–Binet sums
ProvedPropVolSampling.Reduction.expectation_ratiooptimal-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1volume-sampling
Let , a real matrix, a probability measure on , and assume the normaliser is positive. Let be proportional volume sampling with measure . Then
- ;
- ;
Together these bound the expected A-objective of the sampled set by , the left-hand side of (7).
Formalization Note The page writes "" in part 3. Equality fails when charges a set with : such has , so it is never sampled, but contributes to the right-hand side. The inequality is what the proof needs and is what is stated. Sets with singular have sampling probability , so Lean's junk value of their objective does not enter the expectation. 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 expectation_ratio {d n : ℕ} (hd : 1 ≤ d) (V : Matrix (Fin d) (Fin n) ℝ) (k : ℕ)
(μ : Finset (Fin n) → ℝ) (hμ : IsSetDist k μ) (hZ : 0 < pvsNormalizer V μ) :
(∑ S, μ S * Ek (d - 1) (gram V S) =
∑ T ∈ powersetCard (d - 1) (univ : Finset (Fin n)),
((colSub V T)ᵀ * colSub V T).det * prSup μ T) ∧
(pvsNormalizer V μ =
∑ R ∈ powersetCard d (univ : Finset (Fin n)),
((colSub V R)ᵀ * colSub V R).det * prSup μ R) ∧
pvsExpect V μ (fun S => aObj (gram V S)) ≤
(∑ S, μ S * Ek (d - 1) (gram V S)) / pvsNormalizer V μ := 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, first and second displays (first display printed with "="; stated with "≤")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.