Actualización de la descomposición SVD después de agregar una nueva fila a la matriz

Supongamos que tengo una matriz densa de tamaño , con descomposición SVD En puedo calcular la SVD de la siguiente manera: . $\textbf{A}$ $m \times n$

A = {U S V}^{⊤} .

$\mathbf{A}=\mathbf{USV}^\top.$ Rsvd(A)

Si se agrega una nueva fila a , ¿se puede calcular la nueva descomposición SVD basada en la anterior (es decir, utilizando , y ), sin volver a calcular SVD desde cero? $(m+1)$ $\mathbf A$ $\mathbf U$ $\mathbf S$ $\mathbf V$

algorithms svd linear-algebra matrix-decomposition numerics usuario1436187
fuente

Consulte la literatura de rank 1 updates. Las rápidas revisiones SVD en línea para sistemas de recomendación livianos de Brand son un primer artículo accesible. Desafortunadamente, no he visto algo para SVD ya implementado en R. Las actualizaciones de Cholesky existen ( updowndesde Matrix) gracias a CHOLMOD. La escasez de su matriz

realmente hará una diferencia en su solución final; ¿Asumes una matriz densa o escasa?

A

$A$

usεr11852 dice Reinstate Monic el

+1 a @ usεr11852. También tenga en cuenta que es mucho más fácil y más estándar actualizar QR y en algunas aplicaciones QR es suficiente y uno realmente no necesita SVD. Así que piense también en su aplicación.

ameba dice Reinstate Monica

Sí, la matriz es densa.

user1436187

'Elimine la literatura recomendada entonces y enfóquese en el procesamiento de imágenes. Preguntas similares con tours han sido publicadas en términos de "nuevas imágenes" en una base de datos. Por ejemplo, mi presentimiento es que alguien debe tener un algoritmo para actualizar las entradas de sus caras propias en línea. Estos tipos trabajan con representaciones matriciales densas.

usεr11852 dice Reinstate Monic el

Algunos hilos relacionados en otros sitios web de SE: scicomp.stackexchange.com/questions/2678 , scicomp.stackexchange.com/questions/19253 , mathoverflow.net/questions/143375 .

ameba dice Reinstate Monica

Sí, se puede actualizar una descomposición SVD después de agregar una nueva fila a la matriz existente.

En general, esta formulación del problema " agregar uno a " se conoce como actualizaciones de rango uno . El enlace MathOverflow proporcionado por @amoeba sobre " actualizaciones eficientes de rango dos de una descomposición de valores propios " es un gran primer paso si desea comenzar a profundizar en el asunto; El primer artículo proporciona una solución explícita a su pregunta específica. Solo para aclarar lo que significan el rango uno y el rango dos para que no se confunda, si su nueva es tal que: $A^*$

\begin{aligned} {UN}^{*} = UN - tu v^{T} \end{aligned}

$\begin{align} A^* = A - uv^T \end{align}$

Donde y son vectores, entonces se refiere a esto como una actualización de rango uno (o perturbación ). La base de esta actualización está dictada por la fórmula de Sherman-Morrison. . Si la perturbación es más de un rango, es decir. $u$ $v$

\begin{aligned} {UN}^{*} = UN - U V^{T} \end{aligned}

$\begin{align} A^* = A - UV^T \end{align}$

la fórmula Woodbury entra en juego. Si ve estas fórmulas, notará que hay mucha inversión inversa. No resuelve estos directamente. Como ya resolvió gran parte de sus subsistemas (es decir, ya tiene cierta descomposición calculada), los utiliza para obtener estimaciones más rápidas y / o más estables. (Es por eso que la gente todavía investiga este campo). He usado el libro " Estadísticas computacionales " de JE Gentle como referencia; Creo Chapt. 5 El álgebra lineal numérica lo configurará correctamente. (El súper clásico: " Álgebra matricial desde la perspectiva de un estadístico " de Harville desafortunadamente no toca en absoluto las actualizaciones de rango).

Mirando hacia el lado de las estadísticas / aplicaciones, las actualizaciones de rango uno son comunes en los sistemas de recomendación porque uno puede tener miles de entradas de clientes y volver a calcular el SVD (o cualquier descomposición dada) cada vez que un nuevo usuario se registra o un nuevo producto es agregado o eliminado es bastante derrochador (si no inalcanzable). Por lo general, las matrices del sistema de recomendación son escasas y esto hace que los algoritmos sean aún más eficientes. Un primer artículo accesible es el manuscrito " Revisiones rápidas de SVD en línea para sistemas de recomendación livianos " de M. Brand. Yendo a matrices densas, creo que mirar los documentos del Reconocimiento de patrones y el Procesamiento de imágenes puede llevarlo bastante lejos a conseguir un algoritmo real para usar. Por ejemplo los papeles:

Aprendizaje incremental de componentes principales bidireccionales para reconocimiento facial (2009) por Ren y Dai,
Sobre el aprendizaje subespacial incremental y robusto (2003) por Li et al.
Extracción de bases secuenciales de Karhunen-Loeve y su aplicación a imágenes (2000) por Levey y Lindenbaum.
Aprendizaje incremental para el seguimiento visual robusto (2007) por Ross et al.

todos parecen estar abordando el mismo problema en su núcleo; Están llegando nuevas características y necesitamos actualizar nuestra representación en consecuencia rápidamente . Observe que estas matrices no son simétricas ni cuadradas. Otro trabajo de M. Brand también puede abordar este problema (ver el documento " Modificaciones rápidas de bajo rango de la descomposición del valor singular delgado (2006) ", esto también se menciona en el enlace MO que aparece al principio de la publicación). muchos buenos trabajos sobre el tema, pero la mayoría tienden a ser muy matemáticos (por ejemplo, el trabajo de Benaych-Georgesa y Nadakuditi sobre " Los valores singulares y los vectores de perturbaciones de bajo rango de grandes matrices aleatorias rectangulares (2012) ") y no creo que ayuden a encontrar una solución pronto. Le sugiero que mantenga su enfoque en la literatura de Procesamiento de imágenes.

Lamentablemente, no he encontrado ninguna implementación de R para las rutinas de actualizaciones de rango uno. La respuesta sobre "¿ Implementación SVD actualizable en Python, C o Fortran? " De Computational Science SE ofrece varias implementaciones de MATLAB y C ++ que es posible que desee considerar. Por lo general, la implementación de R, Python, etc. son envoltorios alrededor de implementaciones de C, C ++ o FORTRAN.

usεr11852 dice Reinstate Monic
fuente

Este es un buen comentario, pero me decepcionó no encontrar una respuesta a la pregunta. Resulta que otro artículo de Matthew Brand , vinculado desde la respuesta de MO, contiene una solución explícita.

whuber

+1 tanto para usted como para @whuber (¡y no creo que se deba evitar "duplicar" cualquier información proporcionada en otro sitio de SE! Yo diría que deberíamos tratar de hacer que la información proporcionada en este sitio sea autosuficiente como sea posible De hecho, casi toda la información aquí contenida es, en cierto sentido, duplicar libros de texto, recursos en línea o trabajos de investigación existentes). Una pregunta: usted mencionó las fórmulas de Sherman-Morrison y Woodbury que describen cómo cambia el inverso de la matriz después de una actualización de rango uno o superior; ¿Qué tienen que ver con SVD?

ameba dice Reinstate Monica

Entiendo por qué es posible que desee dirigir a las personas a las páginas de MO para ese enlace, pero puede considerar directamente declarar que resuelve el problema. ("Un buen primer paso" es una gran subestimación). Gran parte de su comentario podría malinterpretarse como una indicación de que aún no ha encontrado una buena solución.

whuber

@whuber: "Bueno" se convirtió en "genial" y ahora también mencioné el artículo, ¿mejor? :) (Gracias por los comentarios por cierto.)

usεr11852 dice Reinstate Monic el

Solo por el bien de la historia: Bunch y Nielsen fueron los primeros en demostrar una forma de actualizar y actualizar la SVD. El método de la marca en general generaliza los métodos de este artículo anterior.

JM no es un estadístico

Actualización de la descomposición SVD después de agregar una nueva fila a la matriz

Respuestas: