On Sketching Quadratic Forms

Abstract

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 to $A$) a multiplicative $(1+\epsilon )$-approximation to $x^{T}Ax$ for any desired query $x\in {\mathbb{R}}^n$. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size $\Theta ({\epsilon }^{-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.) We design significantly better sketches for the important subclass of graph Laplacian matrices, which we also extend to symmetric diagonally dominant matrices. A sequence of work culminating in that of Batson, Spielman, and Srivastava (SIAM Review, 2014), shows that by choosing and reweighting $O({\epsilon }^{-2}n)$ edges in a graph, one achieves the "for all" guarantee. Our main results advance this front. $\bullet$ For the "for all" guarantee, we prove that Batson et al.'s bound is optimal even when we restrict to "cut queries" $x\in \{0,1{\}}^n$. In contrast, previous lower bounds showed the bound only for {\em spectral-sparsifiers}. $\bullet$ For the "for each" guarantee, we design a sketch of size $\tilde{O}({\epsilon }^{-1}n)$ bits for "cut queries" $x\in \{0,1{\}}^n$. We prove a nearly-matching lower bound of $\Omega ({\epsilon }^{-1}n)$ bits. For general queries $x\in {\mathbb{R}}^n$, we construct sketches of size $\tilde{O}({\epsilon }^{-1.6}n)$ bits.

46 pages; merging of arXiv:1403.7058 and arXiv:1412.8225

Cited by in corpus (17)

• Dynamic Streaming Spectral Sparsification in Nearly Linear Time and Space
• Computing exact minimum cuts without knowing the graph
• Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices
• Sparsification of Binary CSPs
• Faster Spectral Sparsification in Dynamic Streams
• Sketching and Clustering Metric Measure Spaces
• Universal Streaming of Subset Norms
• Gaussian Sketching yields a J-L Lemma in RKHS
• Towards Tight Bounds for Spectral Sparsification of Hypergraphs
• Additive Sparsification of CSPs
• Near Optimal Linear Algebra in the Online and Sliding Window Models
• Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
• Sparsification of Two-Variable Valued CSPs
• Non-PSD Matrix Sketching with Applications to Regression and Optimization
• Online Spectral Approximation in Random Order Streams
• Tight Bounds for the Subspace Sketch Problem with Applications