Mark Braverman, Ankit Garg, et al.
STOC 2016
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).
Mark Braverman, Ankit Garg, et al.
STOC 2016
T.S. Jayram, David P. Woodruff
ACM Transactions on Algorithms
Zhao Song, David P. Woodruff, et al.
STOC 2017
Arnab Bhattacharyya, Palash Dey, et al.
SIGMOD/PODS 2016