News for hackers. Stuff that matters.
Re:Lecture Notes on Randomized Linear Algebra (2013) by rajasinghe on Tuesday January 24, 2017 @03:17PM (#13475053)
This stuff is incredibly useful when dealing with large matrices. The idea is that an n-by-n matrix often doesn't contain n^2 pieces of independent information, but can be written a product of matrices of size at most n-by-r (for r << n). A famous example of this is the Netflix recommendation matrix. In this case, you can often avoid O(n^2) complexity by only dealing with such low-rank approximations.

It should be noted that this overview dates from 2013 and that a lot of new results have appeared since then. The author gives some good references in the abstract.

Re:Lecture Notes on Randomized Linear Algebra (2013) by apathy on Tuesday January 24, 2017 @04:46PM (#13475876)
Sparse x low-rank: if you collected every cell in the matrix, you paid too much for your sensor :-)

Emmanuel Candes' lectures on compressed sensing changed my life.

Re:Lecture Notes on Randomized Linear Algebra (2013) by sytelus on Tuesday January 24, 2017 @04:49PM (#13475922)
Is this a more formal treatment for algorithm that Simon Funk gave?

http://sifter.org/~simon/journal/20061211.html

Re:Lecture Notes on Randomized Linear Algebra (2013) by jey on Tuesday January 24, 2017 @05:08PM (#13476143)
That's more related to 'stochastic gradient descent' for 'matrix completion'. The key difference is that Simon Funk's algorithm doesn't treat missing entries as a zero, whereas using linear algebra based techniques on the observed data matrix (formed by putting zeros for unobserved entries) would try to predict the missing entries as zero exactly.

Also related is the 'alternating least squares' algorithm.

Re:Lecture Notes on Randomized Linear Algebra (2013) by dang on Wednesday January 25, 2017 @10:11AM (#13481969)
Great comment! We put 2013 in the title above.