Abstract
The Nystrom method is an efficient technique to generate low-rank matrix approximations and is used in several large-scale learning applications. A key aspect of this method is the distribution according to which columns are sampled from the original matrix. In this work, we present an analysis of different sampling techniques for the Nystrom method. Our analysis includes both empirical and theoretical components. We first present novel experiments with several real world datasets, comparing the performance of the Nystrom method when used with uniform versus non-uniform sampling distributions. Our results suggest that uniform sampling without replacement, in addition to being more efficient both in time and space, produces more effective approximations. This motivates the theoretical part of our analysis which gives the first performance bounds for the Nystrom method precisely when used with uniform sampling without replacement.
Introduction
In large-scale machine learning, kernel matrices representing similarities between data points are often too massive to store or process directly. The Nyström method addresses this by constructing a low-rank approximation from a small subset of columns. While practitioners typically favor uniform sampling for its computational efficiency, theoretical work has historically suggested that non-uniform sampling—weighting columns by importance or norm—is necessary for rigorous accuracy guarantees. This paper bridges the gap between practice and theory, demonstrating that uniform sampling without replacement is not only faster but often more accurate.
Methodology and Datasets
The study evaluates three primary sampling strategies:
- Uniform Sampling: Every column has an equal chance of being selected.
- Diagonal Sampling: Columns are weighted by their diagonal elements ($G_{ii}$).
- Column-Norm Sampling: Columns are weighted by their $l_2$ norm.
These strategies were tested across five diverse datasets: face images (PIE-2.7K, PIE-7K), handwritten digits (MNIST), protein data (ESS), and physical measurements (ABN). The authors utilized both linear and RBF kernels to account for varying matrix structures. Beyond empirical tests, the authors derived new performance bounds for uniform sampling without replacement by applying concentration inequalities for symmetric functions of random variables. This approach more accurately reflects real-world implementations than previous "with replacement" models.
Key Results and Insights
Empirical Performance
The empirical results consistently favored uniform sampling. For instance, on the PIE-7K dataset with 20% of columns sampled, uniform sampling achieved a relative accuracy of 83.5%, significantly outperforming diagonal (69.8%) and column-norm (79.9%) sampling.
The "simple is better" outcome is attributed to the fact that non-uniform sampling only provides advantages in rare cases where a few columns dominate the matrix—a structure not typically found in standard ML benchmarks. Furthermore, sampling without replacement was found to be superior as it prevents the selection of redundant columns, ensuring a more diverse and informative subset.
Theoretical Advancements
The theoretical analysis provides a "safety certificate" for uniform sampling. The newly derived bounds are significantly tighter than previous state-of-the-art results.
As shown in the figure above, the new bound yields a lower error epsilon for the same number of sampled columns compared to the existing bounds by Drineas and Mahoney (2005). This theoretical tightness aligns with the strong empirical performance observed in practice.
Conclusion
This work demonstrates that uniform sampling without replacement is the optimal choice for the Nyström method in most practical scenarios. It offers $O(1)$ implementation complexity for the sampling distribution, compared to $O(n)$ or $O(n^2)$ for non-uniform alternatives, while providing superior empirical accuracy. By establishing tighter theoretical bounds, the authors validate the efficiency and effectiveness of the most commonly used sampling approach in large-scale machine learning.
Summary updated