What is the fastest way to calculate the leading singular value of a very large matrix (10mln x 100k)?

Question

I only know of the following power iteration. But it needs to create a huge matrix A'*A when both of rows and columns are pretty large. And A is a dense matrix as well. Is there any alternative to power iteration method below? I have heard of krylov subspace method, but I am not familiar with it. In anycase I am looking for any faster method than the one mentioned below:

B = A'*A; % or B = A*A' if it is smaller
x = B(:,1); % example of starting point, x will have the largest eigenvector 
x = x/norm(x); 
for i = 1:200 
  y = B*x; 
  y = y/norm(y);
  % norm(x - y); % <- residual, you can try to use it to stop iteration
  x = y; 
end; 
n3 = sqrt(mean(B*x./x)) % translate eigenvalue of B to singular value of A

Answer 1

There are two approaches that require only small number of multiplications of vectors by $A$ or $A'$, and so have computational complexity $O(MNk)$ for small fixed $k$. Their performance is empirically similar, too.

• Lanczos-type algorithms:
• Stochastic SVD

You absolutely do not want to implement a Lanczos-type algorithm yourself -- the rounding error is subtle and quick to anger -- but implementations are available in many packages.

You actually can implement Stochastic SVD yourself; there's a very short Matlab implementation at that link.