用核密度估计加速核矩阵的线性代数运算，显著降低计算复杂度。
Even Faster Kernel Matrix Linear Algebra via Density Estimation
- 通过核密度估计查询替代直接读取矩阵元素，降低对数据量n的依赖。
- 在误差控制在1+ε时，多项式依赖ε和n的指数均优于已有最优算法。
- 适用于大规模高维数据的核矩阵计算，尤其适合需要高效近似结果的场景。
本文研究利用核密度估计（KDE）进行核矩阵相关线性代数任务的计算，包括矩阵-向量乘积、矩阵-矩阵乘积、谱范数及所有元素之和的计算，目标是在(1+ε)相对误差范围内实现加速。新算法的运行时间依赖于维度d、点数n和目标误差ε。关键优势在于：通过KDE查询访问核矩阵，相较于逐个读取元素，对n的依赖程度大幅降低。相比现有最优算法（Backurs, Indyk, Musco, Wagner '21），本方法显著降低了ε的多项式依赖，并在计算核矩阵总和时也减少了对n的依赖。同时，论文提供了若干下界分析，揭示了相关问题的条件性二次时间难解性，并暗示了基于KDE方法的理论极限。
原文摘要 · Abstract (English)
This paper studies the use of kernel density estimation (KDE) for linear algebraic tasks involving the kernel matrix of a collection of $n$ data points in $\mathbb R^d$. In particular, we improve upon existing algorithms for computing the following up to $(1+\varepsilon)$ relative error: matrix-vector products, matrix-matrix products, the spectral norm, and sum of all entries. The runtimes of our algorithms depend on the dimension $d$, the number of points $n$, and the target error $\varepsilon$. Importantly, the dependence on $n$ in each case is far lower when accessing the kernel matrix through KDE queries as opposed to reading individual entries. Our improvements over existing best algorithms (particularly those of Backurs, Indyk, Musco, and Wagner '21) for these tasks reduce the polynomial dependence on $\varepsilon$, and additionally decreases the dependence on $n$ in the case of computing the sum of all entries of the kernel matrix. We complement our upper bounds with several lower bounds for related problems, which provide (conditional) quadratic time hardness results and additionally hint at the limits of KDE based approaches for the problems we study.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。