Actualización de la descomposición SVD tras añadir una nueva fila a la matriz

Question

Supongamos que tengo una matriz densa $ \textbf{A}$ de $m \times n$ tamaño, con descomposición SVD $$\mathbf{A}=\mathbf{USV}^\top.$$ En R Puedo calcular la SVD de la siguiente manera: svd(A) .

Si un nuevo $(m+1)$ -se añade una fila a $\mathbf A$ se puede calcular la nueva descomposición SVD a partir de la anterior (es decir, utilizando $\mathbf U$ , $\mathbf S$ y $\mathbf V$ ), sin volver a calcular el SVD desde cero?

Answer 1

Sí, se puede actualizar una descomposición SVD tras añadir una nueva fila a la matriz existente.

En general, este " añadir uno a "La formulación del problema se conoce como actualizaciones del rango uno . El enlace de MathOverflow proporcionado por @amoeba en " actualizaciones eficientes de rango dos de una descomposición de valores propios " es un gran primer paso si quieres empezar a profundizar en el asunto; el primer documento proporciona una solución explícita a tu pregunta concreta. Sólo para aclarar lo que significan el rango uno y el rango dos para que no se confunda, si su nuevo $A^*$ es tal que:

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

Dónde $u$ y $v$ son vectores, entonces se habla de una actualización de rango uno (o perturbación ). Las bases de esta actualización están dictadas por el Fórmula Sherman-Morrison. . Si la perturbación es de más de un rango, es decir \begin{align} A^* = A - UV^T \end{align}

el Fórmula Woodbury entra en juego. Si ves estas fórmulas te darás cuenta de que hay muchas inversas involucradas. No se resuelven directamente. Como ya has resuelto gran parte de sus subsistemas (es decir, tienes alguna descomposición ya calculada) las utilizas para obtener unas estimaciones más rápidas y/o estables. (Por eso la gente sigue investigando en este campo). He utilizado el libro " Estadística computacional " de J.E. Gentle mucho como referencia; creo que el capítulo 5 Álgebra lineal numérica te pondrá a tono. (El superclásico: " Álgebra matricial desde la perspectiva del estadístico " de Harville, por desgracia, no aborda en absoluto las actualizaciones de los rangos).

Desde el punto de vista de las estadísticas y las aplicaciones, las actualizaciones de rango uno son habituales en los sistemas de recomendación, ya que se pueden tener miles de entradas de clientes y volver a calcular la SVD (o cualquier descomposición) cada vez que se registra un nuevo usuario o se añade o elimina un nuevo producto es bastante inútil (si no imposible). Por lo general, las matrices de los sistemas de recomendación son dispersas, lo que hace que los algoritmos sean aún más eficaces. Un primer trabajo accesible es el de " Revisiones rápidas de SVD en línea para sistemas de recomendación ligeros " manuscrito de M. Brand. En cuanto a las matrices densas, creo que mirar los artículos de Pattern Recognition and Imaging Processing puede llevarte bastante lejos en la obtención de un algoritmo real para usar. Por ejemplo, los documentos:

1. Aprendizaje incremental de componentes principales bidireccionales para el reconocimiento de caras reconocimiento de rostros (2009) por Ren y Dai,
2. Sobre el aprendizaje incremental y robusto del subespacio robusto (2003) por Li et al.
3. Extracción secuencial de bases Karhunen-Loeve y su aplicación a las imágenes (2000) por Levey y Lindenbaum.
4. Aprendizaje incremental para el seguimiento visual robusto (2007) por Ross et al.

todos parecen estar abordando el mismo problema en su núcleo; las nuevas características están llegando y tenemos que actualizar nuestra representación en consecuencia rápido . Obsérvese que estas matrices no son simétricas, ni siquiera cuadradas. Otro trabajo de M. Brand también puede abordar este problema (véase el documento " Modificaciones rápidas de bajo rango de la descomposición fina del valor singular (2006) " - esto también se menciona en el enlace de MO dado al principio del post). Hay un montón de buenos artículos sobre el tema, pero la mayoría tienden a ser muy matemáticos (por ejemplo, el artículo de Benaych-Georgesa y Nadakuditi sobre " Los valores singulares y vectores de perturbaciones de bajo rango de grandes matrices aleatorias rectangulares (2012) ") y no creo que ayuden a conseguir una solución pronto. Le sugiero que mantenga su enfoque en la literatura de Procesamiento de Imágenes.

Desgraciadamente no he encontrado ninguna implementación de R para las rutinas de actualización de rango uno. La respuesta en " ¿Implementación de SVD actualizable en Python, C o Fortran? " del Computational Science SE ofrece una serie de implementaciones en MATLAB y C++ que puede considerar. Por lo general, las implementaciones de R, Python, etc. son envoltorios de implementaciones de C, C++ o FORTRAN.