# Matrix Coherence and the Nystrom Method

arXiv: https://arxiv.org/abs/1408.2044 · HTML: https://mlsanity.com/paper/1408.2044/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Aug 2014.

## Built on by (most cited first, 8 of 8)

- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Target alignment in truncated kernel ridge regression](https://mlsanity.com/paper/2206.14255/) (2022)
- [Localization from structured distance matrices via low-rank matrix recovery](https://mlsanity.com/paper/2311.18076/) (2023)
- [Sublinear Time Approximation of Text Similarity Matrices](https://mlsanity.com/paper/2112.09631/) (2021)
- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)
- [Boosting Nystr"om Method](https://mlsanity.com/paper/2302.11032/) (2023)
- [Making the Nystr"om method highly accurate for low-rank approximations](https://mlsanity.com/paper/2307.05785/) (2023)
- [Recovering Wasserstein Distance Matrices from Few Measurements](https://mlsanity.com/paper/2509.19250/) (2025)

## Abstract (arXiv)

The Nystrom method is an efficient technique used to speed up large-scale learning applications by generating low-rank approximations. Crucial to the performance of this technique is the assumption that a matrix can be well approximated by working exclusively with a subset of its columns. In this work we relate this assumption to the concept of matrix coherence, connecting coherence to the performance of the Nystrom method. Making use of related work in the compressed sensing and the matrix completion literature, we derive novel coherence-based bounds for the Nystrom method in the low-rank setting. We then present empirical results that corroborate these theoretical bounds. Finally, we present more general empirical results for the full-rank setting that convincingly demonstrate the ability of matrix coherence to measure the degree to which information can be extracted from a subset of columns.