Structured Block Basis Factorization for Scalable Kernel Matrix Evaluation

Ruoxi Wang, Yingzhou Li, Michael W. Mahoney, Eric DarvearXiv 2015 · arXiv

Introduction

Kernel methods, such as Support Vector Machines and Kernel Ridge Regression, are fundamental tools in machine learning for capturing non-linear relationships. However, they face a significant scalability hurdle: the kernel matrix, which stores similarities between all pairs of $n$ data points, requires $O(n^2)$ memory and $O(n^3)$ time for linear system solutions. While low-rank approximations like the Nyström method are common remedies, they often fail in high-accuracy regimes where small kernel bandwidths are required. This paper introduces Block Basis Factorization (BBF), a structured matrix approximation that maintains linear complexity even when traditional low-rank methods struggle.

The Bandwidth-Rank Tradeoff

A critical challenge in kernel approximation is the relationship between the kernel bandwidth ($h$) and the matrix rank. In many real-world applications—particularly those involving imbalanced classes or non-smooth decision boundaries—a small $h$ is necessary for high accuracy. As $h$ decreases, the kernel matrix becomes increasingly high-rank and eventually diagonally dominant.

Singular value decay for different kernel bandwidths. For small bandwidths (e.g., $h=2^{-4}$), the singular values decay very slowly, making global low-rank approximations ineffective.

Traditional methods like SVD or Nyström rely on a "large spectrum gap" to compress the matrix. When the singular values decay slowly (as seen in the figure above for small $h$), these methods either lose significant information or revert to quadratic complexity to maintain accuracy.

Block Basis Factorization (BBF)

BBF addresses this by bridging the gap between low-rank and full-rank representations. Instead of a single global basis, BBF exploits the fact that local interactions often have lower numerical rank than the global matrix. The method follows a three-stage pipeline:

  1. Clustering: The dataset is partitioned into $k$ clusters, and the kernel matrix is permuted to reveal a block structure.
  2. Basis Construction: A column basis is computed for each "row-submatrix" (interactions between one cluster and the whole dataset). BBF uses a randomized sampling strategy—leveraging pivoted QR/LQ factorizations—to ensure stability and efficiency without the cubic cost of standard SVD.
  3. Inner Matrix Construction: The blocks are compressed using these local bases, resulting in a structured approximation $M \approx \tilde{U}\tilde{C}\tilde{U}^\top$, where $\tilde{U}$ is block-diagonal.

This approach is specifically tailored for high-dimensional, non-grid-like machine learning data, offering a more robust alternative to existing hierarchical matrix methods.

Empirical Results

The authors evaluated BBF across diverse benchmarks, including UCI datasets and large-scale classification tasks like Forest Covertype (580k+ instances). A key finding is BBF's consistent performance across varying bandwidths.

F1 scores on test sets for classification tasks (EMG, CTG, Otto, Gesture) across different kernel bandwidths (h). BBF maintains high performance even as h varies.

Key Insights:

  • Linear Scaling: Factorization time scales linearly ($O(n)$), enabling the processing of hundreds of thousands of data points.
  • Superior Accuracy at Small $h$: As the matrix rank increases (small $h$), the gap between BBF and Nyström-based methods widens, with BBF maintaining much lower relative error for the same memory budget.
  • Downstream Performance: In Kernel Ridge Regression, BBF achieved lower RMSE than competing methods on datasets like Cpusmall and Mushroom.

Conclusion

Block Basis Factorization provides a scalable and robust framework for kernel matrix approximation. By focusing on local block structures and employing stable randomized sampling, it overcomes the limitations of global low-rank methods in high-rank regimes. Future work may explore relaxing orthogonality constraints or explicitly integrating regularization parameters into the compression step to further enhance efficiency.

Summary updated

Abstract

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.
BibTeX
@misc{wang2015structured,
  author = {Ruoxi Wang and Yingzhou Li and Michael W. Mahoney and Eric Darve},
  title = {{Structured Block Basis Factorization for Scalable Kernel Matrix Evaluation}},
  year = {2015},
  eprint = {1505.00398},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1505.00398},
}
Figure