- 马尔科夫链的近线性时间算法和有向图的新谱基元
本文提出了一种面向有向图的射影逼近概念,并利用该方法构建了一个广泛启发自 Peng-Spielman 的对称线性系统求解框架,通过结合近乎线性时间的稀疏化算法,得到求解定向 Laplacian 线性系统的近乎线性时间算法,本算法的时间复杂度 - 随机稀疏 Kaczmarz 方法的线性收敛
提出了一种新的随机稀疏 Kaczmarz 方法并证明了它在解决线性方程组,成分分解和低秩矩阵问题方面的线性收敛性,同时数值实验表明了其优越性。
- ICML通过移位反演预处理加速特征向量计算
该研究论文提出了一种基于随机优化和矩阵估计的算法,能够通过线性系统求解来计算矩阵(具有稳定秩)的顶部特征向量,并提供了更快的算法和改进的样本复杂度。
- 线性系统的随机迭代方法
该研究发展了一种基于随机迭代的方法来解决线性系统问题,并通过变化两个参数来恢复广泛的已知算法,并且在单个定理中证明了误差的指数收敛,并给出了预期迭代的精确公式。
- 随机扩展 Gauss-Seidel 和 Kaczmarz 方法的收敛性质
本文提供了关于 Kaczmarz method 和 Gauss-Seidel method 的完整理论,证明了它们在不同情形下的收敛性和推导出其变种算法的收敛性,同时证明了 Gauss-Seidel 在欠定系统情形下收敛到最小范数解。
- LSMR:一种用于稀疏最小二乘问题的迭代算法
介绍了一个用于求解线性系统和最小二乘问题的迭代方法 LSMR,可以处理稀疏矩阵和快速线性算子,以及探讨了该新迭代方法在额外可用内存的情况下的改进。
- 解线性方程组的量子算法
该研究探讨了解决稀疏矩阵线性系统的期望值问题,通过使用量子算法实现了在 poly (log N, kappa) 时间内运行,这是目前最佳经典算法的指数级改进。
- 大规模图的本地聚类算法及其在近似线性时间图分割中的应用
本文研究了大规模图的本地算法设计并提出了一种本地聚类算法,该算法可在几乎线性的时间内找到较好的簇,并基于该聚类算法提出了一种划分算法,进而设计了求解对称对角占优矩阵中线性系统的近线性算法,还提出了其他相关结果。
- 具有指数收敛的随机 Kaczmarz 算法
介绍了 Kaczmarz 方法的随机版本来解决一致、超定的线性问题,证明了它具有期望指数收敛速度,且速度不依赖于方程的数量,甚至只需知道随机的一小部分。