Timezone: »

 
Poster
Even Faster SVD Decomposition Yet Without Agonizing Pain
Zeyuan Allen-Zhu · Yuanzhi Li

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #127
in Tuesday Posters »
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.
Keywords: Matrix Factorization · Component Analysis (ICA,PCA,CCA, FLDA)

Author Information

Zeyuan Allen-Zhu (Princeton University)
Yuanzhi Li (Princeton University)

More from the Same Authors