LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

Abstract

We study $k$-SVD that is to obtain the first $k$ singular vectors of a matrix $A$. Recently, a few breakthroughs have been discovered on $k$-SVD: Musco and Musco [1] proved the first gap-free convergence result using the block Krylov method, Shamir [2] discovered the first variance-reduction stochastic method, and Bhojanapalli et al. [3] provided the fastest $O(\mathsf{nnz}(A)+\mathsf{poly}(1/\epsilon ))$-time algorithm using alternating minimization. In this paper, we put forward a new and simple LazySVD framework to improve the above breakthroughs. This framework leads to a faster gap-free method outperforming [1], and the first accelerated and stochastic method outperforming [2]. In the $O(\mathsf{nnz}(A)+\mathsf{poly}(1/\epsilon ))$ running-time regime, LazySVD outperforms [3] in certain parameter regimes without even using alternating minimization.

first circulated on May 20, 2016; this newer version improves writing

Cited by in corpus (7)

• CONE-Align: Consistent Network Alignment with Proximity-Preserving Node Embedding
• Natasha: Faster Non-Convex Stochastic Optimization Via Strongly Non-Convex Parameter
• Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization
• Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls
• Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• Faster Principal Component Regression and Stable Matrix Chebyshev Approximation