¿Cuál es el estado actual de la técnica con respecto a los algoritmos para la descomposición de valores singulares?

12

Estoy trabajando en una biblioteca matricial de solo encabezado para proporcionar un grado razonable de capacidad de álgebra lineal en un paquete lo más simple posible, y estoy tratando de estudiar cuál es el estado actual de la técnica: calcular la SVD de un matriz compleja

Estoy haciendo una descomposición de dos fases, bidiagonalización seguida de cálculo de valor singular. En este momento estoy usando el método de jefe de familia para la bidiagonalización (creo que LAPACK también lo usa), y creo que es tan bueno como lo es actualmente (a menos que alguien sepa de un algoritmo para ello..). O(N2)

El cálculo del valor singular es el siguiente en mi lista, y estoy un poco fuera de lugar en cuanto a cuáles son los algoritmos comunes para hacer esto. Leí aquí que la investigación se dirigía hacia un método de iteración inversa que garantiza la ortogonalidad con la complejidad . Me interesaría saber sobre ese u otros avances.O(N)

linear-algebra matrix svd gct
fuente
¿hay algún documento para tu lib de matriz de encabezado (aparte del .h)? También agregue la etiqueta "svd".
denis

Respuestas:

7

Los "algoritmos aleatorizados" se han vuelto muy populares recientemente para svds parciales. Aquí se puede descargar una implementación de solo encabezado: http://code.google.com/p/redsvd/

Puede encontrar una revisión de los métodos actuales aquí: http://arxiv.org/abs/0909.4061

Para svds completos, no estoy seguro de si puedes hacerlo mejor que Householder.

dranxo
fuente
Eso suena muy interesante, tendré que echar un vistazo a esa encuesta, ¡gracias!
gct
OP está interesado en algoritmos para matrices densas. No creo que los algoritmos aleatorios sean competitivos en ese entorno, si es que funcionan.
Federico Poloni
Esta publicación indica que los métodos aleatorios funcionan bien en matrices densas research.facebook.com/blog/294071574113354/fast-randomized-svd
dranxo
@dranxo No hay comparaciones de precisión en absoluto en esa publicación, y los resultados de tiempo no parecen muy meticulosos. Además, los algoritmos aleatorios se basan en la proyección + solución exacta de un problema a pequeña escala. Esto significa que OP necesitaría una implementación de un "método estándar" para el problema de pequeña escala resultante de todos modos.
Federico Poloni
Lo suficientemente justo. Aunque estoy un poco confundido por qué deberíamos pensar que estos métodos solo funcionan en matrices dispersas. Directamente el resumen del artículo de Joel Tropp: "Para una matriz de entrada densa, los algoritmos aleatorios requieren operaciones de punto flotante (flops) O (mn log (k)) en contraste con O (mnk) para algoritmos clásicos". arxiv.org/pdf/0909.4061v2.pdf
dranxo
4

Leí aquí que la investigación se dirigía hacia un método de iteración inversa que garantiza la ortogonalidad con la complejidad . Me interesaría saber sobre ese u otros avances.O(N)

(Solo quería hacer algunos comentarios, ya que no tengo tiempo para escribir detalles, pero se hizo bastante grande para el cuadro de comentarios).

Creo que sería el algoritmo MRRR (múltiples representaciones relativamente robustas) de Dhillon y Parlett. Esto se basa en el trabajo anterior de Fernando, que a su vez se inspiró en un problema planteado por Jim Wilkinson en su monumental libro sobre problemas de valores propios. La parte de "iteración inversa" para obtener vectores singulares se basa en el concepto de "factorizaciones retorcidas" de Fernando , que hace uso de las matrices de factorización en y descomposiciones .U D U ⊤LDL⊤UDU⊤

La porción de "valor singular" del algoritmo, por otro lado, proviene del algoritmo de diferencia de cociente diferencial (desplazado) (dqd (s)) , que es la culminación del trabajo previo de Fernando, Parlett , Demmel y Kahan (con inspiración de Heinz Rutishauser).

Como sabrán, los métodos SVD generalmente proceden primero con una descomposición bidiagonal antes de obtener los valores singulares de la matriz bidiagonal. Lamentablemente, no estoy demasiado actualizado sobre el mejor método actual para la descomposición bidiagonal frontal; La última vez que verifiqué, el método habitual es comenzar con la descomposición QR con el pivote de la columna y luego aplicar las transformaciones ortogonales de manera apropiada al factor triangular para obtener finalmente la descomposición bidiagonal.

Entiendo que he sido escaso con los detalles; Intentaré desarrollar esta respuesta una vez que tenga acceso a mi biblioteca ...

JM
fuente
Forma de matriz a bi-diagonal, haga una columna y luego una fila, repita hacia abajo la diagonal: use givens o householder para poner a cero la columna en diagonal, luego haga lo mismo para la fila a la super-diagonal.
Adam W
Ignora mi comentario anterior, estaba pensando en una forma tri-diagonal. Lo siento. La bi-diagonalización no es trivial en una similitud (en realidad revelaría los valores propios), pero su referencia no está haciendo una similitud, está haciendo otra cosa; izquierda y derecha se multiplican con diferentes matrices ortogonales. es bi-diagonal con y , lo que se puede hacer como dice primero con QR, pero no se describe tan fácilmente en un comentario. Me interesaría si profundiza la respuesta (pero también podría averiguarlo ya que mis estudios se dirigen en esta dirección en este momento). U U ⊤ = I V V ⊤ = IUAVUU⊤=IVV⊤=I
Adam W