论文标题
随机旋转的Cholesky：内核矩阵的实用近似，很少输入评估
Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations
论文作者
论文摘要
随机旋转的部分Cholesky算法（RPCholesky）计算N X N阳性 - 毫秒（PSD）矩阵的分解级别K-K近似。 rpcholesky仅需要（k + 1）n输入评估和o（k^2 n）其他算术操作，并且只需几行代码就可以实现。该方法对于近似内核矩阵特别有用。 本文对这种基本算法的经验和理论行为进行了彻底的新研究。对于科学机器学习中出现的矩阵近似问题，实验表明rpcholesky匹配或击败了替代算法的性能。此外，RPCholesky证明是返回几乎最佳的低级近似值。 Rpcholesky的简单性，有效性和鲁棒性强烈支持其在科学计算和机器学习应用中的使用。
The randomly pivoted partial Cholesky algorithm (RPCholesky) computes a factorized rank-k approximation of an N x N positive-semidefinite (psd) matrix. RPCholesky requires only (k + 1) N entry evaluations and O(k^2 N) additional arithmetic operations, and it can be implemented with just a few lines of code. The method is particularly useful for approximating a kernel matrix. This paper offers a thorough new investigation of the empirical and theoretical behavior of this fundamental algorithm. For matrix approximation problems that arise in scientific machine learning, experiments show that RPCholesky matches or beats the performance of alternative algorithms. Moreover, RPCholesky provably returns low-rank approximations that are nearly optimal. The simplicity, effectiveness, and robustness of RPCholesky strongly support its use in scientific computing and machine learning applications.
