David P. Woodruff
Foundations and Trends in Theoretical Computer Science
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 CUR approximates the matrix A, that is, ∥A-CUR∥2 F ≤ (1 + ϵ) ∥A-Ak∥2 F, 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 the values c, r, and rank(U).
David P. Woodruff
Foundations and Trends in Theoretical Computer Science
Ravindran Kannan, Santosh S. Vempala, et al.
JMLR
Jiecao Chen, He Sun, et al.
NeurIPS 2016
Christos Boutsidis, David P. Woodruff
STOC 2014