5 ms·

Fast Randomized SVD (2014)

54 points by Cynddl 12y ago

Cynddl 12y ago
Posted six months ago on https://news.ycombinator.com/item?id=8525237 https://news.ycombinator.com/item?id=8525237. > We will soon release the implementations for these algorithms described. I would like to see them now.
- hyperbovine 12y ago
  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...
- ajtulloch 12y ago
  See https://github.com/facebook/fbpca https://github.com/facebook/fbpca
  - Cynddl 12y ago
    Thanks!
inglor 12y ago
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,
- alphaBetaGamma 12y ago
  How does compressed sensing work if you don't know the base in which the signal is sparse beforehand?
  - inglor 12y ago
    Start at slide 44 http://www.cs.huji.ac.il/~shais/Lectures2014/lecture11.pdf http://www.cs.huji.ac.il/~shais/Lectures2014/lecture11.pdf
- beagle3 12y ago
  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.
rwitten 12y ago
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#page-1 http://link.springer.com/article/10.1007%2Fs00453-014-9891-7... http://statweb.stanford.edu/~candes/papers/RandomizedNLA.pdf http://statweb.stanford.edu/~candes/papers/RandomizedNLA.pdf

54 points by Cynddl 12y ago

Posted six months ago on https://news.ycombinator.com/item?id=8525237 https://news.ycombinator.com/item?id=8525237. > We will soon release the implementations for these algorithms described. I would like to see them now.

hyperbovine 12y ago
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...
ajtulloch 12y ago
See https://github.com/facebook/fbpca https://github.com/facebook/fbpca
- Cynddl 12y ago
  Thanks!

inglor 12y ago

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,

alphaBetaGamma 12y ago
How does compressed sensing work if you don't know the base in which the signal is sparse beforehand?
- inglor 12y ago
  Start at slide 44 http://www.cs.huji.ac.il/~shais/Lectures2014/lecture11.pdf http://www.cs.huji.ac.il/~shais/Lectures2014/lecture11.pdf
beagle3 12y ago
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.

rwitten 12y ago

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#page-1 http://link.springer.com/article/10.1007%2Fs00453-014-9891-7... http://statweb.stanford.edu/~candes/papers/RandomizedNLA.pdf http://statweb.stanford.edu/~candes/papers/RandomizedNLA.pdf