Skip to yearly menu bar Skip to main content


Even Faster SVD Decomposition Yet Without Agonizing Pain

Zeyuan Allen-Zhu · Yuanzhi Li

Area 5+6+7+8 #127

Keywords: [ Component Analysis (ICA,PCA,CCA, FLDA) ] [ Matrix Factorization ]

Abstract: We study k-SVD that is to obtain the first k singular vectors of a matrix A approximately. Recently, a few breakthroughs have been discovered on $k$-SVD: Musco and Musco [1] provided the first gap-free theorem for the block Krylov method, Shamir [2] discovered the first variance-reduction stochastic method, and Bhojanapalli et al. [3] provided the fastest $O(nnz(A) + poly(1/eps))$-type of algorithm using alternating minimization. In this paper, we improve the above breakthroughs by providing a new framework for solving k-SVD. In particular, we obtain faster gap-free convergence speed outperforming [1], we obtain the first accelerated AND stochastic method outperforming [3]. In the NNZ running-time regime, we outperform [3] without even using alternating minimization for certain parameter regimes.

Live content is unavailable. Log in and register to view live content