mlsanityData to 7 Oct 2026

Optimal CUR Matrix Decompositions

arXiv 1405.7910 ↗First posted 30 May 2014cs.DS cs.LG cs.NAcited by 29

Not on the map. Why?

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).

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 3; 2023: 10; 2024: 2; 2025: 4; 2026: 2.

29 papers.

Sort:

By area:

  1. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  2. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  3. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  4. 2022Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerabilitycited by 25
  5. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  6. 2021Robust CUR Decomposition: Theory and Imaging Applicationscited by 20
  7. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  8. 2022Dynamic Tensor Product Regressioncited by 17
  9. 2021Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositionscited by 13
  10. 2023Federated Empirical Risk Minimization via Second-Order Methodcited by 9
  11. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  12. 2023Latent Graph Inference with Limited Supervisioncited by 9
17 more
  1. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  2. 2025A3 : an Analytical Low-Rank Approximation Framework for Attentioncited by 7
  3. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  4. 2021Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Timecited by 4
  5. 2021Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selectioncited by 2
  6. 2021Faster Randomized Methods for Orthogonality Constrained Problemscited by 2
  7. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  8. 2022Error Analysis of Tensor-Train Cross Approximationcited by 1
  9. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  10. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  11. 2025CURing Large Models: Compression via CUR Decompositioncited by 1
  12. 2021Projection-based QLP Algorithm for Efficiently Computing Low-Rank Approximation of Matricescited by 0
  13. 2023Performance of ℓ1 Regularization for Sparse Convex Optimizationcited by 0
  14. 2023Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solutioncited by 0
  15. 2025Clustering-Based Low-Rank Matrix Approximation for Medical Image Compressioncited by 0
  16. 2026FL-Sailer: Efficient and Privacy-Preserving Federated Learning for Scalable Single-Cell Epigenetic Data Analysis via Adaptive Samplingcited by 0
  17. 2026Prompt2Effect: Training-Free Image-to-Video Model Specialization via LoRA Generationcited by 0