Kernel methods and spectral algorithms are among the most powerful tools in machine learning for capturing non-linear relationships, mapping complex manifolds, and clustering data. However, they suffer from a notorious "cubic bottleneck": computing an exact $n \times n$ kernel or affinity matrix requires $O(n^2)$ space and $O(n^3)$ time, making them impractical for large datasets.
To bypass this bottleneck, practitioners rely on low-rank matrix approximations. The most prominent framework for this is the Nyström method. Instead of computing the relationships between all pairs of data points, the Nyström method selects a small subset of $m$ representative points—called landmarks or anchor points—where $m \ll n$. By computing the kernel matrix only between the full dataset and these landmarks ($n \times m$) and among the landmarks themselves ($m \times m$), we can reconstruct an approximation of the full $n \times n$ matrix in linear time.
As John Platt demonstrated in FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms, many seemingly distinct scalable manifold learning algorithms are fundamentally variations of this single Nyström framework. Similarly, Weinberger et al. leveraged this concept in Nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization to scale semidefinite embedding by orders of magnitude.
The core challenge of this approach is simple: The quality of the entire approximation hinges entirely on which landmarks you choose.
The Failure of Uniform Random Sampling
The simplest way to choose landmarks is uniform random sampling. While computationally effortless ($O(1)$ selection time) and mathematically tractable, uniform sampling often yields poor approximations in real-world datasets.
To understand why, imagine trying to map the topography of a mountain range. If you pick your survey points completely at random, you will heavily oversample the vast, flat valleys (where most of the surface area lies) and completely miss the narrow ridges and peaks that define the geometry of the landscape.
In data science, this manifests in several ways:
- Missing Isolated Clusters: As noted by Bouneffouf et al. in Sampling with Minimum Sum of Squared Similarities for Nystrom-Based Large Scale Spectral Clustering, uniform sampling frequently fails to capture small or isolated data clusters, leading to broken manifold representations.
- Incomplete Bases: Abdolali et al. showed in Scalable and robust sparse subspace clustering using randomized clustering and multilayer graphs that if the chosen anchors are not well-distributed, the resulting dictionary provides an incomplete basis for representing the original samples.
- High Coherence Bottlenecks: In datasets where a small number of points contain the majority of the structural information (high coherence), Affandi et al. argued in Nystrom Approximation for Large-Scale Determinantal Processes that random sampling fails to reliably identify these critical landmarks.
When uniform sampling selects suboptimal landmarks, the downstream model suffers a severe drop in performance, whether it is an image classifier losing accuracy (Tsai et al. in Solving Nonlinear SVM in Linear Time? A Nyström Approximated SVM with Applications to Image Classification) or a biological visualization misrepresenting cellular structures (Kuchroo et al. in Multiscale PHATE Exploration of SARS-CoV-2 Data Reveals Multimodal Signatures of Disease).
Designing Smarter Surveyors: Non-Uniform Strategies
To fix this, researchers have developed data-dependent, non-uniform landmark selection strategies. These methods act as intelligent surveyors, evaluating the global geometry of the data to pick the most informative points. These strategies generally fall into three categories.
1. Distance and Density-Based Spreading
Instead of sampling purely by density (which oversamples dense regions), these methods explicitly force landmarks to be geometrically diverse.
A prime example is using Kernel K-means++ initialization to select landmarks. As demonstrated in Nyström Method with Kernel K-means++ Samples as Landmarks, this approach uses a probabilistic distance-based mechanism to ensure that each new landmark is chosen far away from already selected landmarks. This guarantees global coverage of the data manifold.
Similarly, the Minimum Sum of Squared Similarities (MSSS) framework proposed by Bouneffouf et al. explicitly minimizes the redundancy between landmarks, ensuring that every selected anchor point adds novel geometric information to the low-rank approximation.
2. Statistical Leverage Scores
Leverage scores measure the "influence" or uniqueness of a data point relative to the rest of the dataset. Points in low-density regions or points that act as critical bridges between clusters have high leverage scores.
Sampling landmarks proportional to their leverage scores ensures that rare but structurally vital regions are preserved. The utility of integrating leverage scores has been highlighted across various domains, from distributed kernel ridge regression (Yin et al. in Distributed Nyström Kernel Learning with Communications) to kernel mean embeddings (Chatalic et al. in Nyström Kernel Mean Embeddings).
3. Task-Specific and Learnable Landmarks
Rather than treating landmark selection as a purely unsupervised preprocessing step, some frameworks incorporate downstream task information.
Zhang et al. introduced this in Improved Nystrom Low-rank Decomposition with Priors by aligning the landmark selection with task-specific priors, such as class labels. More recently, Zarvandi et al. in Interpretable Kernel Representation Learning at Scale: A Unified Framework Utilizing Nyström Approximation pointed toward learnable or adaptive landmark selection mechanisms that dynamically optimize the anchor points during self-supervised training.
The Fundamental Trade-off
If non-uniform sampling strategies are so much more accurate, why isn't uniform sampling completely obsolete? The answer lies in a fundamental trade-off between preprocessing cost and approximation fidelity.
Uniform Sampling ──────────────────────────► High Leverage Score Sampling
[Low Selection Cost / High Error] [High Selection Cost / Low Error]
As reviewed by Zhu et al. in A review of Nyström methods for large-scale machine learning and Kashima et al. in Recent Advances and Trends in Large-Scale Kernel Methods, low-rank approximations exhibit extreme sensitivity to this choice:
- The Computational Cost of Selection: Calculating exact leverage scores or running iterative clustering algorithms over millions of points requires significant time and memory. As Chen et al. noted in Error Analysis of Generalized Nyström Kernel Regression, advanced sampling techniques often require expensive matrix operations that can inadvertently negate the very efficiency gains that the Nyström method was chosen to provide.
- The Parsimony of the Representation: On the flip side, a sophisticated selection strategy allows you to achieve a target accuracy with a significantly smaller number of landmarks ($m$). A smaller $m$ means the final downstream model (like a Support Vector Machine or a spectral embedding) is much smaller, faster, and more memory-efficient during inference.
Ultimately, the goal of modern landmark selection research is to find the sweet spot on this Pareto frontier: designing selection heuristics that can approximate the global geometry of a dataset in nearly-linear time, ensuring both rapid training and highly accurate low-rank representations.
Key Foundational Work
A Scalable Kernel-Based Algorithm for Semi-Supervised Metric Learning (2007) — contributed 1 concept elements to this direction.
FastMap, MetricMap, and Landmark MDS are all Nystrom Algorithms (2005) — contributed 1 concept elements to this direction.
Nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization (2005) — contributed 1 concept elements to this direction.