Optimal CUR Matrix Decompositions

2014/05/30 by Christos Boutsidis, David P. Woodruff, Boutsidis, Christos +1 · 10 citations
Engineering · Mathematics · #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1405.7910

openalex publication_date 2014/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 ||_F² ≤ (1+ε) || A - A_k||_F², where ||.||_F denotes the Frobenius norm and A_k 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).

Cited by

• Generalized Interlacing Families: New Error Bounds for CUR Matrix Decompositions
• How many integrals should be evaluated at least in two-dimensional hyperinterpolation?
• Subset selection for matrices in spectral norm
• Efficient Frequent Directions Algorithm for Sparse Matrices
• Dimensionality Reduction for k-Means Clustering and Low Rank\n Approximation
• S^\top S-SVD via Sketching and the Nearest S^\top S-orthogonal Matrix
• Optimal Sparse Linear Auto-Encoders and Sparse PCA
• Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse
• A3 : an Analytical Low-Rank Approximation Framework for Attention
• Clustering-Based Low-Rank Matrix Approximation for Medical Image Compression

Related

• Simpler is better: A comparative study of randomized algorithms for computing the CUR decomposition
• Relative-Error CUR Matrix Decompositions
• CUR Decompositions, Approximations, and Perturbations
• A Simple Approach to Optimal CUR Decomposition
• Perspectives on CUR Decompositions