Sublinear time spectral density estimation
Sublinear time spectral density estimation
复制标题
DOI：
10.1145/3519935.3520009
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
V. Braverman;A. Krishnan;Christopher Musco
中科院分区：
文献类型：
--
作者：
V. Braverman;A. Krishnan;Christopher Musco
本文提出了一种新的次线性时间算法来逼近n× n归一化图邻接矩阵或Laplacian矩阵的谱密度（特征值分布）。该算法在给定样本访问图的情况下，在O（n·（1/n））时间内恢复到Wasserstein-1距离的1/2精度。这一结果对大卫科恩-施泰纳、孔伟豪、克里斯蒂安·索勒和格雷戈里·瓦利安特（Gregory Valiant，2018）最近的工作表示赞赏，他们获得了一个运行时间与n无关，但在1/n内呈指数关系的解。我们推测，尺寸依赖性和精度之间的权衡是固有的。我们的方法是简单的，实验效果很好。它是基于Chebyshev多项式矩匹配方法，雇员随机估计矩阵迹。我们证明了，对于任何厄米特A，这种矩匹配方法返回一个近似的谱密度仅使用O（1/1）矩阵向量积与A。通过利用切比雪夫多项式三项递归的稳定性，我们证明了该方法是适合使用粗糙的近似矩阵向量乘积。我们的次线性时间算法如下结合这一结果与一种新的采样算法近似矩阵向量产品与归一化图形邻接矩阵。独立的利益，我们展示了一个类似的结果，广泛使用的核多项式方法（KPM），证明这种实用的算法几乎匹配的理论保证，我们的矩匹配方法。我们的分析使用的工具，从杰克逊的开创性工作的近似与积极的多项式内核。
We present a new sublinear time algorithm for approximating the spectral density (eigenvalue distribution) of an n× n normalized graph adjacency or Laplacian matrix. The algorithm recovers the spectrum up to є accuracy in the Wasserstein-1 distance in O(n· (1/є)) time given sample access to the graph. This result compliments recent work by David Cohen-Steiner, Weihao Kong, Christian Sohler, and Gregory Valiant (2018), which obtains a solution with runtime independent of n, but exponential in 1/є. We conjecture that the trade-off between dimension dependence and accuracy is inherent. Our method is simple and works well experimentally. It is based on a Chebyshev polynomial moment matching method that employees randomized estimators for the matrix trace. We prove that, for any Hermitian A, this moment matching method returns an є approximation to the spectral density using just O(1/є) matrix-vector products with A. By leveraging stability properties of the Chebyshev polynomial three-term recurrence, we then prove that the method is amenable to the use of coarse approximate matrix-vector products. Our sublinear time algorithm follows from combining this result with a novel sampling algorithm for approximating matrix-vector products with a normalized graph adjacency matrix. Of independent interest, we show a similar result for the widely used kernel polynomial method (KPM), proving that this practical algorithm nearly matches the theoretical guarantees of our moment matching method. Our analysis uses tools from Jackson’s seminal work on approximation with positive polynomial kernels.