Lemma 2.1, p. 7 —
ProvedPropVolSampling.Reduction.lemma_2_1determinantsoptimal-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and with for all . For write for the submatrix of columns , , and for the matrix with columns , . If , then
It converts the -weighted Cauchy–Binet sums of the relaxation's matrix into unweighted Gram determinants times monomials , which is what makes them comparable with the sampling probabilities.
Formalization Note The page takes (Algorithm 1, step 2); nonnegativity is stated as a hypothesis so that .
Preamble
import Mathlib import Definitions.Def_PropVolSampling_Reduction_Model
Formal statement
namespace PropVolSampling.Reduction
open Matrix Finset
theorem lemma_2_1 {d n : ℕ} (V : Matrix (Fin d) (Fin n) ℝ) (x : Fin n → ℝ) (hx : ∀ i, 0 ≤ x i)
(T : Finset (Fin n)) (hT : T.card ≤ d) :
((colSubW V x T)ᵀ * colSubW V x T).det = xPow x T * ((colSub V T)ᵀ * colSub V T).det := by sorry
end PropVolSampling.Reduction
Source
Nikolov, Singh, Tantipongpipat, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, arXiv:1802.08318v5, p. 7, Lemma 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.