基于几何图的线性代数算法与难度

Nov, 2020

基于几何图的线性代数算法与难度

Algorithms and Hardness for Linear Algebra on Geometric Graphs

Josh Alman, Timothy Chu, Aaron Schild, Zhao Song

TL;DR该研究探讨了在一类称为 K - 图的特殊完全图上实现有效光谱图论的可能性，包括矩阵乘法，谱稀疏化，以及拉普拉斯系统解决方案等问题，并以多种函数为例进行算法开发和难度对比，并发现对于某些函数，即使采用著名的快速多极方法（Fast multipole method），在维度上存在无法克服的指数限制。

Abstract

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

spectral graph theory adjacency matrix laplacian matrix spectral sparsifier laplacian system

发现论文，激发创造

Twice-Ramanujan Sparsifiers

这篇论文证明了每个图形都有一个谱稀疏器，其边数与其顶点数成线性关系。特别地，通过 Laplacian matrices 构造的谱稀疏器提供了对图形的光谱映射，令其成为扩展图的推广。此外，该论文提供了一个简单的确定性多项式时间算法来构造这种稀疏器。

Aug, 2008

马尔科夫链的近线性时间算法和有向图的新谱基元

本文提出了一种面向有向图的射影逼近概念，并利用该方法构建了一个广泛启发自 Peng-Spielman 的对称线性系统求解框架，通过结合近乎线性时间的稀疏化算法，得到求解定向 Laplacian 线性系统的近乎线性时间算法，本算法的时间复杂度优于现有最优解。

Nov, 2016

图核函数

通过扩展线性代数到再生核希尔伯特空间（RKHS）并将其简化为 Sylvester 方程的算法，我们构建了一个统一的框架来研究图形内核，这使得内核计算的时间复杂度从 O（n^6）降至 O（n^3），当图形稀疏时，共轭梯度求解器或固定点迭代带入子立方域。

Jul, 2008

图的频谱稀疏化

本文提出了一种基于图拉普拉斯矩阵谱相似性的新型图稀疏化方法，证明了任何图都有近乎线性大小的谱稀疏化，并给出了一个可在几乎线性时间内构建谱稀疏化的算法，该方法的关键组成部分之一是对具有强保证的近乎线性时间图划分算法的使用。

Aug, 2008

固定角度的等角线

通过基于图形表示的数学优化模型及相关理论如：角度、谱图理论及各自的度量指标，解决了一个长期存在的关于等角线问题，并给出了其中包含的新结果。

Jul, 2019

多路谱分割和高阶 Cheeger 不等式

该论文研究了高阶重复本征值与稀疏割的关系，探讨了利用底部 k 个本征向量将顶点嵌入到 R^k 中，并应用几何考虑进行嵌入的聚类算法的理论基础，并证明了在所有图形中，存在一组大小不超过 2n/k 的集合，其扩展至多为 O (sqrt (λklogk))，从理论上提供了这些算法的近乎最优权衡。

Nov, 2011

基于 SDP 的线性大小谱稀疏化算法

本篇研究将提出一种计算效率更高的算法来构建图的 $(1 + ϵ)$- 频谱稀疏子图，该算法基于三种新技术，并使用新的潜力函数，通过半定规划求解构造单侧频谱稀疏子图。

Feb, 2017

超图拉普拉斯的光谱性质和近似算法

介绍了一个广义图拉普拉斯算子，旨在研究超图的特定组合属性，如多路扩展和直径，并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。

May, 2016

改进的 Cheeger 不等式：通过高阶谱间隙分析谱分裂算法

该研究证明了基于谱的划分算法可以在保证性能的同时，实现稀疏切割，同时将分析扩展到其他图划分问题中。

Jan, 2013

大维数据的核谱聚类

本文通过对核谱聚类方法进行首次分析，发现在维度和数量同时增长的情况下，核矩阵的归一化拉普拉斯矩阵与所谓的尖峰随机矩阵呈类似的渐近行为。通过一种如尖峰矩阵模型的可分离条件，证明该模型中的一些孤立特征值 - 特征向量对携带聚类信息。我们精确评估了这些特征值的位置和特征向量内容，在理论和实践角度揭示了核谱聚类中非常重要（有时相当破坏性）的方面。最后将结果与 MNIST 数据库中图像实际聚类的性能进行比较，证明了理论和实践之间的重要匹配。

Oct, 2015