Aug, 2016

低秩矩阵近似的实用素描算法

PDF
TL;DR该论文介绍了构建输入矩阵的低秩近似的算法套件，这些算法使用矩阵的随机线性图像（称为草图）。这些方法可以保留输入矩阵的结构特性，如半正定性，并且可以生成具有用户指定秩的近似值。此外，每种方法都伴随着一个信息性误差界，允许用户预先选择参数以实现所需的近似质量。这些论断受真实和合成数据的数字实验支持。
发现论文，激发创造
  • 草图作为数值线性代数工具

    本文综述了数值线性代数算法领域的最新进展，着重介绍了利用线性草图技术来进行矩阵压缩的方法，以加速解决原问题。文章讨论了最小二乘、鲁棒回归、低秩逼近和图稀疏化的问题，并优化了这些问题的不同变体。最后，文章探讨了草图方法的局限性。

    Nov, 2014

  • 随机投影的精确表达式：低秩逼近与随机牛顿

    利用随机矩阵的谱分析最新进展，我们开发了一种新的技术，提供了随机投影矩阵的期望值的确切表达式，这些表达式可以用来表征多种常见的机器学习任务中的降维性能，包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法，包括高斯和 Rademacher 草图，结果表明，我们推导出的表达式反映了这些草图方法的实际性能，甚至体现了较低阶效应和恒定因子。

    Jun, 2020

  • 基于学习的低秩逼近

    本文介绍了一种基于学习的算法来解决低秩分解问题，并且通过学习用稀疏矩阵来代替随机矩阵可以减小近似误差。同时，给出了针对稀疏矩阵学习问题的泛化界及近似算法。

    Oct, 2019

  • 矩阵低秩逼近的文献综述

    本文介绍了低秩逼近技术，并给出了众多相关技术的广泛参考资料。在此基础上，简要评述了基于奇异值分解、QR 分解、随机算法以及交叉 / 骨架逼近等各种低秩逼近技术的应用和优缺点。

    Jun, 2016

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

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

    Aug, 2013

  • 简单且确定的矩阵草图

    该研究论文介绍了一种基于矩阵素描的流式算法，可用于近似项目频率，具有确定性、易于实现和基本易于证明的优点，并在计算上具有竞争力，比目前广泛使用的方法能够得到更为精确的矩阵素描。

    Jun, 2012

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

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

    Sep, 2009

  • 基于流数据的半正定矩阵固定秩近似

    本文提出了一种新的算法，利用 Nystrom 逼近和截断秩的新机制实现了从草图中进行固定秩正半定逼近，并证明了在 Schatten 1 - 范数中可以实现任何预设的相对误差，能够利用输入矩阵的谱衰减，并在计算机实验中表现出比固定秩正半定矩阵逼近的替代技术更好的性能。

    Jun, 2017

  • 低秩核矩阵近似的尖锐分析

    本文研究了在正定核框架下的监督学习问题，提出了基于随机矩阵列采样的核矩阵低秩近似方法，此方法可以在 sub-quadratic 的时间复杂度内有效解决核矩阵计算问题，同时保持预测性能不变。

    Aug, 2012

  • 基于三次草图的稀疏低秩张量估计

    该研究提出一种基于稀疏张量分解和阈值梯度下降的二阶段非凸实现框架，可从立方挖掘中进行稀疏和低秩张量估计，在无噪音情况下确保准确恢复，在带噪音情况下高概率稳定恢复，并导出了新的高阶浓度不等式对高阶交互追求在高维线性回归中的潜在应用进行了张量表述。

    Jan, 2018