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

Sep, 2018

Sublinear Time Low-Rank Approximation of Distance Matrices

Ainesh Bakshi, David P. Woodruff

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

Abstract

Let $\mathbf{P}=\{ p_1, p_2, \ldots p_n \}$ and $\mathbf{Q} = \{ q_1, q_2 \ldots q_m \}$ be two point sets in an arbitrary metric space. Let $\mathbf{A}$ represent the $m\times n$ pairwise distance matrix with $\mathbf{A}_{i,j} = d(p_i, q_j)$. Such distance matrices are commonly comput

distance matrices low-rank approximation sublinear time additive error recursive algorithm

发现论文，激发创造

距离矩阵的最优低秩逼近

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

Jun, 2019

线性时间的低秩矩阵近似

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

Oct, 2014

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

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

Jul, 2013

相对误差张量低秩逼近

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

Apr, 2017

量子启发的次线性经典算法求解低秩线性系统

本文介绍了解决低秩线性系统的古典次线性时间算法。我们的算法受 HHL 量子算法解决线性系统和 Tang 去量子化推荐系统量子算法的最新突破的启发。我们提出了两种算法：提供 $A^{-1} b$ 样本的 “采样” 算法和输出 $A^{-1} b$ 条目的估计值的 “查询” 算法。我们考虑的算法的时间复杂度是次线性时间的。

Nov, 2018

文本相似度矩阵的次线性时间近似

本篇研究文章探讨通过推荐算法，计算相似矩阵的问题，介绍了基于 Nyström 方法的一种新的推荐算法，此算法可以以亚线性时间的复杂度对任何相似矩阵进行求解，在 NLP 的不同应用场景中展示出高精确度的表现。

Dec, 2021

输入稀疏时间内低失真子空间嵌入及其在鲁棒线性回归中的应用

提出了一种低失真度嵌入方法，在线性代数问题中得到广泛应用，支持 l_2 误差损失最小回归以及 (1±ε) 失真度的 l_p 子空间嵌入，包括一种基于输入稀疏性的 l_p 子空间采样过程。

Oct, 2012

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

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

Nov, 2023

高维低秩矩阵的估计

本文研究用惯性系数约束和 Frobenius 范数限制下的惩罚最小二乘估计的 Schatten-p 准范惩罚项估计法，能够有效地在高维数据下进行矩阵估计。

Dec, 2009

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

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

Jan, 2016