Efficient Õ(n/∊) Spectral Sketches for the Laplacian and its Pseudoinverse
Efficient Õ(n/∊) Spectral Sketches for the Laplacian and its Pseudoinverse
复制标题
拉普拉斯算子及其伪逆的有效 Õ(n/∊) 谱草图
DOI：
10.1137/1.9781611975031.159
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Aaron Sidford
中科院分区：
文献类型：
--
作者：
A. Jambulapati;Aaron Sidford
在本文中，我们考虑的问题，有效地计算的Laplacian及其伪逆的草图。给定一个拉普拉斯算子和一个误差容限λ，我们试图构造一个函数f，使得对于任何向量x（从f中选择任意一个），有很高的概率（1− λ）x <$Ax≤f（x）≤（1+ λ）x <$Ax其中A是拉普拉斯算子或其伪逆。我们的目标是有效地构造这样一个草图f，并将其存储在尽可能少的空间中。我们提供了近似线性时间算法，当给定一个拉普拉斯矩阵[EQUATION] ∈ Rn×n和一个误差容限ε时，产生O（n/ε）大小的[EQUATION]及其伪逆的草图。我们的算法改进了以前的最佳草图大小O（n/n = 1.6）的Laplacian形式的草图[1]和O（n/n = 2）的Laplacian伪逆的草图[2]。此外，我们展示了如何计算所有对有效电阻从我们的O（n/n）的大小草图在O（n2/n）的时间。这比以前的最佳运行时间O（n2/n2）提高了[3]。
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 [EQUATION] ∈ Rn×n and an error tolerance ϵ, produce O(n/ϵ)-size sketches of both [EQUATION] and its pseudoinverse. Our algorithms improve upon the previous best sketch size of O(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 O(n/ϵ) size sketch in O(n2/ϵ) time. This improves upon the previous best running time of O(n2/ϵ2) by [3].
DOI：
10.1109/focs.2015.24
发表时间：
2015-08
期刊：
2015 IEEE 56th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Y. Lee;He Sun
通讯作者：
Y. Lee;He Sun