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.
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:
- Clustering: The dataset is partitioned into $k$ clusters, and the kernel matrix is permuted to reveal a block structure.
- 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.
- 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.
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