Input-Sparsity Low Rank Approximation in Schatten Norm

We give the first input-sparsity time algorithms for the rank-k low rank approximation problem in every Schatten norm. Specifically, for a given n× n matrix A, our algorithm computes Y,Z∈ ℝn× k, which, with high probability, satisfy |A-YZT|p ≤ (1+ε)|A-Ak|p, where |M|p = left (sumi=1n σi(M)p right )1/p is the Schatten p-norm of a matrix M with singular values σ1(M), ldots, σn(M), and where Ak is the best rank-k approximation to A. Our algorithm runs in time tildeO(operatornamennz(A) + mnαpoperatornamepoly(k/ε)), where αp = 0 for p∈ [1,2) and αp = (ω-1)(1-2/p) for p>2 and ω ≈ 2.374 is the exponent of matrix multiplication. For the important case of p = 1, which corresponds to the more "robust" nuclear norm, we obtain tildeO(operatornamennz(A) + m · operatornamepoly(k/ε)) time, which was previously only known for the Frobenius norm (p = 2). Moreover, since αp < ω - 1 for every p, our algorithm has a better dependence on n than that in the singular value decomposition for every p. Crucial to our analysis is the use of dimensionality reduction for Ky-Fan p-norms.