When dealing with massive datasets, modern machine learning algorithms frequently run into a computational brick wall. Operations like computing the Singular Value Decomposition (SVD), kernel ridge regression, or training long-sequence Transformers scale quadratically or cubically with the size of the matrix.
To bypass this bottleneck, a common strategy is matrix sketching or subsampling: instead of operating on the entire matrix, we randomly select a subset of rows or columns to build a low-rank approximation. The simplest, cheapest way to do this is uniform random sampling. But while uniform sampling works brilliantly on some datasets, it fails catastrophically on others.
The factor that dictates this success or failure is matrix coherence—a measure of how evenly information is distributed across a matrix.
The Intuition of Information Concentration
To understand why uniform sampling is highly sensitive to matrix coherence, imagine trying to summarize a book by randomly picking 10 pages to read.
If the book is an encyclopedia where every page contains an equal density of independent facts, your random sample will give you a fair representation of the overall book. This is a low-coherence matrix: its structural information is spread out globally and evenly across all rows and columns.
Now imagine the book is a mystery novel where the entire plot hinges on a single sentence written on page 247. If you sample 10 pages at random, you are almost certain to miss page 247. Your summary will completely fail to capture the essence of the story. This is a high-coherence matrix: its critical structural information is concentrated within a tiny number of highly influential rows or columns.
As Talwalkar et al. demonstrated, a matrix simply being "low-rank" is not enough to guarantee that randomized approximations like the Nyström method will succeed. If a matrix is highly coherent, uniform random selection acts like looking for a needle in a haystack; it will likely miss the specific columns necessary to define the matrix's underlying structure, resulting in massive reconstruction errors.
This vulnerability to information concentration shows up across many domains:
- Kernel Methods: Jin et al. showed that the theoretical error bounds of uniform Nyström sampling degrade heavily when data structures are highly coherent.
- Graph Neural Networks: Gittens et al. observed that uniform sampling fails completely on sparse graphs, where the underlying topology concentrates information into a few critical hub nodes.
- Deep Learning Attention: Zhou et al. noted that standard random sampling becomes unreliable for long-sequence Transformer attention when the attention maps contain "spiky," highly localized features.
The Catch-22 of Coherence Estimation
If coherence determines whether a fast uniform sampling shortcut will work, the obvious solution is to calculate the matrix's coherence before deciding how to sample it.
However, this introduces a fundamental "chicken-and-egg" dilemma, or Catch-22, described by Mohri et al.. To compute the exact coherence of a matrix, you must first compute its singular vectors or full leverage scores. But computing these vectors requires running the exact expensive, full-scale matrix computations that you were trying to avoid by sampling in the first place!
To break this loop, Mohri et al. developed a fast, sampling-based approximation algorithm designed specifically to estimate matrix coherence efficiently. This allows practitioners to test the waters of a massive dataset and diagnose its information distribution before committing to a sketching strategy.
Strategies for Defeating High Coherence
When a matrix is highly coherent, uniform sampling is off the table. Researchers have developed three primary paradigms to safely compress these difficult matrices.
1. Data-Dependent Importance Sampling (Leverage Scores)
If some columns are vastly more important than others, we should change our sampling probabilities to favor them. Instead of uniform sampling, we can sample columns based on their leverage scores—a metric that quantifies how much "influence" a particular row or column has over the rest of the matrix.
Papailiopoulos et al. proved that a purely deterministic selection of the highest leverage score columns can provide rigorous accuracy guarantees, provided the dataset's leverage scores follow a "power-law" decay (meaning a few elements dominate, which is true for most real-world data).
To make this practical without incurring massive computational overhead, Musco et al. introduced a recursive sampling scheme based on ridge leverage scores. This approach allows algorithms to iteratively discover and sample rare, highly influential points in linear time, making data-dependent Nyström approximation highly scalable.
2. Random Projections and "Smearing" Information
If the information in a matrix is too concentrated, another option is to physically force it to spread out. This is the philosophy behind random projection methods like the Subsampled Randomized Walsh-Hadamard Transform (SRHT).
Avron et al. utilized this technique to accelerate Canonical Correlation Analysis (CCA). The SRHT acts as a mathematical blender: by multiplying the high-coherence input matrix by a structured random matrix, it flattens out the localized "spikes" of information and distributes them evenly across all dimensions. Because the resulting transformed matrix is guaranteed to have low coherence, uniform sampling can then be applied safely without risking the loss of critical features.
3. $\ell_2$ Augmentation for Subspace Embeddings
When approximating matrices under non-standard norms (such as $\ell_p$ sensitivity sampling for coreset construction), purely importance-based sampling can introduce a different failure mode: rank deficiency.
As Munteanu et al. discovered, if you sample a matrix strictly based on its $\ell_p$ norm importance, the algorithm can become hyper-focused on optimizing for that specific norm's scale. In doing so, it may completely neglect certain underlying dimensions, causing the sampled matrix to lose rank or become poorly conditioned.
The authors solved this by introducing $\ell_2$ augmentation. By mixing standard $\ell_p$ sensitivities with $\ell_2$ leverage scores, the sampling distribution is regularized. The $\ell_2$ leverage scores act as a safety net, ensuring that the geometric subspace remains stable and full-rank, allowing sensitivity sampling to achieve optimal, linear sample complexity.
Key Foundational Work
Matrix Coherence and the Nystrom Method (2010) — contributed 3 concept elements to this direction.
Can matrix coherence be efficiently and accurately estimated? (2011) — contributed 2 concept elements to this direction.
On the Estimation of Coherence (2010) — contributed 1 concept elements to this direction.