PaperlayerView exact revision on arXiv

Source-linked AI summary

LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain

Zeyuan Allen-Zhu, Yuanzhi Li

arXiv:1607.03463v2math.NAcs.DScs.LGcs.NAmath.OCstat.ML

TL;DR

Computing k-SVD can be expensive, and existing approaches have limitations in gap dependence, acceleration, or warm-start requirements. This paper introduces LazySVD, a simple framework that improves on prior methods. It reports faster gap-free and accelerated stochastic methods, plus NNZ improvements in certain parameter regimes without alternating minimization.

  • Problem

    Computing k-SVD is expensive, while prior methods have limitations including gap dependence, lack of acceleration, or a costly-to-obtain accurate warm start.

    Source: §1 · pp. 1–2

  • Method

    LazySVD is a simple framework for k-SVD whose analysis relies on convex optimization.

    Source: §1 · p. 3, §1.1 · p. 3

  • Results

    LazySVD yields a faster gap-free method, an accelerated stochastic method that outperforms Shamir, and NNZ improvements over in certain parameter regimes without alternating minimization.

    Source: §1.1 · p. 3

  • Takeaways & Limitations

    In certain parameter regimes, LazySVD improves NNZ running time without using alternating minimization.

    Source: §1.1 · p. 3

    The paper says it has not tried hard to improve the NNZ results’ dependence on k or σ1/σk+1.

    Source: §5 · p. 10

Abstract

from arXiv · show

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/\varepsilon))$-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/\varepsilon))$ running-time regime, LazySVD outperforms [3] in certain parameter regimes without even using alternating minimization.

1 Introduction

The introduction presents LazySVD, a simple framework for k-SVD that improves recent methods and uses convex analysis. Repeated 1-SVD calls yield gap-dependent or gap-free guarantees, an accelerated stochastic method, and improved running times in some NNZ regimes.

1 Introduction

  • SVD decomposes a matrix into singular vectors and values; k-SVD seeks its top k left singular vectors, while traditional SVD can be expensive for large data.The introduction also describes k-SVD’s best rank-k approximation and its uses in retrieval, denoising, and compression.Source: §1 · p. 1

1.1 Our Results and the Settlement of an Open Question

  • LazySVD improves recent k-SVD methods through a simple framework whose analysis relies on convex optimization.Different choices of the 1-SVD subroutine produce algorithms for different needs.Source: §1 · p. 3, §1.1 · p. 3
  • Each of k-SVD’s top k singular vectors can be obtained through repeated 1-SVD calls, projecting out each leading vector before the next call.The introduction describes this as k repetitions of 1-SVD.Source: §1.1 · p. 3
  • LazySVD answers an open question about single-vector methods by avoiding dependence on all intermediate singular-value gaps.Earlier accounts said such methods depended on every intermediate gap, making them ineffective when singular values were close.Source: §1.1 · p. 3
  • The resulting running time depends either on gap^-0.5 for the relative gap between σk and σk+1, or on ε^-0.5 without a gap assumption.Both dependencies match the best-known dependency for block methods.Source: §1.1 · p. 3
  • Using variance reduction for 1-SVD yields the first accelerated stochastic k-SVD algorithm, outperforming Shamir.The introduction notes that Shamir’s method was not accelerated and required a highly accurate warm start whose computation time was unclear.Source: §1.1 · p. 3, §1 · p. 3
  • If A is subsampled before LazySVD, running time becomes eO(nnz(A) + ε^-2poly(k) · d), improving upon in certain (but sufficiently interesting) parameter regimes while completely avoiding alternating minimization.Source: §1.1 · p. 3
  • LazySVD’s analysis uses convex optimization, and the method works without knowing k in advance, unlike block methods.The paper states that 1-SVD is solvable using convex techniques.Source: §1.1 · p. 3

2 Preliminaries

The preliminaries relate k-SVD to k-PCA and establish matrix notation and an approximate matrix-inversion setup used by the algorithms.

2 Preliminaries

  • The notation distinguishes spectral, Frobenius, and Schatten q-norms and uses A ⪰ B to mean A − B is positive semidefinite.Source: §2 · p. 4
  • Solving k-SVD for A is equivalent to solving k-PCA for M = AA⊤.Source: §2 · p. 4
  • The paper uses λ_k(M) for the kth-largest eigenvalue, σ_k(A) for the kth-largest singular value, and A*_k for the best rank-k approximation.Source: §2 · p. 4
  • To approximate (λI − M)^−1b, the setup minimizes the quadratic f(x) = x⊤(λI − M)x − b⊤x when λI − M is positive definite.Source: §2 · p. 4

3 A Specific 1-SVD Algorithm: Shift-and-Inverse Revisited

This section revisits AppxPCA, a multiplicative-approximation algorithm for the leading eigenvector of a symmetric matrix. Its guarantee and oracle-call bound support its use as a shift-and-inverse subroutine in LazySVD.

3 A Specific 1-SVD Algorithm: Shift-and-Inverse Revisited

  • AppxPCA reduces 1-PCA to oracle calls to an approximate matrix-inversion subroutine, and practitioners may instead use an algorithm such as Lanczos.Source: §3 · pp. 5–6
  • The authors reprove a shift-and-inverse result to provide a more refined running-time statement with a multiplicative-error guarantee.Source: §3 · p. 5
  • With probability at least 1 − p, AppxPCA returns w satisfying (w⊤u_i)^2 ≤ ε and w⊤Mw ≥ (1 − δ×)(1 − ε)λ_1.Source: §3 · p. 5
  • The total number of oracle calls to the inversion method is O(log(1/δ×)m1 + m2), with stated conditions on each shift λ(s).Source: §3 · p. 5

4 Main Algorithm and Theorems

LazySVD builds a rank-k approximation by repeatedly finding an approximate leading eigenvector of a projected matrix. Its theorems give approximation guarantees for k-SVD, including gap-dependent and gap-free results.

4 Main Algorithm and Theorems

  • LazySVD calls AppxPCA k times, each time finding an approximate leading eigenvector of the current projected matrix and projecting away that vector.When M = AA⊤, the framework returns an approximate k-SVD of A.Source: §4 · p. 6

4.1 Our Core Theorems

  • Theorem 4.1 gives probabilistic approximation guarantees for the output subspace, residual spectral norm, and Rayleigh quotients.The output Vk is column-orthonormal, and the theorem holds with probability at least 1 − p.Source: §4.1 · pp. 6–7

4.2 Our Main Results for k-SVD

  • LazySVD’s k-SVD corollaries include both gap-dependent and gap-free guarantees, with running times that depend only poly-logarithmically on 1/ε.The paper also reports a standard Frobenius-norm guarantee for its gap-free result.Source: §4.2 · pp. 7–8

4.3 High-Level Ideas Behind Our Theorems

  • The analysis propagates approximation error across iterations at most linearly in k, rather than allowing a naive bound to grow exponentially.The proof extends the correctness argument to approximate eigenvectors and develops a gap-free variant of the Wedin theorem.Source: §4.3 · p. 9

5 NNZ Running Time

The paper adapts LazySVD to NNZ running times by sampling columns or entries before applying the framework. The resulting ε-dependence varies with the sampling and matrix-inversion choices.

5 NNZ Running Time

  • 1/ε²·⁵ running time follows when AGD is combined with either column or entry sampling; 1/ε² follows with accelerated SVRG and column sampling.The paper describes these as translations of its results to the O(nnz(A) + poly(k, 1/ε)(n + d)) regime.Source: §5 · p. 9
  • The sampled-matrix results provide both a spectral-norm guarantee and a Frobenius-norm guarantee for the resulting rank-k approximation.The spectral guarantee is additive in ε times the best rank-k spectral error, while the Frobenius guarantee is multiplicative by 1 + ε.Source: §5 · p. 10
  • The NNZ results prioritize improving ε-dependence to 1/ε²; the authors say k and σ1/σk+1 factors may be improvable and that Frobenius analysis is harder in their proof.They describe 1/ε² as matching the sampling complexity and as challenging to improve.Source: §5 · p. 10

6 Experiments

The experiments compare LazySVD with block power and block Krylov methods on four sparse datasets. Across the selected performance plots, LazySVD almost universally outperforms its three competitors.

6 Experiments

  • For a fixed T, all four methods make the same number of dataset passes, while LazySVD avoids block orthogonalization and a final (Tk)-dimensional SVD.The authors therefore compare methods by running time rather than by T.Source: §6 · p. 11
  • The comparison uses four datasets, k values of 10, 20, and 30, and four performance metrics, yielding 48 plots.The paper selects six plots for the main figure and places the full plots in the appendix.Source: §6 · pp. 10–11
  • LazySVD outperforms its three competitors almost universally in the reported experiments.Figure 1 plots relative error against running time; the paper reports six representative plots from 48 total.Source: §6 · p. 11, Figure 1 · p. 11
  • Krylov(unstable) performs better than stable Krylov for small T, but its instability makes it less useful for accurate solutions.The paper notes that its dotted green curves can rise when T is large.Source: §6 · p. 11
  • The subspace power method is the slowest of the compared methods, which the authors attribute to its lack of acceleration.Source: §6 · p. 12

A.1 Inexact Power Method

The appendix reviews the exact power method and states a high-probability result for its inexact version. It also describes the random initialization used in the argument.

A.1 Inexact Power Method

  • The classical power method repeatedly multiplies a starting unit vector by M and normalizes the result.Source: §A.1 · p. 12
  • The proof uses a random unit starting vector and states that the success probability is at least 1 − p.Source: §A.1 · p. 12
  • The appendix states an inexact power-method result that holds with probability at least 1 − p after a threshold number of iterations.The theorem specifies a per-iteration error parameter, but the supplied passage does not include the resulting bound.Source: §A.1 · pp. 12–13

A.2 Proof of Theorem 3.1

The proof establishes AppxPCA’s guarantees through an iterative analysis of shifted inverse matrices, then bounds the final eigenvalue estimate and oracle-call count.

A.2 Proof of Theorem 3.1

  • The proof inductively establishes the iteration claims, while omitting the base-case proof for s = 1.It defines A(s) = (λ(s)I − M)^−1 for the induction.Source: §A.2 · p. 14
  • λ(f) − λ1 ≤ δ×λ1 at termination, with the proof’s success probability at least 1 − p.The bound follows from the final-iteration estimate and termination criterion.Source: §A.2 · p. 15
  • The repeat-until loop uses at most O(log(1/δ×)m1 + m2) oracle calls to A.The proof bounds the loop iterations by O(log(1/δ×)).Source: §A.2 · p. 15

B Lemmas Needed for Proving Our Main Theorem

This section assembles matrix lemmas used to prove Theorem 4.1, covering approximate projection, gap-free eigenspace comparison, and projected power iteration.

B.1 Approximate Projection Lemma

  • The approximate projection lemma constructs a basis from the projection of Vs onto the leading eigenspace when Vs has limited overlap with the lower-eigenvalue subspace.The lemma’s setup uses ∥V_s⊤U∥2 ≤ ε and defines Qs from U⊥(U⊥)⊤Vs.Source: §B.1 · p. 16

B.2 Gap-Free Wedin Theorem

  • The gap-free Wedin lemma compares eigenspaces of nearby PSD matrices using a threshold separation τ, without requiring a stated spectral gap within either matrix.Its setup assumes ∥A − B∥2 ≤ ε and eigenvalue thresholds µ and µ + τ.Source: §B.2 · p. 17

B.3 Projected Power Method

  • Lemma B.4 considers a unit vector v with ||v^T U||_2 <= epsilon <= 1/2, where U contains eigenvectors with eigenvalue <= mu, and projects v onto U_perp.The proof applies Lemma B.3 on A = M'', U and B = M', V = V2, then Proposition B.1 to A = U and B = V1.Source: §B.3 · p. 18

C Proof Details for Theorem 4.1: Our Main Theorem

The proof builds LazySVD’s guarantees inductively, using projected AppxPCA vectors to track eigenspaces and establish bounds for the residual matrix and returned vectors.

C Proof Details for Theorem 4.1: Our Main Theorem

C.1 Proofs of Corollary 4.3 and Corollary 4.4

The corollary proofs specialize Theorem 4.1 to a gap-based subspace guarantee and to spectral- and Frobenius-norm approximation guarantees.

C.1 Proofs of Corollary 4.3 and Corollary 4.4

  • Setting δ× = gap specializes Theorem 4.1’s subspace guarantee to the eigenspace indexed by k + 1.The proof identifies j = k + 1 and applies the bound on ∥V_k⊤U∥2.Source: §C.1 · p. 22
  • Corollary 4.4 applies Theorem 4.1 with q = ∞ for the spectral-norm guarantee and q = 1 for the Frobenius-norm guarantee.The proof identifies the rank-k SVD as the comparison target.Source: §C.1 · p. 22

D Proof Details for Our NNZ Running-Time Results

The appendix establishes NNZ running-time results through a singular-value perturbation proposition and sampling-based guarantees. It treats column sampling for spectral- and Frobenius-norm guarantees, and entry-wise sampling for a spectral-norm guarantee.

D Proof Details for Our NNZ Running-Time Results

  • If ∥A − A′∥2 ≤ η, each singular value σk(A) differs from σk(A′) by at most η.The proposition is proved using the Courant–Fischer characterization.Source: D Proof Details for Our NNZ… · p. 23

D.1 Column Sampling with Spectral-Norm Guarantee

  • Column sampling transfers a LazySVD approximation to a spectral guarantee; with AGD, runtime is O(nnz(A)) + eO(kmd/√ε).The section also treats accelerated SVRG, with a stated improvement in dependence on ε under a condition on ε and the residual.Source: §D.1 · pp. 23, 25

D.2 Column Sampling with Frobenius-Norm Guarantee

  • Column sampling also yields a Frobenius-norm guarantee for LazySVD’s output on the original matrix.The subsection gives a sampling lemma and a theorem for this guarantee.Source: §D.2 · pp. 25–26

D.3 Entry-Wise Sampling with Spectral-Norm Guarantee

  • Entry-wise sampling transfers an approximate solution to a spectral guarantee on the original matrix.The subsection states a theorem for the entry-sampled matrix and gives a total runtime beginning with O(nnz(A)).Source: §D.3 · pp. 26–27
Loading 1607.03463v2…