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 ⊤ ) || S p ≤ (1+є)min U ⊤ U = I k || A ( I − U U ⊤ ) || S p , where || M || S p 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.

Authors

• Ainesh Bakshi
• Kenneth L. Clarkson
• David P. Woodruff

Keywords

• Schatten norms
• Krylov Methods
• Low-rank Approximation
• Matrix-Vector Product Model