Essential papers on matrix decompositions

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

Maybe, you can find interesting

1. [Learning with Matrix Factorizations] PhD thesis by Nathan Srebro,
2. [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)

Answer 4

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.

Answer 5

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