Factorization of prefix indicators from near-orthogonal labels
ProvedMomentSearch.Supplement.dyadic_prefix_gram_factorizationdimension-reductionlinear-sketch
Let . Given labels in whose inner products approximate the equality indicator within , the prefix matrix admits a factorization through coordinates with entrywise additive error at most .
Preamble
import Mathlib
Formal statement
theorem MomentSearch.Supplement.dyadic_prefix_gram_factorization {n R : ℕ} (hn : 2 ≤ n) {η : ℝ} (hη : 0 ≤ η)
(g : Fin n → Fin R → ℝ)
(hg : ∀ a b, |(∑ s, g a s * g b s) - (if a = b then 1 else 0)| ≤ η) :
let h := Nat.clog 2 n + 1
∃ (U : Matrix (Fin n) (Fin (h*R)) ℝ) (V : Matrix (Fin (h*R)) (Fin n) ℝ),
∀ t j, |(U * V) t j - (if j ≤ t then 1 else 0)| ≤ (h:ℝ)*η := 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.