- 大矩阵的函数梯度
通过导出 Lanczos 和 Arnoldi 迭代的未知共轭系统,该研究利用 JAX 实现了用于科学机器学习模型的数值线性代数效率高的可微分算法,该算法成功地不需要特定问题的代码优化,并在不同领域如选取高斯过程模型和校准贝叶斯神经网络中表现 - 图神经网络与应用线性代数
稀疏矩阵计算是科学计算中无处不在的。近期对科学机器学习的兴趣使得人们自然而然地问及稀疏矩阵计算如何利用神经网络。然而,多层感知机(MLP)神经网络通常不适用于图形或稀疏矩阵计算。本文旨在为数值线性代数的读者介绍图神经网络(GNNs),并提供 - 高效交替最小化与带权低秩近似的应用
本研究提供了一种有效和稳健的交替最小化框架来解决线性代数和机器学习中的一些问题,关注于都市中加权矩阵的低秩矩阵近似问题,并将运行时间从之前的 n^2k^2 降至 n^2k。
- 广义特征值问题作为纳什均衡
本文提出了一个利用博弈理论建立广义特征值问题的 Top-k 模型,并给出了一种可并行化的算法,该算法的渐近收敛性能可达纳什平衡,在高维数据集上的计算复杂度为 O (dk)。研究表明该算法可以解决神经网络激活等种类的广义特征值问题实例。
- 线性草图的高效对称范数回归
提供了高效的算法来解决超定的线性回归问题,其中损失函数是对称范数(在符号反转和坐标置换下不变的范数),当损失函数为 Orlicz 范数时,算法产生一个 (1+ε)- 近似解,在输入稀疏时间内改进了先前已知的算法。
- 通过行列式均值分布估计逆黑塞矩阵
提出了一种纠正分布式优化和分布式数值线性代数中的倒置偏差的新方法 —— 行列式平均法。通过利用行列式对局部 Hessian 估计进行加权重新计算,然后进行平均,从而提高全局估计的准确性,其中包括应用于牛顿法和数据不确定范围内协方差矩阵的逆矩 - 利用海森矩阵特征值密度研究神经网络优化
研究优化过程中深度神经网络中 Hessian 谱的演化对动力学的影响,发现对于非批归一化网络,谱中的大量孤立特征值以及聚集在相应特征空间中的梯度的快速出现将影响优化速度,而批归一化网络中这两种效应几乎不存在。
- 大规模深度神经网络海森矩阵的全频谱:SGD 训练和样本规模的动态
使用最先进的高维数值线性代数工具来有效近似现代深度学习网络巨大参数空间上的 Hessian 谱,研究发现该 Hessian 具有 “尖峰” 行为,同时分别分析各项的训练动态和样本大小变化情况。
- 迭代反向体积抽样用于线性回归
这篇论文详细介绍了基于体积采样技术的线性回归问题解决方案,实验证明该算法不仅可行,而且精度较高。
- 在线和滑动窗口模型下的近似最优线性代数
本研究讨论了滑动窗口模型下的数值线性代数问题,提出了基于行采样的框架并使用随机化算法求解谱逼近、低秩逼近 / 投影成本保持、基于 l1 范数的子空间嵌入等问题,同时通过与在线模型的联系,提出了正文算法,并应用于列 / 行选择、主成分分析等问 - 列子集选择是 NP 完备问题
本研究探讨了矩阵 CSSP 问题在数字线性代数中的应用和算法复杂度,并证明了其为 NP 完全问题。
- 子采样牛顿法 I:全局收敛算法
本文论述了大规模优化问题中 Sub-sampling 的迭代算法,提供了 Hessian 和梯度子采样的收敛边界,使用随机数值线性代数来获得适当的采样策略,并为在大规模线性系统下近似更新的情况下的全局收敛结果提供了解决方案
- MM草图作为数值线性代数工具
本文综述了数值线性代数算法领域的最新进展,着重介绍了利用线性草图技术来进行矩阵压缩的方法,以加速解决原问题。文章讨论了最小二乘、鲁棒回归、低秩逼近和图稀疏化的问题,并优化了这些问题的不同变体。最后,文章探讨了草图方法的局限性。
- 低秩矩阵分解的随机算法:尖锐性能界限
本文研究文献中关于维数约减最常讨论的算法之一,即用低秩矩阵来近似输入矩阵的算法。我们介绍了 Martinsson 等人(2008)中算法的新颖分析方法,可以得出尖锐的估计和关于其性能的新见解。通过实验,我们证明了我们预测的紧密性与经验观测的 - 大矩阵谱密度的近似计算
通过数值线性代数的方法,本文定义了计算实对称矩阵的密度状态和谱密度的问题,并探讨了几种已知方法和联合一些新的现有方法的变化来估计谱密度的精确度。
- 指数随机变量的子空间嵌入和 Lp 回归
本文从子空间嵌入的角度出发,提出了一种构造常数扭曲率子空间嵌入的新方法,并将其应用于线性回归问题以及分布式计算中。
- 通过更稀疏的子空间嵌入实现更快的数值线性代数算法
本研究提出了一种 Oblivious Subspace Embedding (OSE) 技术以及两种 Oblivious Sparse Norm-Approximating Projections (OSNAPs) 技术,基于随机矩阵理论, - 快速矩阵排名算法与应用
本文介绍了一种随机算法来计算矩阵的秩,可以在线性时间内找到一组线性无关的列,并解决了动态矩阵更新问题。这种方法可以有效地应用于数值线性代数、组合优化和动态数据结构中。
- 求解配对和列交通时间以及 Katz 分数的快速矩阵计算
本研究利用数值线性代数方法,采用基于矩阵、矩估计和求积公式的方法,探讨了评估节点对之间的通勤时间和 Katz 得分的算法,并提出了一种从一个节点到图中所有其他节点的通勤时间和 Katz 得分近似估计方法。在 17 个真实图上的测试结果表明, - 大多数张量问题是 NP 难问题
证明了在数值线性代数中,许多高效可计算问题的多线性(张量)形式都是 NP 难的。其中包括决定一个双线性方程组的可行性,确定一个三阶张量是否具有给定的特征值,奇异值或谱范数;逼近特征值,特征向量,奇异向量或谱范数;确定三阶张量的秩或最佳秩 -