18

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.

gappy
  • 5,390
  • 3
  • 28
  • 50

5 Answers5

17

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?

onestop
  • 16,816
  • 2
  • 53
  • 83
  • 2
    I would say "the" textbook myself, with Stewart's *Matrix Algorithms* ( [both](http://books.google.com/books?id=XHOQ_HU-85IC) [parts](http://books.google.com/books?id=FtC9rHW7ORMC)) a close second. I would give a list of the pioneering papers myself, but the OP really should explain if he wants the numerics viewpoint or the stats viewpoint (I can help with the former, but not so much the latter). – J. M. is not a statistician Nov 06 '10 at 09:23
  • 1
    +1 for Golub and Van Loan. And, yes, the definitive article is appropriate. – shabbychef Nov 06 '10 at 19:42
  • 2
    I edited my question to clarify that I am focusing on the statistics part. I agree with everyone that Golub and Van Loan is the standard reference for matrix decompositions. But it's omitting the topic of very large scale decomposition through random projections. A survey paper I would put in my list is "Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions" by Halko et al. – gappy Nov 06 '10 at 20:16
4

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.

shabbychef
  • 10,388
  • 7
  • 50
  • 93
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)

bijey
  • 405
  • 4
  • 10
2

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

pslice
  • 291
  • 3
  • 7
  • 5
    Thanks. I know both papers. I am not a great fan of Witten [not Whitten] et al., as i think there are more important papers on sparse decompositions. On randomized SVD, I especially like the review paper "Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions" (http://arxiv.org/abs/0909.4061) also coauthored by Martinsson. – gappy Nov 22 '10 at 17:17
  • i agree. i was just putting out there 2 papers no one had mentioned. – pslice Nov 22 '10 at 19:19
2

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.

robin girard
  • 6,335
  • 6
  • 46
  • 60