LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain *
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 [19] proved the first gap-free convergence result using the block Krylov method, Shamir [21] discovered the first variance-reduction stochastic method, and Bhojanapalli et al. [7] provided the fastest O(nnz(A) + poly(1/ε))-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 [19], and the first accelerated and stochastic method outperforming [21]. In the O(nnz(A) + poly(1/ε)) running-time regime, LazySVD outperforms [7] in certain parameter regimes without even using alternating minimization.
The main result seems to be an improvement of [14] for spectral-error low rank approximation, from time k*nnz(A)/eps^{1/2} + k^2 d / eps + k^3/eps^{3/2} to k nnz(A)/eps^{1/2} + k^2 d / eps^{1/2}. This is interesting in certain regimes, if say, eps is very small and nnz(A) is about d. Note here the time is worse than nnz(A) times one can achieve with Frobenius norm error, though in certain applications one may need spectral error.   My understanding of the savings - and I hope the authors can clarify this - is that [14] was a bit crude with the k/eps^{1/2} vectors in R^d they find via a block Krylov iteration. I think they just compute an orthonormal basis for such vectors which gives k^2 d/eps time (ignoring fast matrix multi optimizations). This paper achieves k^2 d / eps^{1/2} time essentially because they never have to perform such an orthogonalization; they instead iteratively find a very good rank-1 approx, then they deflate off what they just found, and repeat by finding a very good rank-1 approx on what's left, in total k times. They still need O~(1/eps^{1/2}) iterations for each rank-1 approx, and they need to deflate off what they just found, but given that the vectors they find anyway are almost already orthogonal they just pretend that they are and the deflation takes O(kd/eps^{1/2}) per iteration, giving the O(k^2 d/eps^{1/2}) in total. Another key difference with [14] is that the 1/eps^{1/2} is coming from the shift-and-invert algorithm of [7] and [8], which was not directly used in [14].   By instantiating the above framework with different algorithms in different settings, the authors obtain tradeoffs also in a stochastic setting. They also obtain nnz(A) algorithms with a mixed spectral and Frobenius guarantee though I think there is an issue here - see below.  
I mentioned a comment in the summary above regarding intuition. I hope the authors can clarify that.   Also, of importance, is for the authors to state what is the relationship with the following work which seems to use similar techniques for a similar problem: http://arxiv.org/abs/1607.02925  I didn't find the nnz(A) results very compelling. The main reason is that the authors seem to miss the earlier work of Cohen et al. "Dimensionality Reduction for k-Means Clustering and Low Rank Approximation" http://arxiv.org/pdf/1410.6801v3.pdf Applying Theorem 27 in that paper, with say, the composition of an OSNAP with an SRHT then a Gaussian, one can in nnz(A) + O~(k^2 d/eps^2) time reduce the dimension to k/eps^2 x d, at which point one can find a good low rank-k approximation of the resulting matrix using any method (this is the definition of a projection-cost preserving sketch). Importantly, the same mixed-Frobenius and spectral error guarantee is obtained. Actually the result in the Cohen et al. paper could be stronger because there is an eps/k factor in front of the Frobenius norm term, and importantly it doesn't have a sigma/sigma_{k+1} term in it, as this submission does, which can be arbitrarily large. The overall comparison of the two works depends on which algorithm one uses to solve the k/eps^2 x d problem.   Just a few presentation comments:  (1) the table in the stochastic setting was a bit confusing, it suggests  kn^{3/4} d/(sigma_k^{1/2} eps^{1/2}) <= kd/(sigma_k^2 eps^2).  which can't be true, so I guess the authors instead mean their bound is never worse than what is in parantheses.   (2) in general I feel the writing style could be toned down a bit.