揭示了选主元的低秩逼近算法与最远点采样的几何等价性。
The Geometry of the Pivot: A Note on Lazy Pivoted Cholesky and Farthest Point Sampling
- 用核度量下的最远点采样解释选主元步骤
- 证明了乔列斯基分解隐含正交化过程
- 适合想理解算法几何本质的研究者
大规模核矩阵的低秩近似在机器学习中广泛应用，尤其对扩展高斯过程至海量数据集至关重要。选主元乔列斯基分解是实现该目标的标准工具，具有计算高效、贪心选择的特点。尽管其代数性质在数值线性代数中已有详尽研究，但在核方法中的几何直观仍不清晰。本文阐明了该算法在再生核希尔伯特空间（RKHS）中的几何解释：选主元步骤在数学上等价于使用核度量的最远点采样（FPS），而乔列斯基因子的构建则对应隐式格拉姆-施密特正交化。我们提供了简洁推导和最小化Python实现，弥合理论与实践之间的鸿沟。
原文摘要 · Abstract (English)
Low-rank approximations of large kernel matrices are ubiquitous in machine learning, particularly for scaling Gaussian Processes to massive datasets. The Pivoted Cholesky decomposition is a standard tool for this task, offering a computationally efficient, greedy low-rank approximation. While its algebraic properties are well-documented in numerical linear algebra, its geometric intuition within the context of kernel methods often remains obscure. In this note, we elucidate the geometric interpretation of the algorithm within the Reproducing Kernel Hilbert Space (RKHS). We demonstrate that the pivotal selection step is mathematically equivalent to Farthest Point Sampling (FPS) using the kernel metric, and that the Cholesky factor construction is an implicit Gram-Schmidt orthogonalization. We provide a concise derivation and a minimalist Python implementation to bridge the gap between theory and practice.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。