Identity (4), p. 8 —
ProvedPropVolSampling.Reduction.identity_4determinantslinear-algebrap2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real matrix and . With the -th elementary symmetric polynomial of the eigenvalues of and the -element subsets of ,
This extends the Cauchy–Binet formula from the determinant () to all ; it is the identity that turns both the expected objective of proportional volume sampling and the relaxation's objective into sums over - and -subsets.
Formalization Note is Multiset.esymm k of the real roots of the characteristic polynomial; () and () are symmetric, so the characteristic polynomials split. The identity is stated for every (both sides vanish for ).
Preamble
import Mathlib import Definitions.Def_PropVolSampling_Reduction_Model
Formal statement
namespace PropVolSampling.Reduction
open Matrix Finset
theorem identity_4 {d n : ℕ} (V : Matrix (Fin d) (Fin n) ℝ) (k : ℕ) :
Ek k (V * Vᵀ) = Ek k (Vᵀ * V) ∧
Ek k (Vᵀ * V) = ∑ S ∈ powersetCard k (univ : Finset (Fin n)),
((colSub V S)ᵀ * colSub V S).det := by sorry
end PropVolSampling.Reduction
Source
Nikolov, Singh, Tantipongpipat, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, arXiv:1802.08318v5, p. 8, identity (4)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.