An NPDo Approach for Tensor Block-Diagonalization

Resumo Técnico: Uma Abordagem NPDo para Bloco-Diagonalização de Tensores

Enunciado do Problema
Este artigo aborda o problema da Bloco-Diagonalização de Tensores Principais (PTBD). Dado um tensor de $m$ modos $\mathcal{B} \in \mathbb{C}^{n_1 \times n_2 \times \dots \times n_m}$, o objetivo é encontrar um conjunto de $m$ matrizes ortonormais $P_\ell \in \text{St}(k_\ell, n_\ell)$ (onde $\text{St}$ denota a variedade de Stiefel complexa) tais que o tensor transformado $\mathcal{T} = \mathcal{B} \times_1 P_1^H \times_2 P_2^H \dots \times_m P_m^H$ concentre-se otimamente em seus componentes bloco-diagonais.

O problema é formulado como a maximização da norma de Frobenius da parte bloco-diagonal de $\mathcal{T}$, denotada como $\|\text{BDiag}_{(\tau_{k_1}, \dots, \tau_{k_m})}(\mathcal{T})\|_F^2$, onde $\tau_{k_\ell}$ representa uma partição específica das dimensões dos modos. Esta formulação generaliza várias decomposições de tensores existentes:

• SVD Principal de Tensores (PT-SVD): Ocorre quando o tamanho de cada bloco é $1 \times 1 \times \dots \times 1$.
• Decomposição de Tucker (TD): Ocorre quando há apenas um bloco ($t=1$) por modo.
• Aproximação de Rango Um: Um caso especial onde todos os $k_\ell = 1$.

Ao contrário das decomposições de tensores padrão que frequentemente buscam representações aproximadas de baixo rango, a PTBD busca uma transformação ortonormal ótima que maximize a energia capturada dentro de uma estrutura bloco-diagonal específica.

Metodologia
Os autores propõem uma abordagem NPDo (Decomposição Polar Não Linear com dependência do fator polar ortonormal) para resolver o problema de otimização não convexo resultante.

1. Formulação de Otimização: O problema é lançado como a maximização de uma soma de traços acoplados. As condições de Karush-Kuhn-Tucker (KKT) para otimalidade levam a um sistema de $m$ equações de decomposição polar acopladas. Especificamente, em um ponto estacionário, o gradiente euclidiano parcial da função objetivo em relação a cada $P_\ell$ deve ser igual a $P_\ell \Lambda_\ell$, onde $\Lambda_\ell$ é uma matriz hermitiana semidefinida positiva.
2. Algoritmo Alternado SCF (Algoritmo 3.1): O método central é uma iteração alternada de Campo Autoconsistente (SCF) com atualização do tipo Gauss-Seidel. Em cada etapa, uma matriz $P_\ell$ é atualizada enquanto as outras são fixas. A atualização envolve calcular o gradiente parcial $H_\ell$ e extrair seu fator polar ortonormal via uma Decomposição em Valores Singulares (SVD) fina.
   • O algoritmo garante que a função objetivo aumente monotonicamente a cada etapa.
   • Ele lida com a não unicidade da solução (devido a rotações de blocos) focando na convergência das condições KKT em vez da convergência entrada por entrada das matrizes.
3. Aceleração LOCG (Algoritmo 3.2): Para melhorar a eficiência, os autores introduzem uma aceleração por Gradiente Conjugado Localmente Ótimo (LOCG). Este método constrói um subespaço de busca spanado pela iteração atual, pela iteração anterior e pelo resíduo (gradiente). A otimização é então realizada dentro deste subespaço reduzido, reduzindo significativamente o número de iterações externas necessárias.

Análise de Convergência
O artigo fornece uma análise rigorosa de convergência para ambos os algoritmos padrão e acelerados:

• Monotonicidade: A função objetivo é provada aumentar monotonicamente a cada iteração.
• Convergência Global: A sequência de iterações é mostrada como globalmente convergente para um ponto estacionário sob condições específicas (por exemplo, se o ponto de acumulação é isolado e as matrizes de gradiente relevantes têm rango completo).
• Satisfação KKT: Mesmo sem convergência global da própria sequência, o artigo prova que as iterações computadas satisfazem cada vez mais as condições KKT. Especificamente, o resíduo da condição de decomposição polar converge para zero, desde que o menor valor singular das matrizes de gradiente permaneça limitado afastado de zero.
• Generalização: As provas de convergência dependem de propriedades gerais da função objetivo e dos gradientes, sugerindo que os resultados se aplicam a uma classe mais ampla de problemas além da PTBD.

Resultados Numéricos
Extensos experimentos numéricos foram conduzidos em tensores reais e complexos gerados aleatoriamente de tamanhos variados (até $600 \times 550 \times 600$).

• Comportamento de Convergência: Ambos os algoritmos reduziram com sucesso o resíduo KKT para aproximadamente $10^{-9}$ ou inferior. O número de iterações necessárias diminuiu à medida que o tensor de entrada se tornava mais próximo de ser perfeitamente bloco-diagonalizável (controlado por um parâmetro de ruído $\eta$).
• Eficiência: A versão acelerada por LOCG (accNPDo) demonstrou uma redução dramática no número de iterações externas em comparação com a abordagem NPDo padrão (Gauss-Seidel).
• Escalabilidade: O tempo de CPU foi observado crescendo linearmente com os parâmetros de tamanho do tensor. O método acelerado superou consistentemente o método padrão em termos de tempo total de computação.
• Trajetória da Objetivo: Embora o resíduo KKT não seja estritamente monotônico, o valor da função objetivo aumenta monotonicamente. Os autores observaram picos ocasionais no resíduo KKT correspondentes a saltos no valor da função objetivo, sugerindo que o algoritmo escapa de "pontos de sela" locais para alcançar pontos estacionários melhores.

Significado e Afirmações
O artigo afirma que a abordagem NPDo fornece um quadro unificado para o cálculo de bloco-diagonalizações dominantes de tensores, englobando PT-SVD e decomposição de Tucker como casos especiais.

• Contribuição Teórica: A principal contribuição teórica é o estabelecimento da convergência global para um ponto estacionário para o esquema SCF alternado aplicado a esta classe específica de problemas de decomposição polar acoplada. Os autores notam que, embora trabalhos anteriores (por exemplo, sobre SVD de Tensores ou decomposição de Tucker) tenham estabelecido condições KKT similares, este artigo fornece uma análise de convergência mais abrangente, incluindo resultados quantitativos sobre a velocidade de convergência e o comportamento dos resíduos KKT.
• Utilidade Prática: O método proposto oferece um algoritmo eficiente e escalável para extrair estruturas bloco-diagonais de dados de alta dimensão, com a aceleração LOCG tornando-o viável para problemas de grande escala.
• Generalidade: A abordagem é formulada para tensores complexos, aplicando-se automaticamente a tensores reais, e a teoria de convergência é apresentada de uma maneira que sugere aplicabilidade a outros problemas de otimização envolvendo decomposições polares acopladas em variedades de Stiefel.