Efficient Õ(n/∊) Spectral Sketches for the Laplacian and its Pseudoinverse
Arun Jambulapati, Aaron Sidford · Society for Industrial and Applied Mathematics eBooks · 2018
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⊤ Ax ≤ f(x) ≤ (1 + ∊)x⊤ Ax 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 ℒ ∊ ℝn×n and an error tolerance ∊, produce Õ(n/∊)-size sketches of both ℒ and its pseudoinverse. Our algorithms improve upon the previous best sketch size of Õ(n/∊1.6) for sketching the Laplacian form by [1] and O(n/∊2) for sketching the Laplacian pseudoinverse by [2]. Furthermore we show how to compute all-pairs effective resistances from our Õ(n/∊) size sketch in Õ(n2/∊) time. This improves upon the previous best running time of Õ(n2/∊2) by [3].