Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator
复制标题
平衡分离器的指数逼近、lanczos 方法和 Õ(m) 时间谱算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
L. Orecchia;Sushant Sachdeva;Nisheeth K. Vishnoi
对于平衡（边）分离器问题，我们给出了一种新的谱近似算法，即给定图G，一个常数平衡B ∈（0，1/2]，一个参数γ，或者在G中找到一个电导率为O（B）的Ω（b）平衡割，或者输出一个证明，证明G中所有的b平衡割的电导率至少为γ，并且在时间上运行~O（m）.这就解决了平衡分离器的渐近最优谱算法的设计问题。我们的算法依赖于一个变种的热核随机游走，并需要，作为一个子程序，一个算法来计算exp（-L）v，其中L是拉普拉斯算子的图形相关的G和v是一个向量。计算矩阵指数向量积的算法有效地构成了我们的下一组结果。我们的主要结果是一个新的算法，它计算了一个很好的近似exp（-A）v的一类对称半正定（PSD）矩阵A和一个给定的向量v，在时间上大约~O（mA），独立于A的范数，其中mA是非零元素的数量。这使用，在一个非平凡的方式，结果Spielman和滕对逆对称和对角占优矩阵在O（mA）时间。最后，使用旧的和新的一致逼近e-x，我们展示了如何通过Lanczos方法获得一个简单的算法来计算对称PSD矩阵的exp（-A）v，该算法在时间上运行大约为O（tA），其中tA是给定向量w计算向量Aw所需的时间。作为应用，我们得到了时间为O（m/<$γ）的平衡分离器的一个简单实用的算法，其输出电导为O（<$γ）。后者算法匹配的运行时间，但改进了Andersen和Peres为平衡分离器的基于进化集的算法的近似保证。
We give a novel spectral approximation algorithm for the balanced (edge-)separator problem that, given a graph G, a constant balance b ∈ (0,1/2], and a parameter γ, either finds an Ω(b)-balanced cut of conductance O(√γ) in G, or outputs a certificate that all b-balanced cuts in G have conductance at least γ, and runs in time ~O(m). This settles the question of designing asymptotically optimal spectral algorithms for balanced separator. Our algorithm relies on a variant of the heat kernel random walk and requires, as a subroutine, an algorithm to compute exp(-L)v where L is the Laplacian of a graph related to G and v is a vector. Algorithms for computing the matrix-exponential-vector product efficiently comprise our next set of results. Our main result here is a new algorithm which computes a good approximation to exp(-A)v for a class of symmetric positive semidefinite (PSD) matrices A and a given vector v, in time roughly ~O(mA), independent of the norm of A, where mA is the number of non-zero entries of A. This uses, in a non-trivial way, the result of Spielman and Teng on inverting symmetric and diagonally-dominant matrices in ~O(mA) time. Finally, using old and new uniform approximations to e-x we show how to obtain, via the Lanczos method, a simple algorithm to compute exp(-A)v for symmetric PSD matrices that runs in time roughly O(tA⋅ √norm(A)), where tA is the time required for the computation of the vector Aw for given vector w. As an application, we obtain a simple and practical algorithm, with output conductance O(√γ), for balanced separator that runs in time O(m/√γ). This latter algorithm matches the running time, but improves on the approximation guarantee of the Evolving-Sets-based algorithm by Andersen and Peres for balanced separator.