TITLE: Fast deterministic approximation of symmetric indefinite kernel matrices with high dimensional datasets 

ABSTRACT: Kernel methods are used frequently in various applications of machine
learning. For large-scale high dimensional applications, the success of kernel
methods hinges on the ability to operate certain large dense kernel matrix K.
An enormous amount of literature has been devoted to the study of symmetric
positive semi-definite (SPSD) kernels, where Nystrom methods compute a low-rank
approximation to the kernel matrix via choosing landmark points. In this paper,
we study the Nystrom method for approximating both symmetric indefinite kernel
matrices as well SPSD ones. We first develop a theoretical framework for
general symmetric kernel matrices, which provides a theoretical guidance for
the selection of landmark points. We then leverage discrepancy theory to
propose the anchor net method for computing accurate Nystrom approximations
with optimal complexity. The anchor net method operates entirely on the dataset
without requiring the access to $K$ or its matrix-vector product. Results on
various types of kernels (both indefinite and SPSD ones) and machine learning
datasets demonstrate that the new method achieves better accuracy and stability
with lower computational cost compared to the state-of-the-art Nystrom methods.
Kernel methods are used frequently in various applications of machine
learning. For large-scale high dimensional applications, the success of kernel
methods hinges on the ability to operate certain large dense kernel matrix K.
An enormous amount of literature has been devoted to the study of symmetric
positive semi-definite (SPSD) kernels, where Nystrom methods compute a low-rank
approximation to the kernel matrix via choosing landmark points. In this paper,
we study the Nystrom method for approximating both symmetric indefinite kernel
matrices as well SPSD ones. We first develop a theoretical framework for
general symmetric kernel matrices, which provides a theoretical guidance for
the selection of landmark points. We then leverage discrepancy theory to
propose the anchor net method for computing accurate Nystrom approximations
with optimal complexity. The anchor net method operates entirely on the dataset
without requiring the access to $K$ or its matrix-vector product. Results on
various types of kernels (both indefinite and SPSD ones) and machine learning
datasets demonstrate that the new method achieves better accuracy and stability
with lower computational cost compared to the state-of-the-art Nystrom methods.
Fast deterministic approximation of symmetric indefinite kernel matrices with high dimensional datasets
http://arxiv.org/abs/2102.05215v2