Stochastic Power Iteration with Momentum
This repository contains the Julia code that produces all the experimental results in the paper Accelerated Stochastic Power Iteration.
The main code of the implementation for different PCA algorithms is in the file
minibatch_sgd_m(data, x, beta, iters, u, s, seed=1): This function is the implementation for our algorithm Mini-batch Power Method with Momentum.
datais the data matrix where eacho row represents a single point,
xis the initial point,
betais the momentum parameter,
itersis the maximum number of iterations,
uis the true eigenvector that is used to compute the error for each iterate,
sis the mini-batch size and
seedis the random seed.
minibatch_svrg_m(data, x, beta, epoch, m, u,s, seed=1): This function is the implementation for our algorithm Variance Reduced Power Method with Momemtum. The argument
mis the epoch length and
epochis the number of epochs. The rest arguments are the same as
All the experimental results are generated from the Jupyter notebooks:
Mini-batches-no-acceleration.ipynb: This notebook shows the example that naively adding momentum in Oja’s algorithm does not obtain acceleration.
Mini-batches.ipynb: This notebook shows the acceleration for momentum stochastic power iteration with mini-batching and variance reduction.
Stability.ipynb: This notebook shows the instability of Lanczos method for finding multiple eigenvalues.
Best_Ball.ipynb: This notebook shows the performance of Best Heavy Ball method that auto-tune the momentum parameter in the power iteration.
Inhomogeneous.ipynb: This notebook show the better performance of Inhomogeneous Polynomial Recurrence than the constant momentum power method.