Convergence Analysis of Two Alternating Iterative Schemes for Tucker Decomposition

Resumen Técnico: Análisis de Convergencia de Dos Esquemas Iterativos Alternantes para la Descomposición de Tucker

Planteamiento del Problema
El artículo aborda el cálculo de la descomposición de Tucker (DT) para un tensor de $m$-modos $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$. El objetivo es encontrar matrices factoriales ortonormales $P_\ell \in \text{St}(k_\ell, n_\ell)$ (donde $\text{St}$ denota la variedad de Stiefel compleja) y un tensor núcleo $\mathcal{T}$ tales que el error de aproximación $\|\mathcal{B} - \mathcal{T} \times_1 P_1 \times_2 P_2 \dots \times_m P_m\|_F$ se minimice. Esto es equivalente a maximizar la función objetivo $f(P_1, \dots, P_m) = \|\mathcal{B} \times_1 P_1^H \times_2 P_2^H \dots \times_m P_m^H\|_F^2$.

Aunque existen dos esquemas iterativos alternantes populares para este problema —la Iteración Ortogonal de Alto Orden (HOOI) y la Iteración de Subespacio Alternante (ASI)—, sus propiedades teóricas de convergencia han estado previamente incompletas. Específicamente, el análisis de ASI realizado por Kroonenberg y De Leeuw (1980) contenía lagunas técnicas, y el análisis de una variante "codiciosa" de HOOI por Xu (2018) se restringía a tensores reales y dependía de la teoría avanzada de funciones semialgebraicas (Kurdyka–Lojasiewicz) menos familiar para la comunidad de álgebra lineal numérica.

Metodología
Los autores reformulan la minimización del error de aproximación como un problema de maximización que involucra $m$ ecuaciones matriciales no lineales acopladas. Estas ecuaciones se interpretan de dos maneras:

1. Como un sistema de Problemas de Valores Propios No Lineales acoplados con dependencia de vectores propios (NEPv).
2. Como un sistema de Descomposiciones Polares No Lineales acopladas con dependencia del factor polar ortonormal (NPDo).

El artículo analiza dos algoritmos basados en estas formulaciones:

• HOOI (Algoritmo 4.1): Un esquema de tipo Gauss-Seidel donde, en cada paso, $P_\ell$ se actualiza para ser la matriz de los $k_\ell$ vectores singulares izquierdos principales de un tensor plegado específico (o equivalentemente, los $k_\ell$ vectores propios principales de una matriz hermítica $H_\ell$).
• ASI (Algoritmo 5.1): Un esquema de tipo Gauss-Seidel donde $P_\ell$ se actualiza mediante una iteración de subespacio de un solo paso (específicamente, el factor polar ortonormal de $H_\ell P_\ell$), en lugar de resolver el problema completo de valores propios.

El análisis de convergencia se basa en herramientas del álgebra lineal numérica, incluidos los ángulos canónicos entre subespacios, cotas de error para aproximaciones de valores propios/singulares extremos mediante trazas de matrices y propiedades de la variedad de Grassmann. El análisis se realiza para tensores complejos, considerando los tensores reales como un caso especial.

Contribuciones Clave

1. Pruebas Rigurosas de Convergencia: El artículo proporciona análisis detallados de convergencia tanto para HOOI como para ASI. Demuestra que, bajo condiciones leves, ambos métodos generan secuencias donde la función objetivo aumenta monótonamente y converge.
2. Convergencia Global a Puntos Estacionarios: Los autores demuestran que ambos algoritmos convergen globalmente a puntos estacionarios que satisfacen las condiciones de Karush-Kuhn-Tucker (KKT).
   • Para HOOI, los puntos límite satisfacen un sistema de ecuaciones NEPv acopladas donde los valores propios corresponden a los valores propios más grandes de las matrices hermíticas asociadas.
   • Para ASI, los puntos límite satisfacen un sistema de ecuaciones NPDo acopladas.
3. Manejo de la No Unicidad: El análisis aborda la no unicidad inherente de la descomposición de Tucker (debida a la invariancia unitaria). Los autores muestran que, aunque la secuencia de matrices puede no converger término a término sin alineación, la secuencia de subespacios converge, y la función objetivo converge.
4. Generalización a Tensores Complejos: A diferencia de trabajos anteriores restringidos a tensores reales, este análisis se aplica a tensores complejos, ampliando la aplicabilidad de las garantías de convergencia.
5. Clarificación de la "Alineación Codiciosa": El artículo argumenta que el paso de "alineación" (ajustar la fase/orientación de $P_\ell$ en cada iteración para coincidir con el paso anterior), propuesto por Xu para HOOI codicioso, es numéricamente innecesario para la calidad de la aproximación final, aunque puede ser útil para pruebas teóricas de convergencia.

Resultados

• Resultados Teóricos:
  • Monotonía: Ambos algoritmos producen una secuencia monótonamente creciente de valores objetivo.
  • Estacionariedad: Los puntos de acumulación de las secuencias generadas satisfacen las condiciones KKT.
  • Tasas de Convergencia: El artículo establece que la suma de las distancias al cuadrado entre iteraciones consecutivas (ponderadas por brechas de valores propios o valores singulares) es finita, lo que implica que las iteraciones se aproximan a un punto estacionario.
  • Convergencia Global: Si el punto estacionario está aislado y se cumplen ciertas condiciones de brecha espectral (para HOOI) o de rango completo (para ASI), toda la secuencia converge a ese punto.
• Experimentos Numéricos:
  • Se realizaron experimentos en un "Tensor de Simulación Científica Miranda" y en tensores generados aleatoriamente (tanto reales como complejos).
  • HOOI vs. ASI: HOOI requirió consistentemente menos iteraciones para converger que ASI, ya que calcula el subespacio óptimo en cada paso, mientras que ASI realiza solo un paso de iteración de potencia.
  • Inicialización: Utilizar una HOSVD truncada como estimación inicial generalmente redujo el número de iteraciones, aunque no universalmente (en algunos casos, la inicialización aleatoria convergió más rápido).
  • Complejidad: Aunque HOOI converge en menos iteraciones, el costo computacional por iteración es mayor que el de ASI. Sin embargo, los autores observaron que el tiempo total de CPU para ambos métodos fue competitivo, ya que los ahorros en el recuento de iteraciones de HOOI compensaron el mayor costo por paso.
  • Criterios de Detención: Los experimentos destacaron el riesgo de "falsa convergencia", donde la función objetivo se estabiliza temporalmente antes de volver a subir, lo que sugiere que los criterios de detención basados en residuos son más robustos que los basados en valores objetivo.

Significado y Afirmaciones
El artículo afirma proporcionar un análisis de convergencia más accesible y autocontenido para los algoritmos de descomposición de Tucker en comparación con trabajos anteriores. Al depender enteramente de conceptos de álgebra lineal numérica en lugar de la geometría semialgebraica, los resultados están destinados a ser más accesibles para la comunidad de álgebra lineal numérica. Los autores enfatizan que su análisis cubre tanto tensores reales como complejos y corrige lagunas en el análisis histórico de ASI. Concluyen que, aunque HOOI es teóricamente superior en términos de recuento de iteraciones, ambos métodos son globalmente convergentes y efectivos para calcular descomposiciones de Tucker, siendo la elección entre ellos potencialmente dependiente del compromiso específico entre el recuento de iteraciones y el costo computacional por iteración.