Inequality (5), p. 8 —
ProvedPropVolSampling.Reduction.inequality_5Let be integers and a real matrix. Let with be such that is positive definite, and let be a probability measure on that is -approximate -wise independent with respect to , with positive normaliser . If is proportional volume sampling with measure , then
Applied to an optimal solution of the relaxation (1)–(3), the right-hand side is ; this is the core of Theorem 1.3.
Formalization Note Approximate independence is in the cross-multiplied form of Definition 1.2. Positivity of is assumed so that is a probability distribution, and positive definiteness of so that the right-hand side is the page's finite value rather than Lean's junk . is added because is natural-number subtraction.
import Mathlib import Definitions.Def_PropVolSampling_Reduction_Model
namespace PropVolSampling.Reduction
open Matrix Finset
theorem inequality_5 {d n : ℕ} (V : Matrix (Fin d) (Fin n) ℝ) (k : ℕ) (hd : 1 ≤ d) (hdk : d ≤ k)
(hkn : k ≤ n) (x : Fin n → ℝ) (hx : IsRelaxFeasible k x) (hpd : (weightedGram V x).PosDef)
(μ : Finset (Fin n) → ℝ) (hμ : IsSetDist k μ) (α : ℝ) (hα : IsApproxIndep d α x μ)
(hZ : 0 < pvsNormalizer V μ) :
pvsExpect V μ (fun S => aObj (gram V S)) ≤ α * aObj (weightedGram V x) := by sorry
end PropVolSampling.Reduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.