本文介绍了一些概率算法,来完成线性代数计算,如矩阵分解和线性系统求解,覆盖了在实际问题中得到证明的技术和理论知识,包括规范估计,采样的矩阵逼近,线性回归问题,低秩逼近,亚空间迭代和 Krylov 方法,误差估计和自适应性,插值和 CUR 分解,Nystrom 逼近以及核矩阵的逼近等等,特别适用于机器学习和科学计算。
Feb, 2020
本文基于 2016 年 Park City 数学研究所数据数学暑期学校的随机数值线性代数讲座。
Dec, 2017
本文详细介绍了随机矩阵算法理论的最新进展以及这些思想在大规模数据分析实际问题求解中的应用,重点放在一些简单的核心思想上,这些思想不仅支撑了最近的理论发展,也使得这些工具在大规模数据应用中非常有用;本文特别关注了统计上的杠杆作用这一概念,它不仅可以用于识别异常值,而且还可以帮助开发更好的矩阵算法,这些方法可以解决诸如线性最小二乘问题和低秩矩阵逼近问题。与之前最佳确定性算法相比,最终得到的随机算法的最坏运行时间渐近更快;它们的数值实现在时间上更快;或者它们可以在现有数值算法无法运行的并行计算环境中运行。
Apr, 2011
使用 LightOn Optical Processing Units 实现随机化降维可显著加速 Randomized Numerical Linear Algebra,例如 RandSVD 或 trace estimators,并且精度损失可以忽略不计。
Apr, 2021
在大规模数据时代,分布式系统为处理海量数据提供了可靠的、实惠的存储和可扩展的处理,本文主要介绍发展和实施随机矩阵算法在大规模并行和分布式环境中的最新工作,着重讨论随机投影和随机采样算法在极度超定的 l1 和 l2 回归问题中的实际应用和理论基础。
Feb, 2015
本文针对 least-squares 问题,利用渐进分析推导出一般采样估计器的渐近分布,并探讨了如何构建置信区间和假设检验,最后基于该理论提出了两个标准来确定最佳的采样概率分布。
该论文展示了如何使用基于代理模型的自动调整方法来解决 RandNLA 算法中参数选择的基本问题,并详细研究了基于代理模型的自动调整方法在基于随机预处理的最小二乘法中的应用。实验结果表明,我们的基于代理模型的自动调整方法可以以较少的调整成本实现接近最优的性能,同时适用于任何类型的 RandNLA 算法。
Aug, 2023
本文综述了数值线性代数算法领域的最新进展,着重介绍了利用线性草图技术来进行矩阵压缩的方法,以加速解决原问题。文章讨论了最小二乘、鲁棒回归、低秩逼近和图稀疏化的问题,并优化了这些问题的不同变体。最后,文章探讨了草图方法的局限性。
Nov, 2014
通过采用简单的 Hessian 初始化和自适应训练区域分配,本论文介绍了一种名为 RANL 的新颖高效算法,该算法克服了 Newton 方法在大规模和异构学习环境中的限制,展现了出色的收敛性能,有效地适应可用资源并保持高效率,使其成为实际场景中的分布式随机优化的有希望的方法。
本研究概述了随机数值线性代数 (Randomized Numerical Linear Algebra) 和行列式点过程 (Determinantal Point Processes) 两个看似不相关的数学领域之间新的深入而有益的联系,以及这些联系带来的新保证和改进的算法,并且介绍了 DPP 对于经典线性代数任务,如最小二乘回归、低秩逼近和 Nystrom 方法的应用。
May, 2020