An Adaptive Factorized Nyström Preconditioner for Regularized Kernel Matrices

2023/04/11 by Shifan Zhao, Tianshi Xu, Zhao, Shifan +6 · 4 citations
Chemistry · Computer Science · Physics and Astronomy · #Advanced NMR Techniques and Applications #Electromagnetic Scattering and Analysis #FOS: Mathematics #Matrix Theory and Algorithms #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.2304.05460

openalex publication_date 2023/04/11 · openalex created_date 2023/04/15 · openalex updated_date 2026/07/28

Abstract

The spectrum of a kernel matrix significantly depends on the parameter values of the kernel function used to define the kernel matrix. This makes it challenging to design a preconditioner for a regularized kernel matrix that is robust across different parameter values. This paper proposes the Adaptive Factorized Nyström (AFN) preconditioner. The preconditioner is designed for the case where the rank k of the Nyström approximation is large, i.e., for kernel function parameters that lead to kernel matrices with eigenvalues that decay slowly. AFN deliberately chooses a well-conditioned submatrix to solve with and corrects a Nyström approximation with a factorized sparse approximate matrix inverse. This makes AFN efficient for kernel matrices with large numerical ranks. AFN also adaptively chooses the size of this submatrix to balance accuracy and cost.

Cited by

• Accelerated decomposition of bistochastic kernel matrices by low rank approximation
• Preconditioned Truncated Single-Sample Estimators for Scalable Stochastic Optimization
• Neural Approximate Inverse Preconditioners
• An efficient algorithm for kernel quantile regression

Related

• On the Nystrom Approximation for Preconditioning in Kernel Machines
• Randomized Nyström Preconditioning
• Making the Nyström method highly accurate for low-rank approximations
• Boosting Nyström Method
• Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method