Optimal CUR matrix decompositions

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

Authors

• Christos Boutsidis
• David P. Woodruff

Keywords

• CUR
• SVD
• adaptive sampling
• column subset selection
• input-sparsity-time
• leverage scores
• low rank matrix decomposition
• spectral sparsification