Theorem 5.2 — one-pass diversity-index estimator
OpenCosDensity.Supplement.theorem_5_2complexity-theorycosine-similarityfrequency-momentsp2o-gran-per-chapterp2o-plan-paperp2o-v1streaming-algorithms
Let , and let be a nonempty stream of nonzero vectors in with pairwise nonnegative cosine similarities. Set
and let be the ceiling of
There is a one-pass rejection-sampling algorithm using at most
real words that, with probability at least , does not overflow and returns a -approximation to .
Differences from the source:
- encoding: words → the explicit Algorithm 1 cap with the printed and ; reason: multiplying the maximum retained tuples by their stored scalars gives the displayed asymptotic bound
- encoding: Algorithm 1 returns
OVERFLOWon cap violation → successful seeds have an outputsome estimate; reason: this simultaneously records no overflow and the approximation event
Preamble
import Definitions.Def_CosDensity_Stream import Definitions.Def_CosDensity_Supplement_diversityIndex import Definitions.Def_CosDensity_Supplement_WordStreamAlg open scoped RealInnerProductSpace
Formal statement
namespace CosDensity.Supplement
set_option autoImplicit false
/-- Q. Zhang, *Frequency Moments Beyond Equality: Streaming Cosine Density Moments*,
arXiv:2609.06925 (held version, sha256 f4d4df22…), Algorithm 1 and Theorem 5.2,
pp.16–17 (PDF pp.17–18).
The rejection-sampling diversity estimator uses the paper's explicit `lambda` and `Nmax`. With
probability at least `1-delta` it neither overflows nor fails the `(1+epsilon)` guarantee. The word
bound counts the vector sum and, for every retained sample, its `d` coordinates, random threshold,
and current density. -/
theorem theorem_5_2 :
∀ (epsilon delta : ℝ), 0 < epsilon → epsilon < 1 → 0 < delta → delta < 1 →
∀ (d n : ℕ), 0 < n →
let lambda : ℝ := 8 / (3 * epsilon ^ 2) * Real.log (4 / delta)
let Nmax : ℕ := Nat.ceil
(lambda * d + Real.sqrt (2 * lambda * d * Real.log (2 * n / delta)) +
(2 / 3 : ℝ) * Real.log (2 * n / delta))
∃ A : WordStreamAlg (EuclideanSpace ℝ (Fin d)),
A.words ≤ d + (d + 2) * Nmax + 4 ∧
∀ P : List (EuclideanSpace ℝ (Fin d)),
P.length = n → (∀ x ∈ P, x ≠ 0) → CosDensity.NonnegCosine P →
A.Succeeds (fun omega => ∃ estimate : ℝ,
A.estimate omega P = some estimate ∧
CosDensity.IsApprox epsilon (diversityIndex P) estimate)
(ENNReal.ofReal (1 - delta)) := by sorry
end CosDensity.Supplement
Source
Q. Zhang, Frequency Moments Beyond Equality: Streaming Cosine Density Moments, arXiv:2609.06925 (held version, sha256 f4d4df22…), Algorithm 1 and Theorem 5.2, pp.16–17 (PDF pp.17–18)