[rajasinghe]

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.

[apathy]

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.

[sytelus]

Is this a more formal treatment for algorithm that Simon Funk gave?

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

[jey]

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.

[dang]

Great comment! We put 2013 in the title above.