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

Nov, 2023

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

Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products

Tamas Sarlos, Xingyou Song, David Woodruff, Qiuyi, Zhang

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

Abstract

Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting where we want to find a good rank $k$ approximation to $f(U \cdot V)$, where $U, V^\top \in \mathbb{R}^{n \times r}$ are given, $r = O(\log(n))$, and $f(x)$

low rank approximation transformed setting conditional time hardness lower bounds tensor-based sketching

发现论文，激发创造

单遍逐元素变换低秩逼近

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

Jul, 2021

Krylov 方法在低秩近似中（几乎）是最优的

本文通过矩阵向量乘积模型和多种 Schatten norm 下的 rank-1 低秩逼近问题，证明了 Krylov methods 几乎达到了谱（p=∞）、Frobenius（p=2）和核（p=1）LRA 的信息论最优矩阵向量乘积数量的上界，并给出了一些改进的上界。

Apr, 2023

稳定秩下的最优近似矩阵乘积

用子空间嵌入保证黑盒方式证明，通过降维映射可实现近似矩阵乘法的谱范数保障，其中降维映射具有 O（~r/ε^2）行，且优于以前的工作 [MZ11，KVZ14]，对于任何混淆的降维映射也是最佳的。

Jul, 2015

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

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

Jan, 2016

核矩阵低秩逼近中是否存在稀疏化输入时间？

本文研究了计算有效的低秩核近似的限制，证明计算相对误差 k 秩逼近 K 对于广泛类别的核，包括高斯和多项式核，至少与将输入数据矩阵 A 乘以任意矩阵 C 一样困难，并给出了一些希望：首次证明对于一般的径向基函数核，如高斯核，存在 $O (nnz (A))$ 的时间近似方法。

Nov, 2017

相对误差张量低秩逼近

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

Apr, 2017

线性时间的低秩矩阵近似

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

Oct, 2014

矩阵近似乘法及其在线性嵌入方面的应用

该论文研究了计算两个实矩阵乘积的近似算法，提出了核秩的概念，并应用于线性低维嵌入中，使得任何核秩有界的欧几里得点集能够在独立于输入维度的投影空间上实现加性误差保证。

Mar, 2014

输入稀疏时间内的低秩逼近和回归

本文提出了一种新的稀疏嵌入矩阵，通过使用这种矩阵，可以实现超约束最小二乘回归、低秩逼近、所有梁角得分的近似和 $l_p$- 回归问题的 $(1+\varepsilon)$- 近似，其时间复杂度的主导项是 $O (\nnz (A))$ 或 $O (\nnz (A)\log n)$。

Jul, 2012

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

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

Jul, 2013