Abstract
We undertake a systematic study of sketching a quadratic form: given an n × n matrix A, create a succinct sketch sk(A) which can produce (without further access to A) a multiplicative (1+ϵ)-Approximation to xTAx for any desired query x 2 Rn. While a general matrix does not admit nontrivial sketches, positive semi-definite (PSD) matrices admit sketches of size θ(ϵ-2n), 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 nontrivial 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(ϵ-2n) edges in a graph, one achieves the "for all" guarantee. Our main results advance this front. 1. For the "for all" guarantee, we prove that Batson et al.'s bound is optimal even when we restrict to "cut queries" x 2 f0; 1gn. Specifically, an arbitrary sketch that can (1 + ϵ)-estimate the weight of all cuts (S; S) in an n-vertex graph must be of size ω(ϵ2n) bits. Furthermore, if the sketch is a cut-sparsiffer (i.e., itself a weighted graph and the estimate is the weight of the corresponding cut in this graph), then the sketch must have (ϵ2n) edges. In contrast, previous lower bounds showed the bound only for spectral-sparsifiers. 2. For the "for each" guarantee, we design a sketch of size O (ϵ1n) bits for \cut queries" x 2 f0; 1gn. We apply this sketch to design an algorithm for the distributed minimum cut problem. We prove a nearly-matching lower bound of (ϵ1n) bits. For general queries x 2 Rn, we construct sketches of size O(ϵ1:6n) bits. Our results provide the first separation between the sketch size needed for the "for all" and "for each" guarantees for Laplacian matrices.