Essential papers on matrix decompositions I recently read Skillicorn's book on matrix decompositions, and was a bit disappointed, as it was targeted to an undergraduate audience. I would like to compile (for myself and others) a short bibliography of essential papers (surveys, but also breakthrough papers) on matrix decompositions. What I have in mind primarily is something on SVD/PCA (and robust/sparse variants), and NNMF, since those are by far the most used. Do you all have any recommendation/suggestion? I am holding off mine not to bias the answers. I would ask to limit each answer to 2-3 papers.
P.S.: I refer to these two decompositions as the most used in data analysis. Of course QR, Cholesky, LU and polar are very important in numerical analysis. That is not the focus of my question though.
 A: For NNMF, Lee and Seung describe an iterative algorithm which is very simple to implement. Actually they give two similar algorithms, one for minimizing Frobenius norm of residual, the other for minimizing Kullback-Leibler Divergence of the approximation and original matrix.


*

*Daniel Lee, H. Sebastian Seung, Algorithms for Non-negative Matrix Factorization, Advances in Neural Information Processing Systems 13: Proceedings of the 2000 Conference. MIT Press. pp. 556–562.

A: Maybe, you can find interesting 


*

*[Learning with Matrix Factorizations] PhD thesis by Nathan Srebro,

*[Investigation of Various Matrix Factorization Methods for Large Recommender Systems], Gábor Takács et.al. and almost the same technique described here
The last two links show how sparse matrix factorizations are used in Collaborative Filtering. However, I believe that SGD-like factorization algorithms can be useful somewhere else (at least they are extremely easy to code)
A: Witten, Tibshirani - Penalized matrix decomposition
http://www.biostat.washington.edu/~dwitten/Papers/pmd.pdf
http://cran.r-project.org/web/packages/PMA/index.html
Martinsson, Rokhlin, Szlam, Tygert - Randomized SVD
http://cims.nyu.edu/~tygert/software.html
http://cims.nyu.edu/~tygert/blanczos.pdf
A: At this year's NIPS there was a short paper on distributed, very large-scale SVD that works in a single pass over a streaming input matrix.
The paper's more implementation-oriented but puts things into perspective with real wall-clock times and all. The table near the beginning is a good survey too.
A: How do you know that SVD and NMF are by far the most used matrix decompositions rather than LU, Cholesky and QR? My personal favourite 'breakthrough' would have to be the guaranteed rank-revealing QR algorithm,


*

*Chan, Tony F. "Rank revealing QR factorizations". Linear Algebra and its Applications Volumes 88-89, April 1987, Pages 67-82. DOI:10.1016/0024-3795(87)90103-0
... a development of the earlier idea of QR with column-pivoting:


*

*Businger, Peter; Golub, Gene H. (1965). Linear least squares solutions by Householder transformations. Numerische Mathematik Volume 7, Number 3, 269-276, DOI:10.1007/BF01436084
A (the?) classic textbook is:


*

*Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.


(i know you didn't ask for textbooks but i can't resist)
Edit:
A bit more googling finds a paper whose abstract suggests we could be slightly at cross porpoises. My above text was coming from a 'numerical linear algebra' (NLA) perspective; possibly you're concerned more with an 'applied statistics / psychometrics' (AS/P) perspective? Could you perhaps clarify?


*

*Lawrence Hubert, Jacqueline Meulman and Willem Heiser. Two Purposes for Matrix Factorization: A Historical Appraisal. SIAM Review Vol. 42, No. 1 (Mar., 2000), pp. 68-82

