Artigos essenciais sobre decomposições matriciais

18

Recentemente, li o livro de Skillicorn sobre decomposições matriciais e fiquei um pouco decepcionado, pois era direcionado a um público de graduação. Gostaria de compilar (para mim e para os outros) uma breve bibliografia de artigos essenciais (pesquisas, mas também artigos inovadores) sobre decomposições matriciais. O que eu tenho em mente principalmente é algo sobre SVD / PCA (e variantes robustas / esparsas) e NNMF, já que essas são de longe as mais usadas. Vocês todos têm alguma recomendação / sugestão? Estou segurando o meu para não influenciar as respostas. Eu pediria para limitar cada resposta a 2-3 papéis.

PS: Refiro-me a essas duas decomposições como as mais usadas na análise de dados . É claro que QR, Cholesky, LU e polar são muito importantes na análise numérica. Esse não é o foco da minha pergunta.

matrix-decomposition svd numerics gappy
fonte

Respostas:

16

Como você sabe que SVD e NMF são de longe as decomposições matriciais mais usadas , em vez de LU, Cholesky e QR? Meu "avanço" favorito pessoal teria que ser o algoritmo QR com revelação de classificação garantida,

  • Chan, Tony F. "Rank revelando fatorações QR". Álgebra linear e seus aplicativos Volumes 88-89, abril de 1987, páginas 67-82. DOI: 10.1016 / 0024-3795 (87) 90103-0

... um desenvolvimento da ideia anterior do QR com rotação de colunas:

  • Businger, Peter; Golub, Gene H. (1965). Soluções de mínimos quadrados lineares por transformações de Household. Numerische Mathematik Volume 7, Número 3, 269-276, DOI: 10.1007 / BF01436084

Um livro clássico ( o ?) Clássico é:

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

(eu sei que você não pediu livros didáticos, mas não resisto)

Edit: Um pouco mais pesquisador encontra um artigo cujo resumo sugere que poderíamos estar um pouco em botos cruzados. Meu texto acima vinha de uma perspectiva de 'álgebra linear numérica' (NLA); possivelmente você está mais preocupado com uma perspectiva de 'estatística aplicada / psicometria' (AS / P)? Você poderia talvez esclarecer?

topo
fonte
2
Eu mesmo diria "o" livro-texto, com os algoritmos de matriz de Stewart ( ambas as partes ) um segundo próximo. Eu mesmo daria uma lista dos artigos pioneiros, mas o OP realmente deveria explicar se ele quer o ponto de vista numérico ou o de estatísticas (eu posso ajudar no primeiro, mas não tanto no último).
JM não é estatístico
1
+1 para Golub e Van Loan. E, sim, o artigo definitivo é apropriado.
21810 shabbychef
2
Editei minha pergunta para esclarecer que estou focando na parte de estatísticas. Concordo com todos que Golub e Van Loan são a referência padrão para decomposições matriciais. Mas está omitindo o tópico de decomposição em grande escala através de projeções aleatórias. Um artigo de pesquisa que eu colocaria em minha lista é "Encontrando estrutura com aleatoriedade: algoritmos estocásticos para construir decomposições aproximadas de matriz" por Halko et al.
gappy
4

Para o NNMF, Lee e Seung descrevem um algoritmo iterativo que é muito simples de implementar. Na verdade, eles fornecem dois algoritmos semelhantes, um para minimizar a norma residual de Frobenius e outro para minimizar a divergência de Kullback-Leibler da aproximação e da matriz original.

shabbychef
fonte
3

Talvez você possa achar interessante

  1. [Aprendendo com fatorações matriciais] Tese de doutorado de Nathan Srebro,
  2. [Investigação de vários métodos de fatoração matricial para grandes sistemas de recomendação] , Gábor Takács et.al. e quase a mesma técnica descrita aqui

Os dois últimos links mostram como as fatorações matriciais esparsas são usadas na Filtragem Colaborativa. No entanto, acredito que algoritmos de fatoração do tipo SGD podem ser úteis em outro lugar (pelo menos, são extremamente fáceis de codificar)

bijey
fonte
2

Witten, Tibshirani - Decomposição matricial penalizada

http://www.biostat.washington.edu/~dwitten/Papers/pmd.pdf

http://cran.r-project.org/web/packages/PMA/index.html

Martinsson, Rokhlin, Szlam, Tygert - SVD randomizado

http://cims.nyu.edu/~tygert/software.html

http://cims.nyu.edu/~tygert/blanczos.pdf

pslice
fonte
5
Obrigado. Eu conheço os dois papéis. Não sou muito fã de Witten [não de Whitten] et al., Pois acho que existem trabalhos mais importantes sobre decomposições esparsas. No SVD randomizado, gosto especialmente do artigo de revisão "Encontrando estrutura com aleatoriedade: algoritmos estocásticos para a construção de decomposições aproximadas de matriz" ( arxiv.org/abs/0909.4061 ), também em co-autoria de Martinsson.
gappy
concordo. eu estava colocando dois documentos que ninguém havia mencionado.
Pslice
2

No NIPS deste ano, houve um pequeno artigo sobre SVD distribuído em escala muito grande que funciona em uma única passagem em uma matriz de entrada de streaming .

O artigo é mais orientado à implementação, mas coloca as coisas em perspectiva com o tempo real do relógio de parede e tudo. A tabela perto do início também é uma boa pesquisa.

pisk
fonte
NIPS de quê?
onestop
Link @onestop adicionado. NIPS = Sistemas de Processamento de Informação Neural. É uma comunidade (não um sistema :)). Mas pisk está falando sobre a conferência NIPS 2010.
robin Girard