Block Basis Factorization for Scalable Kernel Matrix Evaluation
This addresses scalability issues for kernel methods in machine learning, particularly for datasets with wide intra-class variability, representing an incremental improvement over existing low-rank approximation techniques.
The paper tackles the quadratic complexity of kernel matrices in machine learning by proposing Block Basis Factorization (BBF), a structured low-rank approximation method that achieves linear memory and computational costs for radial basis function kernels, demonstrating stability and superiority over state-of-the-art algorithms in empirical results.
Kernel methods are widespread in machine learning; however, they are limited by the quadratic complexity of the construction, application, and storage of kernel matrices. Low-rank matrix approximation algorithms are widely used to address this problem and reduce the arithmetic and storage cost. However, we observed that for some datasets with wide intra-class variability, the optimal kernel parameter for smaller classes yields a matrix that is less well approximated by low-rank methods. In this paper, we propose an efficient structured low-rank approximation method -- the Block Basis Factorization (BBF) -- and its fast construction algorithm to approximate radial basis function (RBF) kernel matrices. Our approach has linear memory cost and floating-point operations for many machine learning kernels. BBF works for a wide range of kernel bandwidth parameters and extends the domain of applicability of low-rank approximation methods significantly. Our empirical results demonstrate the stability and superiority over the state-of-art kernel approximation algorithms.