Fast Randomized SVD (2014)

research.facebook.com

54 points·Cynddl··9 comments

Posted six months ago on https://news.ycombinator.com/item?id=8525237.

> We will soon release the implementations for these algorithms described.

I would like to see them now.

I'm sure there are all sorts of implementation issues at Facebook Scale, but the algorithm as described is about 20 lines of (instructive) numpy code...

See https://github.com/facebook/fbpca

Thanks!

If you're interested in lower bounds or tighter upper bounds, you can find the latest here:

http://link.springer.com/article/10.1007%2Fs00453-014-9891-7... http://statweb.stanford.edu/~candes/papers/RandomizedNLA.pdf

Why aren't they just using compressed sensing instead of PCA in the first place? PCA is good because it guarantees perfect recovery wen the set of examples is contained in an n dimentional subspace. Compressed sensing guarantees recovery whenever the set of examples is sparse in some basis - it sounds like a much better fit.

Not to mention random projections which are even faster (even proved by the Johnson-Lindenstrauss lemma) usually do well,

How does compressed sensing work if you don't know the base in which the signal is sparse beforehand?

Start at slide 44 http://www.cs.huji.ac.il/~shais/Lectures2014/lecture11.pdf

Maybe I misunderstand, but I think that's what they're doing, even if they don't use that terminology; I don't have the time to read the paper and code and detail right now, but from a 5-second glance that's an RP method.

They multiply a given matrix by a random matrix, do computations on the result (apparently some power method that efficiently floats bigger eigenvalues in the small base), and project back to the original space.

Reply on news.ycombinator.com