论文标题
几何图上线性代数的算法和硬度
Algorithms and Hardness for Linear Algebra on Geometric Graphs
论文作者
论文摘要
对于功能$ \ MATHSF {k}：\ Mathbb {r}^{d} \ times \ times \ Mathbb {r}^{d}^{d} \ to \ Mathbb {r} _ {\ geq 0} $ \ Mathbb {r}^d $ of $ n $点，$ \ mathsf {k} $ graph $ g_p $ $ p $是$ n $ nodes上的完整图，其中nodes $ i $和$ j $之间的重量由$ \ m athsf {k}（k}（x_i，x_jj）给出。在本文中，我们启动了这些图表上有效的光谱图理论何时进行的研究。我们调查是否可以在$ n^{1+o（1）} $时间中解决以下问题的$ \ Mathsf {k} $ - Graph $ g_p $时，$ d <n^{o（1）} $： 美元 $ \ bullet $找到$ g_p $的光谱弹药器 $ \ bullet $在$ g_p $ s laplacian矩阵中求解laplacian系统 对于这些问题，我们考虑了$ \ mathsf {k}（u，v）= f（\ | u-v \ | _2^2）$的所有功能。我们为许多这样的$ \ mathsf {k} $提供算法和可比的硬度结果，包括高斯内核，神经切线内核等。 For example, in dimension $d = Ω(\log n)$, we show that there is a parameter associated with the function $f$ for which low parameter values imply $n^{1+o(1)}$ time algorithms for all three of these problems and high parameter values imply the nonexistence of subquadratic time algorithms assuming Strong Exponential Time Hypothesis ($\mathsf{SETH}$),给定$ f $的自然假设。 作为结果的一部分，我们还表明，在广泛的函数$ f $的$ \ mathsf {seth} $上，闻名的greengard和rokhlin的尺寸$ d $的指数依赖无法改善。据我们所知，这是关于快速多极方法证明的第一个正式限制。
For a function $\mathsf{K} : \mathbb{R}^{d} \times \mathbb{R}^{d} \to \mathbb{R}_{\geq 0}$, and a set $P = \{ x_1, \ldots, x_n\} \subset \mathbb{R}^d$ of $n$ points, the $\mathsf{K}$ graph $G_P$ of $P$ is the complete graph on $n$ nodes where the weight between nodes $i$ and $j$ is given by $\mathsf{K}(x_i, x_j)$. In this paper, we initiate the study of when efficient spectral graph theory is possible on these graphs. We investigate whether or not it is possible to solve the following problems in $n^{1+o(1)}$ time for a $\mathsf{K}$-graph $G_P$ when $d < n^{o(1)}$: $\bullet$ Multiply a given vector by the adjacency matrix or Laplacian matrix of $G_P$ $\bullet$ Find a spectral sparsifier of $G_P$ $\bullet$ Solve a Laplacian system in $G_P$'s Laplacian matrix For each of these problems, we consider all functions of the form $\mathsf{K}(u,v) = f(\|u-v\|_2^2)$ for a function $f:\mathbb{R} \rightarrow \mathbb{R}$. We provide algorithms and comparable hardness results for many such $\mathsf{K}$, including the Gaussian kernel, Neural tangent kernels, and more. For example, in dimension $d = Ω(\log n)$, we show that there is a parameter associated with the function $f$ for which low parameter values imply $n^{1+o(1)}$ time algorithms for all three of these problems and high parameter values imply the nonexistence of subquadratic time algorithms assuming Strong Exponential Time Hypothesis ($\mathsf{SETH}$), given natural assumptions on $f$. As part of our results, we also show that the exponential dependence on the dimension $d$ in the celebrated fast multipole method of Greengard and Rokhlin cannot be improved, assuming $\mathsf{SETH}$, for a broad class of functions $f$. To the best of our knowledge, this is the first formal limitation proven about fast multipole methods.
