Apr, 2011

矩阵和数据的随机算法

PDF
TL;DR本文详细介绍了随机矩阵算法理论的最新进展以及这些思想在大规模数据分析实际问题求解中的应用，重点放在一些简单的核心思想上，这些思想不仅支撑了最近的理论发展，也使得这些工具在大规模数据应用中非常有用；本文特别关注了统计上的杠杆作用这一概念，它不仅可以用于识别异常值，而且还可以帮助开发更好的矩阵算法，这些方法可以解决诸如线性最小二乘问题和低秩矩阵逼近问题。与之前最佳确定性算法相比，最终得到的随机算法的最坏运行时间渐近更快；它们的数值实现在时间上更快；或者它们可以在现有数值算法无法运行的并行计算环境中运行。
randomized matrix algorithmslarge-scale data analysisstatistical leveragelinear least-squares problemlow-rank matrix approximation problem
发现论文，激发创造
  • 在并行和分布式环境中实现随机矩阵算法

    在大规模数据时代，分布式系统为处理海量数据提供了可靠的、实惠的存储和可扩展的处理，本文主要介绍发展和实施随机矩阵算法在大规模并行和分布式环境中的最新工作，着重讨论随机投影和随机采样算法在极度超定的 l1 和 l2 回归问题中的实际应用和理论基础。

    Feb, 2015

  • 随机数值线性代数：基础与算法

    本文介绍了一些概率算法，来完成线性代数计算，如矩阵分解和线性系统求解，覆盖了在实际问题中得到证明的技术和理论知识，包括规范估计，采样的矩阵逼近，线性回归问题，低秩逼近，亚空间迭代和 Krylov 方法，误差估计和自适应性，插值和 CUR 分解，Nystrom 逼近以及核矩阵的逼近等等，特别适用于机器学习和科学计算。

    Feb, 2020

  • 利用随机性发现结构：构造近似矩阵分解的概率算法

    本文介绍了一种用于构建随机算法的模块化框架，以进行矩阵分解，通过随机抽样识别矩阵的大部分内容，并将输入矩阵压缩到子空间，这种方法在精度、速度和鲁棒性方面都比传统方法更具优势，能够更好地解决大数据集合的问题。

    Sep, 2009

  • 具有统计保证的随机降维

    研究论文通过研究快速执行和数据利用的算法，探索了大型模型和数据利用的有效维度减少策略，以及提高泛化和分布鲁棒性的数据增强方法。

    Oct, 2023

  • 机器学习中的随机数值线性代数的最新和即将发展

    随机数值线性代数（RandNLA）在大矩阵的机器学习和数据分析应用中发挥着重要作用，本文提供了 RandNLA 的综合概述，以应对近期的理论和实践挑战。

    Jun, 2024

  • 低秩矩阵分解的随机算法：尖锐性能界限

    本文研究文献中关于维数约减最常讨论的算法之一，即用低秩矩阵来近似输入矩阵的算法。我们介绍了 Martinsson 等人（2008）中算法的新颖分析方法，可以得出尖锐的估计和关于其性能的新见解。通过实验，我们证明了我们预测的紧密性与经验观测的一致性。

    Aug, 2013

  • 算法协同作用的统计视角

    本文在大数据集上提出了算法杠杆效应的采样方法，通过样本采集分布来提高算法的计算效率，并在固定预测因子的线性回归模型中，提出了一种简单有效的框架来评估算法杠杆的统计性能。其结果表明核心的采样方法的统计性能既不会因为采用杠杆采样而主导也不会因采用均匀采样而优于杠杆采样，但其在最坏分析情况下，杠杆采样与均匀采样相比都能提供更好的结果。在理论性能基础上，本文提出并分析了两种新的杠杆算法，并在合成和真实数据集上进行了详细的实证评估。

    Jun, 2013

  • 随机矩阵的非渐近分析入门

    本文是一篇介绍随机矩阵理论基本的非渐近方法和概念的教程，其中涵盖了许多在理论计算机科学、统计学和信号处理等领域的应用，尤其对于统计学中的协方差矩阵估计问题和压缩感知的概率构造测量矩阵的验证有基本应用。

    Nov, 2010

  • 在不相干矩阵上击败随机响应

    该论文提出了一种在矩阵具有低相干性的情况下，基于差分隐私的低秩逼近算法，在准确性、效率方面优于随机响应算法。

    Nov, 2011

  • 线性系统的随机迭代方法

    该研究发展了一种基于随机迭代的方法来解决线性系统问题，并通过变化两个参数来恢复广泛的已知算法，并且在单个定理中证明了误差的指数收敛，并给出了预期迭代的精确公式。

    Jun, 2015