Near-orthogonal labels for interval indices
ProvedMomentSearch.Supplement.jl_near_orthogonal_labelsdimension-reductionlinear-sketch
For and , there exist real vectors whose Gram matrix is entrywise within of the identity, in dimension at most for one absolute constant .
Preamble
import Mathlib
Formal statement
theorem MomentSearch.Supplement.jl_near_orthogonal_labels : ∃ A : ℝ, 0 < A ∧ ∀ (n : ℕ), 2 ≤ n → ∀ η : ℝ, 0 < η → η < 1 →
∃ R : ℕ, (R : ℝ) ≤ A * Real.logb 2 n / η^2 ∧
∃ g : Fin n → Fin R → ℝ, ∀ a b,
|(∑ s, g a s * g b s) - (if a = b then 1 else 0)| ≤ η := by sorrySource
Megow, Stein, Verschae, Distributionally Robust Search: The Power of Information and the Limits of Moments, arXiv:2611.04559 (held version, sha256 fbfa4b43350dfaea073a9c0a9a0850a9955ea82082a7163a2db90cc48b9339e3), Theorem 27, p.35 (PDF p.37); construction preceding Theorem 27.