# Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2013.

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

- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix Factorization](https://mlsanity.com/paper/2210.12579/) (2022)
- [Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketches](https://mlsanity.com/paper/2206.03827/) (2022)
- [Localization from structured distance matrices via low-rank matrix recovery](https://mlsanity.com/paper/2311.18076/) (2023)
- [ViT-AdaLA: Adapting Vision Transformers with Linear Attention](https://mlsanity.com/paper/2603.16063/) (2026)
- [Sublinear Time Approximation of Text Similarity Matrices](https://mlsanity.com/paper/2112.09631/) (2021)
- [Guaranteed Sampling Flexibility for Low-tubal-rank Tensor Completion](https://mlsanity.com/paper/2406.11092/) (2024)
- [Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection](https://mlsanity.com/paper/2106.06983/) (2021)
- [Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence](https://mlsanity.com/paper/2212.12737/) (2022)
- [Continual Low-Rank Scaled Dot-product Attention](https://mlsanity.com/paper/2412.03214/) (2024)
- [Co-Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/2109.00749/) (2021)
- [One-pass additive-error subset selection for ℓp subspace approximation](https://mlsanity.com/paper/2204.12073/) (2022)
- [Error Analysis of Tensor-Train Cross Approximation](https://mlsanity.com/paper/2207.04327/) (2022)
- [On Subspace Approximation and Subset Selection in Fewer Passes by MCMC Sampling](https://mlsanity.com/paper/2103.11107/) (2021)
- [Boosting Nystr"om Method](https://mlsanity.com/paper/2302.11032/) (2023)
- [Plug-and-play linear attention with provable guarantees for training-free image restoration](https://mlsanity.com/paper/2506.08520/) (2025)
- [CG-GLORE: A Conjugate Gradient-Based Global-Local Regularization Network for Sparse-View CT Reconstruction](https://mlsanity.com/paper/2608.15246/) (2026)

## Abstract (arXiv)

The CUR matrix decomposition and the Nystr"om approximation are two important low-rank matrix approximation techniques. The Nystr"om method approximates a symmetric positive semidefinite matrix in terms of a small number of its columns, while CUR approximates an arbitrary data matrix by a small number of its columns and rows. Thus, CUR decomposition can be regarded as an extension of the Nystr"om approximation. In this paper we establish a more general error bound for the adaptive column/row sampling algorithm, based on which we propose more accurate CUR and Nystr"om algorithms with expected relative-error bounds. The proposed CUR and Nystr"om algorithms also have low time complexity and can avoid maintaining the whole data matrix in RAM. In addition, we give theoretical analysis for the lower error bounds of the standard Nystr"om method and the ensemble Nystr"om method. The main theoretical results established in this paper are novel, and our analysis makes no special assumption on the data matrices.