Oct, 2014
线性时间的低秩矩阵近似
Low Rank Matrix Approximation in Linear Time
Sariel Har-Peled
TL;DR给定一个矩阵，提出了一个线性时间复杂度算法计算其 k 秩矩阵，达到了乘性近似，误差满足 (1+ϵ) 最小误差。
Abstract
$\newcommand{\MatA}{\mathcal{M}}$ $\newcommand{\eps}{\varepsilon}$
$\newcommand{\NSize}{\mathsf{N}{}}$ $\newcommand{\MatB}{\mathcal{B}}$
$\newcommand{\Fnorm}[1]{\left\| {#1} \right\|_F}$
$\newcommand{\PrcOpt}[2]{\mu_{\mathrm{opt}}\pth{#1, #2}}$
$\newcommand{\pth}[1]{\left(#1\right)}$
Given a
发现论文，激发创造
距离矩阵的亚线性时间低秩逼近
本文研究了距离矩阵的低秩近似，证明了在任何底层距离度量下，均可以在亚线性时间内实现加性误差的低秩近似，并发展了一种基于投影 - 成本保持抽样的递归算法。同时，在一般情况下，相对误差逼近是不可能的，即使允许二标准解决方案。此外，如果 P = Q 并且 d 是欧几里得平方距离，则可以在亚线性时间内找到相对误差的二标准解决方案。
Sep, 2018
确定性低秩矩阵逼近的相对误差
使用 Frequent Directions 算法处理 n x d 矩阵，通过确定性地维护一个 l x d 矩阵 Q 来处理每一行，从而获得一个时间复杂度为 O (d l^2) 的方法，其中 l=k+k/eps 返回最佳秩 k 逼近，同时证明了无法将该算法明显地适应于保留矩阵的原始行的稀疏版本。
Jul, 2013
低秩二进制矩阵逼近问题的逼近方案
我们为一种关于二进制向量聚类的约束性问题提供了一种随机线性时间逼近方案，并且通过解决这个问题，我们获得了在二进制向量聚类和二进制矩阵低秩逼近方面的第一个线性时间逼近方案。
Jul, 2018
入项变换矩阵乘积的低秩逼近难度
在输入转换设置中，我们研究低秩逼近，给出了该问题的条件时间难度结果和运行时下界，同时证明了这些下界是紧致的，并提供了使用基于张量的草图的相对误差逼近算法。
Nov, 2023
矩阵隐式函数的分布式低秩逼近
本研究探讨了分布式低秩逼近，其中需要只隐含地跨不同服务器表示逼近的矩阵。研究表明，在宽泛的函数 f 类别中，可以高效计算一个低秩映射矩阵 P，以满足通信成本为 d∙(sk/ε)^O (1)，且算法成功概率高，并可将其用于计算入门型 softmax、Gaussian 核扩展以及 robust 低秩逼近等问题。
Jan, 2016