Optimal CUR Matrix Decompositions

Abstract

The CUR decomposition of an $m\times n$ matrix $A$ finds an $m\times c$ matrix $C$ with a subset of $c<n$ columns of $A,$ together with an $r\times n$ matrix $R$ with a subset of $r<m$ rows of $A,$ as well as a $c\times r$ low-rank matrix $U$ such that the matrix $CUR$ approximates the matrix $A,$ that is, $||A-CUR|{|}_F^2\le (1+\epsilon )||A-A_k|{|}_F^2$, where $||.|{|}_F$ denotes the Frobenius norm and $A_k$ is the best $m\times 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/\epsilon )$ and $r=O(k/\epsilon )$ and rank$(U)=k$. Up to constant factors, our algorithms are simultaneously optimal in $c,r,$ and rank$(U)$.

small revision in lemma 4.2

Cited by in corpus (16)

• Sketching as a Tool for Numerical Linear Algebra
• CUR Algorithm for Partially Observed Matrices
• Provably Correct Algorithms for Matrix Column Subset Selection with Selectively Sampled Data
• Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
• Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach
• Low Rank Approximation with Entrywise ${\ell }_1$-Norm Error
• Rectangular maximum volume and projective volume search algorithms
• Generalized Leverage Score Sampling for Neural Networks
• Hybrid CUR-type decomposition of tensors in the Tucker format
• Optimal Principal Component Analysis in Distributed and Streaming Models
• An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications
• Optimal Sparse Linear Auto-Encoders and Sparse PCA
• A near-optimal algorithm for approximating the John Ellipsoid
• Incomplete Pivoted QR-based Dimensionality Reduction
• Efficient Frequent Directions Algorithm for Sparse Matrices
• Sketching Transformed Matrices with Applications to Natural Language Processing