随机数值线性代数算法采样估计的渐进分析
对大规模最小二乘问题的解决方法采用随机草图算法的统计和算法方面进行了考虑,提出了算法和统计两种框架并比较其性能,并且证明了在使用随机投影和随机抽样算法的情况下,当样本数为 $r$,且 $p<r<n$ 时,算法误差与原始问题的误差相同。
Jun, 2014
该论文展示了如何使用基于代理模型的自动调整方法来解决 RandNLA 算法中参数选择的基本问题,并详细研究了基于代理模型的自动调整方法在基于随机预处理的最小二乘法中的应用。实验结果表明,我们的基于代理模型的自动调整方法可以以较少的调整成本实现接近最优的性能,同时适用于任何类型的 RandNLA 算法。
Aug, 2023
本文考虑了最小二乘回归问题,提出了平均恒定步长随机梯度下降(也称最小均方误差)的性能的详细渐近分析。在强凸情况下,我们提供了一个高度渐近展开式。我们的分析提供了对随机逼近算法的新见解。
Nov, 2014
本文考虑从具有噪音的线性观测中学习系数向量 x0,通过解决 L1 惩罚的最小二乘问题,即 LASSO 或 BPDN 问题构造一种稀疏估计器 x',对于随机矩阵序列 A,我们证明了 LASSO 的规范风险趋于极限,并获得了该极限的一个显式表达式,并进行了实际数据矩阵的模拟,表明我们的结果在广泛的实际应用中都是相关的。
Aug, 2010
本文章研究了列子集选择的问题,通过分析随机化算法的谱范数重构,建立了一个新的、显式地以采样概率为依据的误差界,并通过解一个与误差界有关的约束优化问题来实现比传统采样分布更好的性能。数值模拟结果显示,新的采样分布可以比目前的算法在低秩矩阵近似和最小二乘近似方面表现得更好。
May, 2015
本文提出了一种新的回归方法,根据样本大小相对于稀疏性条件,在稀疏条件下获得每个精度矩阵条目的渐近高效估计,以解决高斯图模型中有关样本大小问题的难点,同时实现了整个精度矩阵的自适应速率最优估计及在潜变量的图模型中进行推断。
Sep, 2013
本文在大数据集上提出了算法杠杆效应的采样方法,通过样本采集分布来提高算法的计算效率,并在固定预测因子的线性回归模型中,提出了一种简单有效的框架来评估算法杠杆的统计性能。其结果表明核心的采样方法的统计性能既不会因为采用杠杆采样而主导也不会因采用均匀采样而优于杠杆采样,但其在最坏分析情况下,杠杆采样与均匀采样相比都能提供更好的结果。在理论性能基础上,本文提出并分析了两种新的杠杆算法,并在合成和真实数据集上进行了详细的实证评估。
Jun, 2013
本文介绍了一些概率算法,来完成线性代数计算,如矩阵分解和线性系统求解,覆盖了在实际问题中得到证明的技术和理论知识,包括规范估计,采样的矩阵逼近,线性回归问题,低秩逼近,亚空间迭代和 Krylov 方法,误差估计和自适应性,插值和 CUR 分解,Nystrom 逼近以及核矩阵的逼近等等,特别适用于机器学习和科学计算。
Feb, 2020
随机数值线性代数(RandNLA)在大矩阵的机器学习和数据分析应用中发挥着重要作用,本文提供了 RandNLA 的综合概述,以应对近期的理论和实践挑战。
Jun, 2024
从非线性和含噪声观测中估计一个低秩矩阵的任务中,我们证明了一个强普适性结果,表明贝叶斯最优性能可由一个等效的高斯模型表示,其先验参数完全由非线性函数的展开所确定。特别地,我们展示了为了准确重建信号,需要一个随着 $ N^{rac 12 (1-1/k_F)}$ 增长的信噪比,其中 $k_F$ 是函数的第一个非零 Fisher 信息系数。我们提供了最小可实现均方误差(MMSE)的渐近特征及一个类似于问题的线性版本的条件下能达到 MMSE 的近似传递算法。我们还提供了方法如主成分分析与贝叶斯去噪等的渐近误差,并将其与贝叶斯最优 MMSE 进行了比较。
Mar, 2024