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

Jul, 2013

Relative Errors for Deterministic Low-Rank Matrix Approximations

Mina Ghashami, Jeff M. Phillips

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

Abstract

We consider processing an n x d matrix A in a stream with row-wise updates according to a recent algorithm called frequent directions (Liberty, KDD 2013). This algorithm maintains an l x d matrix Q deterministically, processing each row in O(d l^2) time; the processing time can be decr

frequent directions matrix processing stream processing approximation sparse version

发现论文，激发创造

Frequent Directions：简单和确定性的矩阵草图

Frequent Directions 是一种新的确定性矩阵草图算法，适用于行更新模型。它在空间误差权衡中优于现有的流式算法的示例实现。

Jan, 2015

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

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

Jan, 2016

相对误差张量低秩逼近

本文介绍了如何在规定 Frobenius 范数的情况下对张量进行相对误差的低秩近似，提出了两种算法，并展示了在基于指数时间假设下的时间下限。

Apr, 2017

线性时间的低秩矩阵近似

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

Oct, 2014

简单且确定的矩阵草图

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

Jun, 2012

距离矩阵的亚线性时间低秩逼近

本文研究了距离矩阵的低秩近似，证明了在任何底层距离度量下，均可以在亚线性时间内实现加性误差的低秩近似，并发展了一种基于投影 - 成本保持抽样的递归算法。同时，在一般情况下，相对误差逼近是不可能的，即使允许二标准解决方案。此外，如果 P = Q 并且 d 是欧几里得平方距离，则可以在亚线性时间内找到相对误差的二标准解决方案。

Sep, 2018

单遍逐元素变换低秩逼近

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

Jul, 2021

距离矩阵的最优低秩逼近

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

Jun, 2019

基于学习的低秩逼近

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

Oct, 2019

一种用于低秩近似的快速频率方向算法

本文提出了一种使用随机化算法（稀疏子空间嵌入）以降低计算成本的快速频繁方向算法，它在低秩逼近问题中工作得很好并且利用了频繁方向的自然块结构和稀疏子空间嵌入向每个块发送更多信息，该算法有效且高效，通过在合成和真实数据集上的实验结果以及在网络分析中的应用进行了证明。

May, 2017