Identity (6), p. 8 —
ProvedPropVolSampling.Reduction.identity_6linear-algebraoptimal-designp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and let be a real symmetric matrix of rank (), with eigenvalues . Then
This observation of Avron and Boutsidis rewrites the A-objective as a ratio of two spectral elementary symmetric functions, to which identity (4) applies.
Formalization Note The page states (6) for a matrix of rank in a context where is defined for positive semidefinite matrices. The Lean statement assumes symmetric with (so the eigenvalues are real and the characteristic polynomial splits), which includes the positive definite case; 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 identity_6 {d : ℕ} (hd : 1 ≤ d) (M : Matrix (Fin d) (Fin d) ℝ) (hM : M.IsHermitian)
(hdet : M.det ≠ 0) :
aObj M = Ek (d - 1) M / M.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 (6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.