Convergence Analysis of Two Alternating Iterative Schemes for Tucker Decomposition

Resumo Técnico: Análise de Convergência de Dois Esquemas Iterativos Alternados para Decomposição de Tucker

Enunciado do Problema
O artigo aborda o cálculo da decomposição de Tucker (DT) para um tensor $m$-modos $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$. O objetivo é encontrar matrizes fator ortonormais $P_\ell \in \text{St}(k_\ell, n_\ell)$ (onde $\text{St}$ denota a variedade de Stiefel complexa) e um tensor núcleo $\mathcal{T}$ tal que o erro de aproximação $\|\mathcal{B} - \mathcal{T} \times_1 P_1 \times_2 P_2 \dots \times_m P_m\|_F$ seja minimizado. Isso é equivalente a maximizar a função 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$.

Embora existam dois esquemas iterativos alternados populares para este problema — a Iteração Ortogonal de Alta Ordem (HOOI) e a Iteração Alternada de Subespaço (ASI) —, suas propriedades de convergência teórica foram anteriormente incompletas. Especificamente, a análise da ASI por Kroonenberg e De Leeuw (1980) continha lacunas técnicas, e a análise de uma variante "gananciosa" da HOOI por Xu (2018) restringia-se a tensores reais e baseava-se na teoria avançada de funções semi-algébricas (Kurdyka–Lojasiewicz), menos familiar à comunidade de álgebra linear numérica.

Metodologia
Os autores reformulam a minimização do erro de aproximação como um problema de maximização envolvendo $m$ equações matriciais não lineares acopladas. Essas equações são interpretadas de duas maneiras:

1. Como um sistema de Problemas de Autovalores Não Lineares Acoplados com dependência de autovetores (NEPv).
2. Como um sistema de Decomposições Polares Não Lineares Acopladas com dependência do fator polar ortonormal (NPDo).

O artigo analisa dois algoritmos baseados nessas formulações:

• HOOI (Algoritmo 4.1): Um esquema do tipo Gauss-Seidel onde, em cada etapa, $P_\ell$ é atualizado para ser a matriz dos $k_\ell$ autovetores esquerdos principais de um tensor desdobrado específico (ou equivalentemente, os $k_\ell$ autovetores principais de uma matriz hermitiana $H_\ell$).
• ASI (Algoritmo 5.1): Um esquema do tipo Gauss-Seidel onde $P_\ell$ é atualizado via uma iteração de subespaço de um único passo (especificamente, o fator polar ortonormal de $H_\ell P_\ell$), em vez de resolver o problema completo de autovalores.

A análise de convergência utiliza ferramentas da álgebra linear numérica, incluindo ângulos canônicos entre subespaços, limites de erro para aproximações de autovalores/valores singulares extremos via traços matriciais e propriedades da variedade de Grassmann. A análise é conduzida para tensores complexos, com tensores reais tratados como um caso especial.

Principais Contribuições

1. Provas Rigorosas de Convergência: O artigo fornece análises detalhadas de convergência para HOOI e ASI. Demonstra-se que, sob condições suaves, ambos os métodos geram sequências onde a função objetivo aumenta monotonicamente e converge.
2. Convergência Global para Pontos Estacionários: Os autores demonstram que ambos os algoritmos convergem globalmente para pontos estacionários que satisfazem as condições Karush-Kuhn-Tucker (KKT).
   • Para a HOOI, os pontos limite satisfazem um sistema de equações NEPv acopladas onde os autovalores correspondem aos maiores autovalores das matrizes hermitianas associadas.
   • Para a ASI, os pontos limite satisfazem um sistema de equações NPDo acopladas.
3. Tratamento da Não Unicidade: A análise aborda a não unicidade inerente da decomposição de Tucker (devido à invariância unitária). Os autores mostram que, embora a sequência de matrizes possa não convergir termo a termo sem alinhamento, a sequência de subespaços converge e a função objetivo converge.
4. Generalização para Tensores Complexos: Diferentemente de trabalhos anteriores restritos a tensores reais, esta análise aplica-se a tensores complexos, ampliando a aplicabilidade das garantias de convergência.
5. Esclarecimento do "Alinhamento Ganancioso": O artigo argumenta que o passo de "alinhamento" (ajustar a fase/orientação de $P_\ell$ em cada iteração para corresponder ao passo anterior), proposto por Xu para a HOOI gananciosa, é numericamente desnecessário para a qualidade da aproximação final, embora possa ser útil para provas teóricas de convergência.

Resultados

• Resultados Teóricos:
  • Monotonicidade: Ambos os algoritmos produzem uma sequência monotonicamente crescente de valores objetivos.
  • Estacionariedade: Pontos de acumulação das sequências geradas satisfazem as condições KKT.
  • Taxas de Convergência: O artigo estabelece que a soma dos quadrados das distâncias entre iterações consecutivas (ponderada por lacunas de autovalores ou valores singulares) é finita, implicando que as iterações se aproximam de um ponto estacionário.
  • Convergência Global: Se o ponto estacionário for isolado e certas condições de lacuna espectral (para HOOI) ou condições de posto completo (para ASI) forem atendidas, toda a sequência converge para esse ponto.
• Experimentos Numéricos:
  • Experimentos foram conduzidos em um "Tensor de Simulação Científica Miranda" e em tensores gerados aleatoriamente (tanto reais quanto complexos).
  • HOOI vs. ASI: A HOOI consistentemente exigiu menos iterações para convergir do que a ASI, pois calcula o subespaço ótimo em cada etapa, enquanto a ASI realiza apenas um único passo de iteração de potência.
  • Inicialização: O uso de uma HOSVD truncada como estimativa inicial geralmente reduziu o número de iterações, embora não universalmente (em alguns casos, a inicialização aleatória convergiu mais rapidamente).
  • Complexidade: Embora a HOOI convirja em menos iterações, o custo computacional por iteração é maior do que o da ASI. No entanto, os autores observaram que o tempo total de CPU para ambos os métodos foi competitivo, pois a economia no número de iterações da HOOI equilibrava o maior custo por etapa.
  • Critérios de Parada: Os experimentos destacaram o risco de "falsa convergência", onde a função objetivo estagna temporariamente antes de subir novamente, sugerindo que critérios de parada baseados em resíduos são mais robustos do que aqueles baseados em valores objetivos.

Significado e Alegações
O artigo alega fornecer uma análise de convergência mais acessível e autocontida para algoritmos de decomposição de Tucker em comparação com trabalhos anteriores. Ao depender inteiramente de conceitos de álgebra linear numérica em vez de geometria semi-algébrica, os resultados destinam-se a ser mais acessíveis à comunidade de álgebra linear numérica. Os autores enfatizam que sua análise cobre tanto tensores reais quanto complexos e corrige lacunas na análise histórica da ASI. Eles concluem que, embora a HOOI seja teoricamente superior em termos de número de iterações, ambos os métodos são globalmente convergentes e eficazes para o cálculo de decomposições de Tucker, sendo a escolha entre eles potencialmente dependente do compromisso específico entre o número de iterações e o custo computacional por iteração.