Efficient $\widetilde{O}(n/ε)$ Spectral Sketches for the Laplacian and its Pseudoinverse

In this paper we consider the problem of efficiently computing $ε$-sketches for the Laplacian and its pseudoinverse. Given a Laplacian and an error tolerance $ε$, we seek to construct a function $f$ such that for any vector $x$ (chosen obliviously from $f$), with high probability $(1-ε) x^\top A x \leq f(x) \leq (1 + ε) x^\top A x$ where $A$ is either the Laplacian or its pseudoinverse. Our goal is to construct such a sketch $f$ efficiently and to store it in the least space possible. We provide nearly-linear time algorithms that, when given a Laplacian matrix $\mathcal{L} \in \mathbb{R}^{n \times n}$ and an error tolerance $ε$, produce $\tilde{O}(n/ε)$-size sketches of both $\mathcal{L}$ and its pseudoinverse. Our algorithms improve upon the previous best sketch size of $\widetilde{O}(n / ε^{1.6})$ for sketching the Laplacian form by Andoni et al (2015) and $O(n / ε^2)$ for sketching the Laplacian pseudoinverse by Batson, Spielman, and Srivastava (2008). Furthermore we show how to compute all-pairs effective resistances from $\widetilde{O}(n/ε)$ size sketch in $\widetilde{O}(n^2/ε)$ time. This improves upon the previous best running time of $\widetilde{O}(n^2/ε^2)$ by Spielman and Srivastava (2008).