Documentos esenciales sobre descomposiciones matriciales

18

Hace poco leí el libro de Skillicorn sobre descomposiciones de matrices, y me decepcionó un poco, ya que estaba dirigido a un público universitario. Me gustaría compilar (para mí y para otros) una breve bibliografía de documentos esenciales (encuestas, pero también documentos innovadores) sobre descomposiciones de matrices. Lo que tengo en mente principalmente es algo en SVD / PCA (y variantes robustas / dispersas) y NNMF, ya que esas son las más utilizadas. ¿Todos ustedes tienen alguna recomendación / sugerencia? Estoy retrasando la mía para no sesgar las respuestas. Yo pediría limitar cada respuesta a 2-3 documentos.

PD: Me refiero a estas dos descomposiciones como las más utilizadas en el análisis de datos . Por supuesto, QR, Cholesky, LU y polar son muy importantes en el análisis numérico. Sin embargo, ese no es el enfoque de mi pregunta.

matrix-decomposition svd numerics gappy
fuente

Respuestas:

16

¿Cómo sabe que SVD y NMF son, con mucho, las descomposiciones de matriz más utilizadas en lugar de LU, Cholesky y QR? Mi 'avance' favorito personal tendría que ser el algoritmo QR de rango revelador garantizado,

  • Chan, Tony F. "Rango revelando factorizaciones QR". Álgebra lineal y sus volúmenes de aplicaciones 88-89, abril de 1987, páginas 67-82. DOI: 10.1016 / 0024-3795 (87) 90103-0

... un desarrollo de la idea anterior de QR con pivote de columna:

  • Businger, Peter; Golub, Gene H. (1965). Soluciones lineales de mínimos cuadrados por transformaciones de Householder. Numerische Mathematik Volumen 7, Número 3, 269-276, DOI: 10.1007 / BF01436084

Un libro de texto clásico ( ¿ el ?) Es:

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

(Sé que no pediste libros de texto pero no puedo resistirme)

Editar: un poco más de búsqueda en Google encuentra un artículo cuyo resumen sugiere que podríamos estar ligeramente en marsopas cruzadas. Mi texto anterior provenía de una perspectiva de 'álgebra lineal numérica' (NLA); ¿posiblemente le preocupa más una perspectiva de 'estadística aplicada / psicometría' (AS / P)? ¿Podrías quizás aclarar?

onestop
fuente
2
Yo mismo diría "el" libro de texto, con los Algoritmos Matrix de Stewart ( ambas partes ) en segundo lugar. Yo mismo daría una lista de los trabajos pioneros, pero el OP realmente debería explicar si quiere el punto de vista numérico o el punto de vista de las estadísticas (puedo ayudar con el primero, pero no tanto con el último).
JM no es un estadístico
1
+1 para Golub y Van Loan. Y sí, el artículo definitivo es apropiado.
shabbychef
2
Edité mi pregunta para aclarar que me estoy centrando en la parte de estadísticas. Estoy de acuerdo con todos en que Golub y Van Loan son la referencia estándar para las descomposiciones de matrices. Pero está omitiendo el tema de la descomposición a gran escala a través de proyecciones aleatorias. Una encuesta que pondría en mi lista es "Encontrar estructura con aleatoriedad: algoritmos estocásticos para construir descomposiciones de matriz aproximadas" por Halko et al.
alegre
4

Para NNMF, Lee y Seung describen un algoritmo iterativo que es muy simple de implementar. En realidad, ofrecen dos algoritmos similares, uno para minimizar la norma residual de Frobenius y el otro para minimizar la divergencia Kullback-Leibler de la aproximación y la matriz original.

shabbychef
fuente
3

Tal vez, puedes encontrar interesante

  1. [Aprendizaje con factorizaciones matriciales] Tesis doctoral de Nathan Srebro,
  2. [Investigación de varios métodos de factorización matricial para grandes sistemas de recomendación] , Gábor Takács et.al. y casi la misma técnica descrita aquí

Los dos últimos enlaces muestran cómo se utilizan factorizaciones de matriz dispersas en el filtrado colaborativo. Sin embargo, creo que los algoritmos de factorización tipo SGD pueden ser útiles en otro lugar (al menos son extremadamente fáciles de codificar)

revs bijey
fuente
2

Witten, Tibshirani - Descomposición 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 aleatorizado

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

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

pslice
fuente
55
Gracias. Conozco ambos papeles. No soy un gran admirador de Witten [no Whitten] et al., Ya que creo que hay documentos más importantes sobre descomposiciones dispersas. En SVD aleatorizado, me gusta especialmente el artículo de revisión "Encontrar estructura con aleatoriedad: algoritmos estocásticos para construir descomposiciones matriciales aproximadas" ( arxiv.org/abs/0909.4061 ) también en coautoría de Martinsson.
alegre
estoy de acuerdo. Solo estaba sacando 2 papeles que nadie había mencionado.
pslice
2

En el NIPS de este año hubo un breve documento sobre SVD distribuido a gran escala que funciona en un solo paso sobre una matriz de entrada de transmisión .

El documento está más orientado a la implementación, pero pone las cosas en perspectiva con tiempos reales de reloj de pared y todo. La tabla cerca del comienzo también es una buena encuesta.

pisk
fuente
¿Qué significa NIPS?
onestop
Enlace @onestop agregado. NIPS = Sistemas de procesamiento de información neuronal. Es una comunidad (no un sistema :)). Pero Pisk está hablando de la conferencia NIPS 2010.
robin girard