单遍逐元素变换低秩逼近

ICMLJul, 2021

Single Pass Entrywise-Transformed Low Rank Approximation

Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David P. Woodruff

TL;DR本文提出了一种用于矩阵分解且只需一次通过矩阵的内部即可完成的内存高效算法，并且在同样类似于 Liang et al. 所研究的函数 $f$ 的条件下，误差显著减小，还提出了应用于回归问题的算法，并通过实验证明了其结果的正确性。

Abstract

In applications such as natural language processing or computer vision, one is given a large $n \times d$ matrix $A = (a_{i,j})$ and would like to compute a matrix decomposition, e.g., a low rank approximation, o

matrix decomposition low rank approximation likelihood function memory-efficient algorithm single-pass algorithm

发现论文，激发创造

入项变换矩阵乘积的低秩逼近难度

在输入转换设置中，我们研究低秩逼近，给出了该问题的条件时间难度结果和运行时下界，同时证明了这些下界是紧致的，并提供了使用基于张量的草图的相对误差逼近算法。

Nov, 2023

矩阵隐式函数的分布式低秩逼近

本研究探讨了分布式低秩逼近，其中需要只隐含地跨不同服务器表示逼近的矩阵。研究表明，在宽泛的函数 f 类别中，可以高效计算一个低秩映射矩阵 P，以满足通信成本为 d∙(sk/ε)^O (1)，且算法成功概率高，并可将其用于计算入门型 softmax、Gaussian 核扩展以及 robust 低秩逼近等问题。

Jan, 2016

基于学习的低秩逼近

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

Oct, 2019

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

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

Mar, 2015

确定性低秩矩阵逼近的相对误差

使用 Frequent Directions 算法处理 n x d 矩阵，通过确定性地维护一个 l x d 矩阵 Q 来处理每一行，从而获得一个时间复杂度为 O (d l^2) 的方法，其中 l=k+k/eps 返回最佳秩 k 逼近，同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。

Jul, 2013

距离矩阵的最优低秩逼近

本文研究了距离矩阵的低秩近似算法及其样本复杂度，在实验中得到了验证。

Jun, 2019

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

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

Oct, 2023

线性时间的低秩矩阵近似

给定一个矩阵，提出了一个线性时间复杂度算法计算其 k 秩矩阵，达到了乘性近似，误差满足 (1+ϵ) 最小误差。

Oct, 2014

矩阵低秩逼近的文献综述

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

Jun, 2016

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

本文提出了一种新的随机算法，该算法采用特别偏向采样的方法，使误差最小化，可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近，并具有 better dependence on error ε，是一种高度可并行化的优化方法。此外，本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。

Oct, 2014