Embeddings of schatten norms with applications to data streams
Yi Li, David P. Woodruff
ICALP 2017
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).
Yi Li, David P. Woodruff
ICALP 2017
Zhao Song, David P. Woodruff, et al.
STOC 2017
Christos Boutsidis, Malik Magdon-Ismail
Information Processing Letters
Andrew McGregor, A. Pavan, et al.
Algorithmica