Oct, 2014

通过采样杠杆元素实现更紧凑的低秩近似

PDF
TL;DR本文提出了一种新的随机算法，该算法采用特别偏向采样的方法，使误差最小化，可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近，并具有 better dependence on error ε，是一种高度可并行化的优化方法。此外，本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。
randomized algorithmlow-rank approximationspectral normweighted alternating minimizationdistributed pca
发现论文，激发创造
  • 通过 Ridge Leverage Score 抽样进行输入稀疏时间低秩逼近

    该研究提出了一种新的基于采样策略的算法来计算矩阵的最优低秩逼近，相较于之前基于随机投影的算法，该方法可适用于稀疏结构等场景，并在核矩阵逼近算法方面表现最优。

    Nov, 2015

  • 基于杠杆的低秩张量分解实用采样

    本文研究稀疏张量的低秩正交多项式分解，提出了使用杠杆得分来选择子集行数的草图方法，并提供了一个实际的解决方案，以提高高杠杆得分行的采样和理论界限。

    Jun, 2020

  • 基于学习的低秩逼近

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

    Oct, 2019

  • 通过随机低秩和低精度因式分解实现矩阵压缩

    我们提出一种算法，利用矩阵的低秩结构来获得任意矩阵的低秩分解，通过向量量化和压缩技术实现了压缩比例和逼近精度之间的折衷。

    Oct, 2023

  • 可证明地补全任意低秩矩阵

    本文提出了一种特定偏向分布的采样方式，利用该采样方式可以从少量采样的数据中精确恢复任何秩为 r 的 nxn 的矩阵（无需满足之前已有的结构限制要求），而且在没有先验信息下本文建立了三种使用该采样方式的方法，其中还包括分析了针对非均匀采样情形中，加权核范数 / 迹范数惩罚的优点。

    Jun, 2013

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

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

    Aug, 2013

  • 高效交替最小化与带权低秩近似的应用

    本研究提供了一种有效和稳健的交替最小化框架来解决线性代数和机器学习中的一些问题，关注于都市中加权矩阵的低秩矩阵近似问题，并将运行时间从之前的 n^2k^2 降至 n^2k。

    Jun, 2023

  • 可证明的确定性杠杆得分采样

    本研究发现借助确定性列采样算法可以优化矩阵逼近的效果，但要求杠杆得分具有适度陡峭的幂律衰减特性。我们提供了实证证据支持这一假设，并通过实际测试表明，该算法的性能已达到或超过了现有技术水平。

    Apr, 2014

  • 一种随机分块算法，用于高效计算矩阵排名披露因子分解

    本文介绍了一种计算部分秩相因分解的方法，该方法采用随机取样避免了列交换，从而使得计算速度得到了大幅提升，并且在各种矩阵上都表现出色，特别是在 GPU 结构上表现尤为突出。

    Mar, 2015

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

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

    Sep, 2009