Low-rank approximation with 1/ε1/3 matrix-vector products

We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-p norm. Here, given access to a matrix A through matrix-vector products, an accuracy parameter є, and a target rank k, the goal is to find a rank-k matrix Z with orthonormal columns such that || A (I − Z Z⊤) || Sp ≤ (1+є)min U⊤U = Ik || A (I − U U⊤) || Sp, where || M ||Sp denotes the ℓp norm of the the singular values of M. For the special cases of p=2 (Frobenius norm) and p = ∞ (Spectral norm), Musco and Musco (NeurIPS 2015) obtained an algorithm based on Krylov methods that uses Õ(k/√є) matrix-vector products, improving on the naïve Õ(k/є) dependence obtainable by the power method, where Õ(·) suppresses poly(log(dk/є)) factors.