On Sketching Quadratic Forms

Alexandr Andoni, Jiecao Chen, Robert Krauthgamer +3

We undertake a systematic study of sketching a quadratic form: given an $n\times n$ matrix $A$, create a succinct sketch $\text{sk}(A)$ which can produce (without further access…