Making the Nystr\"om method highly accurate for low-rank approximations

DOI10.1137/23M1585039arXiv2307.05785MaRDI QIDQ6443409FDOQ6443409

Authors: Jianlin Xia 

Publication date: 11 July 2023

Abstract: The Nystr"om method is a convenient heuristic method to obtain low-rank approximations to kernel matrices in nearly linear complexity. Existing studies typically use the method to approximate positive semidefinite matrices with low or modest accuracies. In this work, we propose a series of heuristic strategies to make the Nystr"om method reach high accuracies for nonsymmetric and/or rectangular matrices. The resulting methods (called high-accuracy Nystr"om methods) treat the Nystr"om method and a skinny rank-revealing factorization as a fast pivoting strategy in a progressive alternating direction refinement process. Two refinement mechanisms are used: alternating the row and column pivoting starting from a small set of randomly chosen columns, and adaptively increasing the number of samples until a desired rank or accuracy is reached. A fast subset update strategy based on the progressive sampling of Schur complements is further proposed to accelerate the refinement process. Efficient randomized accuracy control is also provided. Relevant accuracy and singular value analysis is given to support some of the heuristics. Extensive tests with various kernel functions and data sets show how the methods can quickly reach prespecified high accuracies in practice, sometimes with quality close to SVDs, using only small numbers of progressive sampling steps.

Recommendations

• On the Nyström method for approximating a gram matrix for improved kernel-based learning
• Randomized Low-Rank Approximation for Symmetric Indefinite Matrices
• Revisiting the Nyström method for improved large-scale machine learning
• Asymptotic error bounds for kernel-based Nyström low-rank approximation matrices
• Single-pass Nyström approximation in mixed precision

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cited In (2)

• Single-pass Nyström approximation in mixed precision
• Energy-based sequential sampling for low-rank PSD-matrix approximation

This page was built for publication: Making the Nystr\"om method highly accurate for low-rank approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443409)