Krylov Methods are (nearly) Optimal for Low-Rank Approximation

MaRDI QIDQ6432334arXivFDO

Authors Ainesh Bakshi, Shyam Narayanan

Publication date 6 April 2023

Published in arXiv

arXiv classification

cs.DScs.LGcs.NAmath.NA

Abstract: We consider the problem of rank-$1$ low-rank approximation (LRA) in the matrix-vector product model under various Schatten norms: ${\displaystyle }$ min_{|u|_2=1} |A (I - u u^ op)|_{mathcal{S}_p} , ${\displaystyle }$ where $|M{|}_{mathcal{S}_p}$ denotes the $el{l}_p$ norm of the singular values of $M$. Given $varepsilon>0$, our goal is to output a unit vector $v$ such that ${\displaystyle }$ |A(I - vv^ op)|_{mathcal{S}_p} leq (1+varepsilon) min_{|u|_2=1}|A(I - u u^ op)|_{mathcal{S}_p}. ${\displaystyle }$ Our main result shows that Krylov methods (nearly) achieve the information-theoretically optimal number of matrix-vector products for Spectral ($p=infty$), Frobenius ($p=2$) and Nuclear ($p=1$) LRA. In particular, for Spectral LRA, we show that any algorithm requires $Omegaleft(log(n)/varepsilo{n}^{1/2}ight)$ matrix-vector products, exactly matching the upper bound obtained by Krylov methods [MM15, BCW22]. Our lower bound addresses Open Question 1 in [Woo14], providing evidence for the lack of progress on algorithms for Spectral LRA and resolves Open Question 1.2 in [BCW22]. Next, we show that for any fixed constant $p$, i.e. $1leqp=O(1)$, there is an upper bound of $Oleft(log(1/varepsilon)/varepsilo{n}^{1/3}ight)$ matrix-vector products, implying that the complexity does not grow as a function of input size. This improves the $Oleft(log(n/varepsilon)/varepsilo{n}^{1/3}ight)$ bound recently obtained in [BCW22], and matches their $Omegaleft(1/varepsilo{n}^{1/3}ight)$ lower bound, to a $log(1/varepsilon)$ factor.

Cited in

(1)

• A recursive butterfly factorization with optimality guarantees

This page was built for publication: Krylov Methods are (nearly) Optimal for Low-Rank Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432334)