An NPDo Approach for Tensor Block-Diagonalization

Resumen Técnico: Un Enfoque NPDo para la Bloque-Diagonalización de Tensores

Enunciado del Problema
Este artículo aborda el problema de la Bloque-Diagonalización de Tensores Principales (PTBD). Dado un tensor de $m$ modos $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$, el objetivo es encontrar un conjunto de $m$ matrices ortonormales $P_\ell \in \text{St}(k_\ell, n_\ell)$ (donde $\text{St}$ denota la variedad de Stiefel compleja) tales que el tensor transformado $\mathcal{T} = \mathcal{B} \times_1 P_1^H \times_2 P_2^H \dots \times_m P_m^H$ se concentre óptimamente en sus componentes bloque-diagonales.

El problema se formula como la maximización de la norma de Frobenius de la parte bloque-diagonal de $\mathcal{T}$, denotada como $\|\text{BDiag}_{(\tau_{k_1}, \dots, \tau_{k_m})}(\mathcal{T})\|_F^2$, donde $\tau_{k_\ell}$ representa una partición específica de las dimensiones de los modos. Esta formulación generaliza varias descomposiciones de tensores existentes:

• SVD de Tensores Principales (PT-SVD): Ocurre cuando el tamaño de cada bloque es $1 \times 1 \times \dots \times 1$.
• Descomposición de Tucker (TD): Ocurre cuando hay un solo bloque ($t=1$) por modo.
• Aproximación de Rango Uno: Un caso especial donde todos los $k_\ell = 1$.

A diferencia de las descomposiciones de tensores estándar que a menudo buscan representaciones aproximadas de bajo rango, la PTBD busca una transformación ortonormal óptima que maximice la energía capturada dentro de una estructura bloque-diagonal específica.

Metodología
Los autores proponen un enfoque NPDo (Descomposición Polar No Lineal con dependencia del factor polar ortonormal) para resolver el problema de optimización no convexa resultante.

1. Formulación de Optimización: El problema se plantea como la maximización de una suma de trazas acopladas. Las condiciones de Karush-Kuhn-Tucker (KKT) para la optimalidad conducen a un sistema de $m$ ecuaciones de descomposición polar acopladas. Específicamente, en un punto estacionario, el gradiente euclidiano parcial de la función objetivo con respecto a cada $P_\ell$ debe ser igual a $P_\ell \Lambda_\ell$, donde $\Lambda_\ell$ es una matriz semidefinida positiva hermítica.
2. Algoritmo Alternante SCF (Algoritmo 3.1): El método central es una iteración alternante de Campo Autoconsistente (SCF) con actualización tipo Gauss-Seidel. En cada paso, se actualiza una matriz $P_\ell$ mientras las demás permanecen fijas. La actualización implica calcular el gradiente parcial $H_\ell$ y extraer su factor polar ortonormal mediante una Descomposición en Valores Singulares (SVD) delgada.
   • El algoritmo asegura que la función objetivo aumente monótonamente en cada paso.
   • Maneja la no unicidad de la solución (debido a rotaciones de bloques) centrándose en la convergencia de las condiciones KKT en lugar de la convergencia entrada por entrada de las matrices.
3. Aceleración LOCG (Algoritmo 3.2): Para mejorar la eficiencia, los autores introducen una aceleración mediante Gradiente Conjugado Localmente Óptimo (LOCG). Este método construye un subespacio de búsqueda abarcado por la iteración actual, la iteración anterior y el residuo (gradiente). La optimización se realiza entonces dentro de este subespacio reducido, reduciendo significativamente el número de iteraciones externas requeridas.

Análisis de Convergencia
El artículo proporciona un análisis riguroso de la convergencia para ambos algoritmos, el estándar y el acelerado:

• Monotonía: Se demuestra que la función objetivo aumenta monótonamente con cada iteración.
• Convergencia Global: Se muestra que la secuencia de iteraciones converge globalmente a un punto estacionario bajo condiciones específicas (por ejemplo, si el punto de acumulación está aislado y las matrices de gradiente relevantes tienen rango completo).
• Satisfacción de KKT: Incluso sin convergencia global de la secuencia en sí, el artículo demuestra que las iteraciones calculadas satisfacen cada vez más las condiciones KKT. Específicamente, el residuo de la condición de descomposición polar converge a cero, siempre que el valor singular más pequeño de las matrices de gradiente permanezca acotado lejos de cero.
• Generalización: Las pruebas de convergencia se basan en propiedades generales de la función objetivo y los gradientes, lo que sugiere que los resultados se aplican a una clase más amplia de problemas más allá de la PTBD.

Resultados Numéricos
Se realizaron experimentos numéricos extensos en tensores reales y complejos generados aleatoriamente de diversos tamaños (hasta $600 \times 550 \times 600$).

• Comportamiento de Convergencia: Ambos algoritmos redujeron con éxito el residuo KKT a aproximadamente $10^{-9}$ o menos. El número de iteraciones requeridas disminuyó a medida que el tensor de entrada se acercaba a ser perfectamente bloque-diagonalizable (controlado por un parámetro de ruido $\eta$).
• Eficiencia: La versión acelerada con LOCG (accNPDo) demostró una reducción dramática en el número de iteraciones externas en comparación con el enfoque NPDo estándar (Gauss-Seidel).
• Escalabilidad: Se observó que el tiempo de CPU crecía linealmente con los parámetros de tamaño del tensor. El método acelerado superó consistentemente al método estándar en términos de tiempo total de cómputo.
• Trayectoria de la Función Objetivo: Aunque el residuo KKT no es estrictamente monótono, el valor de la función objetivo aumenta monótonamente. Los autores observaron picos ocasionales en el residuo KKT que corresponden a saltos en el valor de la función objetivo, lo que sugiere que el algoritmo escapa de "puntos de silla" locales para alcanzar puntos estacionarios mejores.

Significado y Afirmaciones
El artículo afirma que el enfoque NPDo proporciona un marco unificado para calcular bloque-diagonalizaciones dominantes de tensores, abarcando la PT-SVD y la descomposición de Tucker como casos especiales.

• Contribución Teórica: La contribución teórica principal es el establecimiento de la convergencia global a un punto estacionario para el esquema SCF alternante aplicado a esta clase específica de problemas de descomposición polar acoplada. Los autores señalan que, aunque trabajos anteriores (por ejemplo, sobre SVD de tensores o descomposición de Tucker) establecieron condiciones KKT similares, este artículo proporciona un análisis de convergencia más completo, incluidos resultados cuantitativos sobre la velocidad de convergencia y el comportamiento de los residuos KKT.
• Utilidad Práctica: El método propuesto ofrece un algoritmo eficiente y escalable para extraer estructuras bloque-diagonales de datos de alta dimensión, siendo la aceleración LOCG lo que lo hace viable para problemas a gran escala.
• Generalidad: El enfoque se formula para tensores complejos, aplicándose automáticamente a tensores reales, y la teoría de convergencia se presenta de manera que sugiere aplicabilidad a otros problemas de optimización que involucran descomposiciones polares acopladas en variedades de Stiefel.