Abstract
Symmetric positive semidefinite (SPSD) matrix approximation is an important problem with applications in kernel methods. However, existing SPSD matrix approximation methods such as the Nyström method only have weak error bounds. In this paper, we conduct in-depth studies of an SPSD matrix approximation model and establish strong relative-error bounds. We call it the prototype model for it has more efficient and effective extensions, and some of its extensions have high scalability. Though the prototype model itself is not suitable for large-scale data, it is still useful to study its properties, on which the analysis of its extensions relies. This paper offers novel theoretical analysis, efficient algorithms, and a highly accurate extension. First, we establish a lower error bound for the prototype model and improve the error bound of an existing column selection algorithm to match the lower bound. In this way, we obtain the first optimal column selection algorithm for the prototype model. We also prove that the prototype model is exact under certain conditions. Second, we develop a simple column selection algorithm with a provable error bound. Third, we propose a so-called spectral shifting model to make the approximation more accurate when the eigenvalues of the matrix decay slowly, and the improvement is theoretically quantified. The spectral shifting method can also be applied to improve other SPSD matrix approximation models.
Introduction
Many fundamental machine learning algorithms, including Support Vector Machines (SVMs) and Gaussian Processes (GPs), rely on kernel matrices. For a dataset with $n$ points, the corresponding kernel matrix is $n \times n$. As $n$ grows into the millions, the $O(n^2)$ storage and $O(n^3)$ computational costs for matrix inversion become prohibitive. To mitigate this, researchers frequently employ low-rank approximations, most notably the Nyström method, which uses a subset of columns to represent the full matrix.
However, the standard Nyström method often suffers from "weak" error bounds. This research provides a rigorous overhaul of Symmetric Positive Semidefinite (SPSD) matrix approximation by focusing on the "prototype model" (also known as the modified Nyström method). The authors establish the first optimal column selection algorithm for this model and introduce Spectral Shifting (SS), a technique designed to maintain accuracy even when a matrix’s eigenvalues decay slowly.
Methodology
The Prototype Model and Optimal Sampling
Unlike the standard Nyström method, which uses a specific intersection matrix, the prototype model seeks the optimal intersection matrix $U$ to minimize the Frobenius norm error $||K - CUC^T||_F$. To achieve high-quality approximations, the authors propose a three-stage Uniform+Adaptive² Sampling algorithm:
- Uniform Sampling: A rough initial sketch is created by sampling columns uniformly.
- Adaptive Sampling (Rounds 2 & 3): New columns are selected based on the residual error of the current sketch, ensuring that the most informative parts of the matrix are captured.
Spectral Shifting (SS)
Traditional low-rank approximations assume that the "tail" of the eigenvalue spectrum is negligible. In practice, many datasets exhibit a "fat tail" where small eigenvalues collectively contain significant energy. The Spectral Shifting model approximates the matrix as $K \approx CUC^T + \delta I$. By incorporating this diagonal shift $\delta I$, the model accounts for the discarded tail energy, leading to significantly higher fidelity in noisy or high-dimensional settings.
Complexity and Theoretical Comparison
The paper provides a comprehensive comparison of the proposed models against the standard Nyström method. As shown in the table below, the prototype model and its "Faster" variant achieve $(1+\epsilon)$ relative-error bounds, which are significantly stronger than the "weak" bounds associated with standard Nyström.
Experimental Results
The methods were evaluated across diverse benchmarks, including kernel approximation (MNIST, Letters) and Gaussian Process Regression (Plant, Wine, Housing).
- Accuracy: In kernel PCA experiments, the prototype model with adaptive sampling achieved misalignment errors often an order of magnitude lower than standard Nyström.
- The Impact of Spectral Shifting: On datasets with slow eigenvalue decay, the SS model reduced approximation error by nearly 50% compared to non-shifted models. In GPR tasks, the SS model consistently yielded the lowest Mean Squared Error (MSE) while maintaining the same memory footprint as its competitors.
- Scalability: To demonstrate real-world utility, the authors applied a hybrid "SS+MEKA" method to the
covtypedataset (over 580,000 instances), proving that these theoretical advancements scale to massive datasets.
Discussion and Limitations
While this work establishes optimal bounds, some challenges remain. The current optimal algorithms require at least one full pass over the kernel matrix to calculate adaptive sampling probabilities, making truly sub-linear $O(n)$ algorithms with these strong bounds an open area for research. Additionally, while the "Faster Spectral Shifting" model shows empirical promise, its full theoretical analysis remains a subject for future study. Despite these limitations, the introduction of Spectral Shifting and the proof of optimality for the prototype model represent significant steps forward in scaling kernel-based machine learning.
Summary updated