# Optimal CUR Matrix Decompositions

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2014.

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

- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Federated Empirical Risk Minimization via Second-Order Method](https://mlsanity.com/paper/2305.17482/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [Latent Graph Inference with Limited Supervision](https://mlsanity.com/paper/2310.04314/) (2023)
- [Solving Tensor Low Cycle Rank Approximation](https://mlsanity.com/paper/2304.06594/) (2023)
- [A3 : an Analytical Low-Rank Approximation Framework for Attention](https://mlsanity.com/paper/2505.12942/) (2025)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time](https://mlsanity.com/paper/2107.08090/) (2021)
- [Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection](https://mlsanity.com/paper/2106.06983/) (2021)
- [Faster Randomized Methods for Orthogonality Constrained Problems](https://mlsanity.com/paper/2106.12060/) (2021)
- [Fast Graph Neural Tangent Kernel via Kronecker Sketching](https://mlsanity.com/paper/2112.02446/) (2021)
- [Error Analysis of Tensor-Train Cross Approximation](https://mlsanity.com/paper/2207.04327/) (2022)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [CURing Large Models: Compression via CUR Decomposition](https://mlsanity.com/paper/2501.04211/) (2025)
- [Projection-based QLP Algorithm for Efficiently Computing Low-Rank Approximation of Matrices](https://mlsanity.com/paper/2103.07245/) (2021)
- [Performance of ℓ1 Regularization for Sparse Convex Optimization](https://mlsanity.com/paper/2307.07405/) (2023)
- [Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solution](https://mlsanity.com/paper/2309.17403/) (2023)
- [Clustering-Based Low-Rank Matrix Approximation for Medical Image Compression](https://mlsanity.com/paper/2505.08256/) (2025)
- [FL-Sailer: Efficient and Privacy-Preserving Federated Learning for Scalable Single-Cell Epigenetic Data Analysis via Adaptive Sampling](https://mlsanity.com/paper/2605.04519/) (2026)
- [Prompt2Effect: Training-Free Image-to-Video Model Specialization via LoRA Generation](https://mlsanity.com/paper/2606.13971/) (2026)

## Abstract (arXiv)

The CUR decomposition of an m × n matrix A finds an m × c matrix C with a subset of c < n columns of A, together with an r × n matrix R with a subset of r < m rows of A, as well as a c × r low-rank matrix U such that the matrix C U R approximates the matrix A, that is,  || A - CUR ||F2 ≤ (1+ε) || A - Ak||F2, where ||.||F denotes the Frobenius norm and Ak is the best m × n matrix of rank k constructed via the SVD. We present input-sparsity-time and deterministic algorithms for constructing such a CUR decomposition where c=O(k/ε) and r=O(k/ε) and rank(U) = k. Up to constant factors, our algorithms are simultaneously optimal in c, r, and rank(U).