Efficient $\widetilde{O}(n/ε)$ Spectral Sketches for the Laplacian and its Pseudoinverse
Preprint
Abstract
In this paper we consider the problem of efficiently computing $\epsilon$-sketches for the Laplacian and its pseudoinverse. Given a Laplacian and an error tolerance $\epsilon$, we seek to construct a function $f$ such that for any vector $x$ (chosen obliviously from $f$), with high probability $(1-\epsilon) x^\top A x \leq f(x) \leq (1 + \epsilon) 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 $\epsilon$, produce $\tilde{O}(n/\epsilon)$-size sketches of both $\mathcal{L}$ and its pseudoinverse. Our algorithms improve upon the previous best sketch size of $\widetilde{O}(n / \epsilon^{1.6})$ for sketching the Laplacian form by Andoni et al (2015) and $O(n / \epsilon^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/\epsilon)$ size sketch in $\widetilde{O}(n^2/\epsilon)$ time. This improves upon the previous best running time of $\widetilde{O}(n^2/\epsilon^2)$ by Spielman and Srivastava (2008).
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- Sampling random spanning trees faster than matrix multiplication2017
- Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs2017
- Simple Parallel and Distributed Algorithms for Spectral Graph SparsificationACM Transactions on Parallel Computing, 2016
- Fast Generation of Random Spanning Trees and the Effective Resistance Metric2014
- An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations2013
- Cover times, blanket times, and majorizing measures2011
- Faster Generation of Random Spanning Trees2009
- Relative-Error $CUR$ Matrix DecompositionsSIAM Journal on Matrix Analysis and Applications, 2008
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems2004