相对误差张量低秩逼近
使用 Frequent Directions 算法处理 n x d 矩阵，通过确定性地维护一个 l x d 矩阵 Q 来处理每一行，从而获得一个时间复杂度为 O (d l^2) 的方法，其中 l=k+k/eps 返回最佳秩 k 逼近，同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。
Jul, 2013
在输入转换设置中，我们研究低秩逼近，给出了该问题的条件时间难度结果和运行时下界，同时证明了这些下界是紧致的，并提供了使用基于张量的草图的相对误差逼近算法。
Nov, 2023
本文研究了距离矩阵的低秩近似，证明了在任何底层距离度量下，均可以在亚线性时间内实现加性误差的低秩近似，并发展了一种基于投影 - 成本保持抽样的递归算法。同时，在一般情况下，相对误差逼近是不可能的，即使允许二标准解决方案。此外，如果 P = Q 并且 d 是欧几里得平方距离，则可以在亚线性时间内找到相对误差的二标准解决方案。
Sep, 2018
本文研究了计算有效的低秩核近似的限制，证明计算相对误差 k 秩逼近 K 对于广泛类别的核，包括高斯和多项式核，至少与将输入数据矩阵 A 乘以任意矩阵 C 一样困难，并给出了一些希望：首次证明对于一般的径向基函数核， 如高斯核，存在 $O (nnz (A))$ 的时间近似方法。
Nov, 2017
本文讨论了针对高于三阶的张量的最优低秩逼近定理。我们提出了使用弱解来克服低秩逼近问题的不适定性，并从代数几何的角度将我们的工作与张量的现有研究联系起来。
Jul, 2006
本文提出并研究基于列 / 行数小于原数据矩阵的矩阵近似算法，并给出了两个随机化算法，通过特征值分解将矩阵近似成小的矩阵，并使用名为 “子空间采样” 的新颖采样方法，从而实现相对误差保证下的低维矩阵分解。
Aug, 2007
通过对两个 m 维变量的光滑函数进行采样生成的矩阵的低秩逼近是本文关注的重点。我们否定了先前文献中对一个特定类别的解析函数所提出的论点，即这些矩阵可以独立于 m 具有准确的逐个元素的秩逼近。我们在理论上解释了支持该论点的数值结果，并描述了三个更窄的函数类别，其中 n×n 由函数生成的矩阵可以在与维度 m 无关的情况下以 O (log (n)ε^(-2) polylog (ε^(-1))) 的逐个元素误差逼近。我们还将我们的论点扩展到了由 m 维变量的多线性积生成的张量的低秩张量列逼近。我们在 Transformer 神经网络的注意力低秩逼近的背景下讨论了我们的结果。
Jul, 2024
本文介绍了针对最小二乘回归问题的 CP 和 Tucker 分解模型，以及基于稀疏随机投影的数据降维技术，旨在减小模型参数数量和计算量。作者通过数值模拟得到了实验结果，证实了其理论的有效性。
Sep, 2017