On Sketching Quadratic Forms
Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang · 2016
We undertake a systematic study of sketching a quadratic form: given an n x n matrix A, create a succinct sketch sk(A) which can produce (without further access to A) a multiplicative (1+ε)-approximation to xT A x for any desired query x ∈ Rn. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size θ(ε{-2 n), via the Johnson-Lindenstrauss lemma, achieving the "for each" guarantee, namely, for each query x, with a constant probability the sketch succeeds. (For the stronger "for all" guarantee, where the sketch succeeds for all x's simultaneously, again there are no non-trivial sketches.)