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

NIPSNov, 2017

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

Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?

Cameron Musco, David P. Woodruff

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

Abstract

low-rank approximation is a common tool used to accelerate kernel methods: the $n \times n$ kernel matrix $K$ is approximated via a rank-$k$ matrix $\tilde K$ which can be stored in much less space and processed

low-rank approximation kernel methods gaussian kernel matrix multiplication radial basis function

发现论文，激发创造

低秩核矩阵近似的尖锐分析

本文研究了在正定核框架下的监督学习问题，提出了基于随机矩阵列采样的核矩阵低秩近似方法，此方法可以在 sub-quadratic 的时间复杂度内有效解决核矩阵计算问题，同时保持预测性能不变。

Aug, 2012

关于核学习的复杂性

本文主要研究降低核矩阵计算成本的方法，并针对观测的核矩阵条目数或近似核矩阵的秩，确定这些方法在错误达到下限的条件。研究结果表明损失函数，正则化参数，期望预测器的范数和核矩阵秩等参数与问题难度有关，同时提出了更高效的核学习可能的情况。

Nov, 2014

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

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

Nov, 2023

通过 Ridge Leverage Score 抽样进行输入稀疏时间低秩逼近

该研究提出了一种新的基于采样策略的算法来计算矩阵的最优低秩逼近，相较于之前基于随机投影的算法，该方法可适用于稀疏结构等场景，并在核矩阵逼近算法方面表现最优。

Nov, 2015

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

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

Jul, 2012

距离矩阵的最优低秩逼近

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

Jun, 2019

相对误差张量低秩逼近

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

Apr, 2017

当大数据实际上是低秩的，或者是某个函数生成的矩阵的逐个近似

通过对两个 m 维变量的光滑函数进行采样生成的矩阵的低秩逼近是本文关注的重点。我们否定了先前文献中对一个特定类别的解析函数所提出的论点，即这些矩阵可以独立于 m 具有准确的逐个元素的秩逼近。我们在理论上解释了支持该论点的数值结果，并描述了三个更窄的函数类别，其中 n×n 由函数生成的矩阵可以在与维度 m 无关的情况下以 O (log (n)ε^(-2) polylog (ε^(-1))) 的逐个元素误差逼近。我们还将我们的论点扩展到了由 m 维变量的多线性积生成的张量的低秩张量列逼近。我们在 Transformer 神经网络的注意力低秩逼近的背景下讨论了我们的结果。

Jul, 2024

线性时间的低秩矩阵近似

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

Oct, 2014

核基学习中的稀疏逼近方法的改进收敛速率

本文针对核方法的高计算成本问题，提出了 Nyström 方法和稀疏变分高斯过程逼近方法的置信区间，从而改进了模型在回归和优化问题中的性能界限。

Feb, 2022