An NPDo Approach for Principal Joint SVD-type Block Diagonalization

Resumo Técnico: Uma Abordagem NPDo para Diagonalização em Blocos do Tipo SVD Conjunta Principal

Enunciação do Problema
Este artigo aborda o problema da Diagonalização em Blocos do Tipo SVD Conjunta Principal (pjbsvd). Dado um conjunto de $N$ matrizes $B_\ell \in \mathbb{C}^{n_1 \times n_2}$, o objetivo é encontrar um par de matrizes ortonormais $(U, V)$ com dimensões $n_1 \times k$ e $n_2 \times k$, respectivamente (onde $1 \le k \le \min\{n_1, n_2\}$), de modo que as matrizes transformadas $U^H B_\ell V$ estejam simultaneamente e otimamente próximas de uma estrutura de blocos diagonais prescrita.

Diferentemente da SVD Conjunta padrão (onde $k = \min\{n_1, n_2\}$ e os blocos são $1 \times 1$), a pjbsvd permite $k < \min\{n_1, n_2\}$, tornando-a adequada para problemas de grande escala onde apenas componentes dominantes são de interesse. Além disso, a estrutura de blocos é definida por uma partição $\tau_k = (k_1, \dots, k_t)$ de $k$. O objetivo específico é maximizar a "massa" coletiva (norma de Frobenius ao quadrado) das partes diagonais em blocos em todas as matrizes:
$$\max_{(U,V) \in \text{St}(k,n_1) \times \text{St}(k,n_2)} f(U, V) := \sum_{\ell=1}^N \| \text{BDiag}_{\tau_k}(U^H B_\ell V) \|_F^2$$
onde $\text{St}(k, n)$ denota a variedade de Stiefel complexa. Casos especiais incluem SVD Conjunta Principal (pjsvd) (todos $k_i=1$) e Compressão Conjunta Principal ($t=1$).

Metodologia
Os autores propõem uma abordagem numérica baseada em NPDo (Decomposição Polar Não Linear com dependência do fator polar ortonormal). O método depende da seguinte estrutura teórica e algorítmica:

1. Condições KKT e Decomposição Polar: As condições de otimalidade para a função objetivo levam a duas equações de decomposição polar acopladas envolvendo funções de valor matricial $H_1(U, V)$ e $H_2(U, V)$, que dependem dos fatores ortonormais $U$ e $V$.
2. Iteração SCF Alternada (ASCF): O algoritmo central (Algoritmo 3.1) resolve essas equações acopladas por meio de uma iteração alternada de Campo Autoconsistente (SCF). Em cada etapa, o algoritmo atualiza $U$ e $V$ calculando os fatores polares ortonormais das matrizes de gradiente $H_1$ e $H_2$.
   • Atualização do tipo Jacobi: Atualiza $U$ e $V$ simultaneamente com base nos valores da iteração anterior.
   • Atualização do tipo Gauss-Seidel: Atualiza $U$ primeiro e, em seguida, utiliza o novo $U$ para atualizar $V$ dentro da mesma iteração.
3. Aceleração (LOCG): Para melhorar a eficiência, os autores introduzem uma aceleração por Gradiente Conjugado Localmente Ótimo (LOCG) (Algoritmo 3.2). Isso envolve a construção de um subespaço reduzido abrangido pela iteração atual e o gradiente residual, resolvendo uma versão menor do problema dentro deste subespaço e projetando a solução de volta.
4. Complexo vs. Real: A formulação é apresentada para variedades de Stiefel complexas, mas observa-se que se aplica diretamente a matrizes reais sem transformação.

Principais Contribuições

• Formulação: O artigo formaliza o problema de diagonalização em blocos do tipo SVD conjunta parcial/principal, estendendo conceitos existentes de SVD conjunta para casos onde a dimensão de saída $k$ é menor que as dimensões de entrada e os blocos podem ser maiores que $1 \times 1$.
• Desenvolvimento Algorítmico: Introduz a abordagem NPDo adaptada para este problema específico, utilizando iterações SCF alternadas. Os autores fornecem duas variantes (Jacobi e Gauss-Seidel) e uma versão acelerada LOCG.
• Análise de Convergência:
  • Gauss-Seidel: O artigo prova que a iteração ASCF do tipo Gauss-Seidel converge globalmente para um ponto estacionário, com a função objetivo aumentando monotonicamente a cada etapa.
  • Jacobi: Embora a função objetivo não seja garantida de aumentar monotonicamente no caso Jacobi, os autores analisam a convergência da sequência de pares intermediários e mostram convergência para um ponto estacionário sob condições específicas.
  • Extensões: A teoria de convergência é mostrada como aplicável a problemas de otimização mais gerais em variedades de Stiefel que satisfazem propriedades específicas de continuidade e gradiente.
• Eficiência Numérica: Os métodos propostos são projetados para lidar com matrizes de grande escala de forma eficiente, evitando a necessidade de transformar problemas complexos em reais, o que é uma limitação comum em pacotes de otimização em variedades de propósito geral.

Resultados
Experimentos numéricos foram conduzidos em conjuntos de dados gerados aleatoriamente com níveis de ruído ($\eta$) e dimensões ($n$ até 1000) variados.

• Eficácia: Mapas de calor das matrizes resultantes $U^H B_\ell V$ confirmam que o algoritmo concentra com sucesso a massa da matriz nas estruturas de blocos diagonais prescritas.
• Convergência: Todos os métodos alcançaram resíduos KKT abaixo de $10^{-8}$. As versões aceleradas (accNPDo) consistentemente produziram os menores resíduos.
• Desempenho:
  • As versões aceleradas por LOCG (accNPDo) foram significativamente mais rápidas que o NPDo padrão, particularmente para tamanhos de problema maiores.
  • Para o caso específico de pjsvd (tamanho de bloco $1 \times 1$), a variante Gauss-Seidel foi notavelmente mais rápida que a variante Jacobi. No entanto, para diagonalização em blocos geral (pjbsvd), a diferença de desempenho entre Gauss-Seidel e Jacobi foi menos pronunciada.
  • Os valores da função objetivo convergiram para diferentes pontos estacionários dependendo do método, indicando a natureza não convexa do problema.

Significado e Alegações
Os autores posicionam este trabalho como uma abordagem especializada de álgebra linear numérica, em vez de uma técnica de otimização de propósito geral. Eles afirmam que, ao explorar a estrutura específica do problema (soma de traços acoplados em variedades de Stiefel), sua abordagem NPDo oferece:

1. Simplicidade e Embutibilidade: O algoritmo é simples de implementar e adequado para integração em aplicações de grande escala.
2. Robustez: A variante Gauss-Seidel fornece garantias de convergência global com melhoria monotônica da função objetivo.
3. Escalabilidade: A capacidade de lidar com casos onde $k \ll \min\{n_1, n_2\}$ torna o método viável para aplicações modernas de big data, onde dados de alta dimensão exigem extração de componentes dominantes.
4. Evitação de Transformação: Ao contrário de muitos solucionadores existentes que exigem a transformação de problemas em variedades complexas em reais, esta abordagem opera diretamente em variedades de Stiefel complexas.

O artigo conclui observando que, embora a formulação atual imponha contagens de colunas iguais e partições de blocos simétricas para $U$ e $V$, a teoria e os métodos subjacentes são válidos para configurações mais gerais, embora aplicações práticas para tais generalizações permaneçam a serem exploradas.