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

Question

Posiblemente se salga del tema, pero existen varios ( un , dos ).

Hurgando en la literatura (o buscando en Google Algoritmos SVD Truncados) aparecen muchos trabajos que utilice SVD truncadas de varias maneras, y reclamar (frustrantemente, a menudo sin citar) que existen algoritmos rápidos para calcularlo, pero nadie parece señalar cuáles son esos algoritmos.

Lo único que encuentro es un algoritmo aleatorio utilizado en el 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 ponerlos en práctica, por supuesto).

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

Answer 1

A grandes rasgos, existen dos métodos para calcular los valores propios o las descomposiciones de valores singulares. Un enfoque consiste en diagonalizar la matriz y esto produce esencialmente toda la descomposición de valores propios / valores singulares (todo el espectro de valores propios) al mismo tiempo: ¿Cuáles son los algoritmos eficaces para calcular la descomposición en valores singulares (SVD)? La alternativa es utilizar un algoritmo iterativo que produzca uno (o varios) vectores propios cada vez. Las iteraciones pueden detenerse una vez calculado el número deseado de vectores propios.

No creo que existan algoritmos iterativos específicos para SVD. Esto se debe a que uno puede calcular la SVD de un $n\times m$ matriz $\mathbf B$ haciendo una eigendecomposición de un cuadrado simétrico $(n+m)\times(n+m)$ matriz $$\mathbf A=\left(\begin{array}{cc}0 & \mathbf B\\\mathbf B^\top & 0\end{array}\right).$$ Por lo tanto, en lugar de preguntar qué algoritmos calculan la SVD truncada, deberías preguntar qué algoritmos iterativos calculan la eigendecomposición: $$\text{algorithm for truncated SVD} \approx \text{iterative algorithm for eigendecomposition}.$$

El algoritmo iterativo más sencillo se denomina iteración de potencia y es muy sencillo:

1. Inicializar aleatorio $\mathbf x$ .
2. Actualización $\mathbf x \gets \mathbf A\mathbf x$ .
3. Normalizar $\mathbf x \gets \mathbf x / \|\mathbf x\|$ .
4. Pasar al paso nº 2 a menos que haya convergencia.

Todos los algoritmos más complejos se basan en última instancia en la idea de la iteración de potencia, pero se vuelven bastante sofisticados. La matemática necesaria viene dada por Subespacios de Krylov . Los algoritmos son Iteración Arnoldi (para matrices cuadradas no simétricas), Iteración de Lanczos (para matrices simétricas cuadradas), y sus variaciones como, por ejemplo, "método de Lanczos reiniciado implícitamente" y otros.

Esto se describe, por ejemplo, en 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, etc.) utilizan las mismas bibliotecas Fortran para realizar descomposiciones de valores propios/singulares. Éstas son LAPACK y ARPACK . ARPACK son las siglas de ARnoldi PACKage, y se trata de iteraciones Arnoldi/Lanczos. Por ejemplo, en Matlab hay dos funciones para SVD: svd realiza la descomposición completa mediante LAPACK, y svds calcula un número determinado de vectores singulares a través de ARPACK y en realidad no es más que una envoltura para un eigs en la matriz "cuadrada".

Actualización

Resulta que hay variantes del algoritmo de Lanczos que están específicamente adaptadas para realizar la SVD de una matriz rectangular $\mathbf B$ sin construir explícitamente una matriz cuadrada $\mathbf A$ primero. El término central aquí es Bidiagonalización de Lanczos ; según tengo entendido, se trata esencialmente de un truco para realizar todos los pasos de las iteraciones de Lanczos sobre $\mathbf A$ directamente en $\mathbf B$ sin llegar a construir $\mathbf A$ y ahorrar así espacio y tiempo.

También existe 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 del valor singular de matrices grandes y dispersas o estructuradas. Las rutinas de 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 está soportado de forma nativa en los lenguajes de programación estándar. Está escrito por Rasmus Larsen, que tiene un extenso artículo de 90 páginas publicado en 1998. Bidiagonalización de Lanczos con reortogonalización parcial con lo que parece una buena visión de conjunto. Gracias a @MichaelGrant vía este hilo sobre Ciencias Computacionales SE .

Entre los trabajos más recientes, el más popular parece ser Baglama & Reichel, 2005, Métodos de bidiagonalización de Lanczos aumentados y reiniciados implícitamente que probablemente esté en la vanguardia de la tecnología. Gracias a @Dougal para dar este enlace en los comentarios.

Actualización 2

De hecho, existe un enfoque totalmente diferente descrito en detalle en el documento de síntesis que usted mismo ha citado: Halko et al. 2009, Encontrar estructura con aleatoriedad: Algoritmos probabilísticos para construir descomposiciones matriciales aproximadas . No sé lo suficiente como para hacer comentarios.

Answer 2

Acabo de tropezar con el hilo a través de google rápido SVDs, así que estoy tratando de entender las cosas a mí mismo, pero tal vez usted debe buscar en 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 sólo se necesita una representación separada aproximada $M=\sum_{i=0}^k U_i\cdot V^T_i$ y no un SVD "propiamente dicho", el algoritmo ACA tiene una complejidad computacional (casi) lineal ( $N\times N$ entonces es casi $O(N)$ ). Así que es realmente rápido; por desgracia, mucha gente utiliza la palabra "rápido" a la ligera.

De nuevo, depende de tu problema si eso funciona. En muchos casos con los que me encuentro personalmente, el ACA es una herramienta numérica muy útil.

Nota: Quería escribir esto como comentario, pero como acabo de crear esta cuenta no tengo suficiente reputación para los comentarios... Pero publicar funciona.

Answer 3

He aquí una técnica que he utilizado con éxito en el pasado para calcular un SVD truncado (en el conjunto de datos de Netflix). Está tomada de este documento . En un entorno de filtrado colaborativo, debo señalar que la mayoría de los valores faltan y de lo que se trata es de predecirlos por lo que para utilizar la SVD truncada para resolver un problema de este tipo, hay que utilizar una técnica que funcione en esas condiciones. Una breve descripción:

1. Antes de hacer nada, ajuste un modelo sencillo (por ejemplo, media global + valores constantes de columna y fila), y sólo cuando lo haya hecho deberá pasar a utilizar el SVD truncado para ajustar los residuos.
2. Inicializa un vector aleatorio de longitud k (donde ese es el rango al que estás truncando) a cada fila y columna (a cada película y usuario en el caso de Netflix).
3. Mantener fijos los vectores fila y actualizar los vectores columna para minimizar el error con respecto al conocido entradas de la matriz. El procedimiento se presenta en código matlab en el documento.
4. Mantenga fijos los vectores columna y actualice los vectores fila de forma análoga.
5. Repita los pasos 3 y 4 hasta que converja o hasta que obtenga resultados suficientemente buenos.