Input-Sparsity Low Rank Approximation in Schatten Norm
share
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∈R^n× k, which, with high probability, satisfy A-YZ^T_p ≤ (1+ϵ)A-A_k_p, where M_p = (∑_i=1^n σ_i(M)^p )^1/p is the Schatten p-norm of a matrix M with singular values σ_1(M), ..., σ_n(M), and where A_k is the best rank-k approximation to A. Our algorithm runs in time Õ(nnz(A) + n^α_ppoly(k/ϵ)), where α_p = 1 for p∈ [1,2) and α_p = 1 + (ω-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 Õ(nnz(A) + n ·poly(k/ϵ)) time, which was previously only known for the Frobenius norm (p = 2). Moreover, since α_p < ω 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.
READ FULL TEXT