¿Qué algoritmos rápidos existen para calcular SVD truncada?

Posiblemente fuera de tema aquí, pero ya existen varias ( una , dos ) preguntas relacionadas.

Escudriñar la literatura (o una búsqueda en Google de Algoritmos SVD truncados) muestra muchos documentos que usan SVD truncados de varias maneras y afirman (frustrantemente, a menudo sin citas) que existen algoritmos rápidos para calcularlo, pero nadie parece estar apuntando a cuáles son esos algoritmos.

Lo único que puedo encontrar es un algoritmo aleatorio único , utilizado en la biblioteca redSVD .

Lo que me gustaría ver es un conjunto de algoritmos exactos e inexactos, adecuados para comprender cómo funcionan los sistemas (¡pero no necesariamente para implementarlos, por supuesto!).

¿Alguien tiene una buena referencia para este tipo de cosas?

En términos muy generales, existen dos enfoques para calcular el valor propio o las descomposiciones de valores singulares. Un enfoque es diagonalizar la matriz y esto esencialmente produce la descomposición del valor propio / valor singular (todo el espectro del valor propio) al mismo tiempo, vea una descripción general aquí: ¿Cuáles son los algoritmos eficientes para calcular la descomposición del valor singular (SVD)? La alternativa es utilizar un algoritmo iterativo que produzca uno (o varios) vectores propios a la vez. Las iteraciones se pueden detener después de que se haya calculado el número deseado de vectores propios.

No creo que haya algoritmos iterativos específicamente para SVD. Esto es porque se puede calcular SVD de un matriz B haciendo una eigendecomposition de un cuadrado simétrico ( n + m ) × ( n + m ) de la matriz A = ( 0 B B ⊤ 0 ) . Por lo tanto, en lugar de preguntar qué algoritmos calculan SVD truncada, debería preguntarse qué algoritmos iterativos calculan la descomposición propia: algoritmo para SVD truncada ≈ algoritmo iterativo para descomposición propia $n\times m$$\mathbf B$$(n+m)\times(n+m)$

El algoritmo iterativo más simple se llama iteración de potencia y de hecho es muy simple:

1. $\mathbf x$
2. $\mathbf x \gets \mathbf A\mathbf x$
3. $\mathbf x \gets \mathbf x / \|\mathbf x\|$
4. Ir al paso 2 a menos que converja.

Todos los algoritmos más complejos se basan en última instancia en la idea de iteración de potencia, pero se vuelven bastante sofisticados. Las matemáticas necesarias están dadas por los subespacios de Krylov . Los algoritmos son la iteración de Arnoldi (para matrices cuadradas no simétricas), la iteración de Lanczos (para matrices simétricas cuadradas) y variaciones de los mismos, como por ejemplo, "método de Lanczos reiniciado implícitamente" y otras cosas.

Puede encontrar esto descrito en, por ejemplo, los siguientes libros de texto:

1. Golub & Van Loan, cálculos matriciales
2. Trefethen & Bau, Álgebra Lineal Numérica
3. Demmel, álgebra lineal numérica aplicada
4. Saad, métodos numéricos para grandes problemas de valores propios

Todos los lenguajes de programación y paquetes estadísticos razonables (Matlab, R, Python numpy, lo que sea) usan las mismas bibliotecas Fortran para realizar descomposiciones de valores propios / singulares. Estos son LAPACK y ARPACK . ARPACK significa ARnoldi PACKage, y se trata de iteraciones de Arnoldi / Lanczos. Por ejemplo, en Matlab hay dos funciones para SVD: svdrealiza una descomposición completa a través de LAPACK, y svdscalcula un número dado de vectores singulares a través de ARPACK y en realidad es solo un contenedor para una eigsllamada en la matriz "cuadrada".

Actualizar

$\mathbf B$$\mathbf A$$\mathbf A$$\mathbf B$$\mathbf A$

También hay una biblioteca Fortran para estos métodos, se llama PROPACK :

El paquete de software PROPACK contiene un conjunto de funciones para calcular la descomposición de valores singulares de matrices grandes y dispersas o estructuradas. Las rutinas SVD se basan en el algoritmo de bidiagonalización de Lanczos con reortogonalización parcial (BPRO).

Sin embargo, PROPACK parece ser mucho menos estándar que ARPACK y no se admite de forma nativa en los lenguajes de programación estándar. Está escrito por Rasmus Larsen, que tiene una gran bidiagonalización de Lanczos en papel de 1998 de 90 páginas de largo con reortogonalización parcial con lo que parece una buena visión general. Gracias a @MichaelGrant a través de este hilo de Computational Science SE .

Entre los documentos más recientes, el más popular parece ser Baglama & Reichel, 2005, Augmented reinició implícitamente los métodos de bidiagonalización de Lanczos , lo que probablemente se encuentre en el estado del arte. Gracias a @Dougal por dar este enlace en los comentarios.

Actualización 2

De hecho, hay un enfoque completamente diferente descrito en detalle en el documento general que usted mismo citó: Halko et al. 2009, Hallazgo de estructura con aleatoriedad: algoritmos probabilísticos para construir descomposiciones matriciales aproximadas . No sé lo suficiente para comentar.

Acabo de tropezar con el hilo a través de Google SVD rápidos, así que estoy tratando de resolver las cosas por mí mismo, pero tal vez deberías buscar una aproximación cruzada adaptativa (ACA).

Realmente no sé cómo es el problema o lo que necesita, pero si su matriz $M$ se calcula a partir de funciones suaves, y solo necesita una representación separada aproximada $M=\sum_{i=0}^k U_i\cdot V^T_i$ y no es realmente una SVD "adecuada", el algoritmo ACA tiene (casi) una complejidad computacional lineal ($N\times N$ matriz entonces es casi $O(N)$) Entonces es realmente rápido; desafortunadamente muchas personas usan la palabra "rápido" a la ligera.

Nuevamente, depende de su problema si eso funciona. En muchos casos que encuentro personalmente, el ACA es una herramienta numérica muy útil.

Nota: quería escribir esto como un comentario, pero debido a que acabo de crear esta cuenta, no tengo suficiente reputación para comentar ... Pero la publicación funciona.

Aquí hay una técnica que he usado con éxito en el pasado para calcular un SVD truncado (en el conjunto de datos de Netflix). Está tomado de este documento . En una configuración de filtrado colaborativo, debo tener en cuenta que faltan la mayoría de los valores y el punto es predecirlos , por lo que para usar SVD truncado para resolver dicho problema, debe usar una técnica que funcione bajo esa condición. Una breve descripción:

1. Antes de hacer nada, ajuste un modelo simple (p. Ej., Media global + valores constantes de columna y fila), y solo una vez que lo haya hecho, debe pasar a usar SVD truncado para ajustar los residuos.
2. Inicialice un vector aleatorio de longitud k (donde ese es el rango al que está truncando) en cada fila y columna (para cada película y usuario en el caso de Netflix).
3. Mantenga fijos los vectores de fila y actualice los vectores de columna para minimizar el error de las entradas conocidas en la matriz. El procedimiento se da en código matlab en el documento.
4. Mantenga fijos los vectores de columna y actualice los vectores de fila de forma análoga.
5. Repita 3 y 4 hasta que converja o obtenga resultados suficientemente buenos.