A Practical Mode-parallel Implementation of the (H-)Tucker Decomposition via Randomization

Título

Uma Implementação Prática Paralela por Modos da Decomposição (H-)Tucker via Randomização

1. O Problema

Os tensores (arrays multidimensionais) tornaram-se ferramentas essenciais para representar grandes conjuntos de dados em áreas como aprendizado profundo, visão computacional e processamento de sinais. A decomposição de tensores, especificamente as formatos Tucker e Hierárquico Tucker (H-Tucker), é amplamente utilizada para revelar estruturas ocultas e comprimir dados.

No entanto, existem desafios significativos na computação dessas decomposições para tensores de alta dimensão (com muitos modos):

• Custo Computacional e de Memória: Os algoritmos determinísticos tradicionais (como HOSVD - High-Order SVD) exigem a formação explícita de "desdobramentos" (matricizações) do tensor. Para tensores de alta ordem, essas matricizações são extremamente grandes, exigindo memória que cresce exponencialmente e tornando o processo energeticamente dispendioso.
• Limitações de Paralelismo: Embora a decomposição Tucker seja naturalmente paralelizável por modos (cada modo pode ser processado independentemente), a necessidade de carregar cópias completas do tensor ou suas matricizações em cada nó de computação impede uma implementação verdadeiramente paralela e escalável em ambientes de HPC (High-Performance Computing).
• Ineficiência de Métodos Atuais: Métodos existentes que tentam paralelizar operações (como Tensor-Times-Matrix) ainda visitam os modos de forma sequencial ou exigem a montagem de estruturas de dados massivas, não resolvendo o gargalo de memória.

2. Metodologia Proposta

Os autores propõem novas estratégias numéricas baseadas em randomização para realizar as decomposições Tucker e H-Tucker de forma paralela por modos. A abordagem central evita a formação de qualquer matricização completa do tensor.

A metodologia combina duas técnicas principais:

1. Amostragem de Fibras (Fiber Sampling): Em vez de construir a matriz desdobrada $X^{(k)}$ (que teria $n_k \times \prod_{j \neq k} n_j$ elementos), o algoritmo amostra aleatoriamente um subconjunto de "fibras" (linhas ou colunas) do tensor original. Isso permite construir uma matriz muito menor $Y_k$ contendo apenas as fibras amostradas, eliminando a necessidade de armazenar o tensor completo ou suas matricizações.
2. Encontrador de Intervalo Randomizado (Randomized Range-Finding): Após a amostragem, utiliza-se um algoritmo de range-finding (como SVD Randomizada - RSVD) sobre a matriz amostrada $Y_k$ para estimar a base do espaço coluna do desdobramento original.

Algoritmos Propostos:

• Sub-R-HOSVD: Uma variante da HOSVD truncada que substitui a SVD determinística por SVD Randomizada aplicada a fibras amostradas.
• Sub-R-RtL-HT: Uma variante do algoritmo Root-to-Leaves (RtL) para a decomposição H-Tucker, aplicando a mesma lógica de amostragem e randomização em cada nó da árvore de dimensões.

3. Principais Contribuições

• Paralelismo Real por Modos: Ao eliminar a necessidade de armazenar $d$ cópias do tensor original (ou suas matricizações), o método permite que cada nó computacional processe um modo independentemente, armazenando apenas as fibras amostradas. Isso reduz drasticamente a demanda de memória local e os custos de comunicação entre nós.
• Novas Limites de Erro: Os autores derivam limites teóricos superiores para o valor esperado do erro de aproximação da decomposição Sub-R-HOSVD, provando que a amostragem aleatória, quando combinada com o range-finding, preserva a qualidade da aproximação sob certas condições de coerência.
• Extensão para H-Tucker: Adaptação bem-sucedida da estratégia de amostragem para a decomposição H-Tucker, onde a complexidade de armazenamento é reduzida de exponencial para linear em relação ao número de modos.
• Implementação em HPC: Desenvolvimento e teste de uma implementação escalável em ambientes de computação de alto desempenho.

4. Resultados Numéricos

Os experimentos foram realizados em um cluster HPC (sistema Leonardo, Cineca) utilizando dados sintéticos e do mundo real (imagens COIL-100 e dados meteorológicos).

• Desempenho de Tempo: O método Sub-R-HOSVD foi consistentemente uma ordem de magnitude mais rápido que os métodos determinísticos (HOSVD, ST-HOSVD) e outras técnicas randomizadas de ponta (R-HOSVD, SI-HOSVD, rHKron), especialmente para tensores de alta ordem ($d \ge 5$).
• Precisão: A precisão da aproximação foi comparável ou superior aos métodos determinísticos. Curiosamente, o erro do método proposto manteve-se estável à medida que a ordem do tensor aumentava, enquanto os erros dos métodos tradicionais tendiam a aumentar.
• Eficiência de Memória: O método conseguiu operar com apenas uma fração minúscula dos dados (ex: 0,00005% das colunas da matricização) sem perda de precisão, demonstrando a viabilidade de evitar a alocação de matricizações completas.
• Escalabilidade:
  • Em testes sequenciais, o método mostrou excelente desempenho.
  • Em testes paralelos, a abordagem demonstrou boa escalabilidade forte (strong scaling). A implementação paralela da geração de índices de amostragem foi crucial para manter a eficiência à medida que o tamanho dos dados aumentava.
  • Para H-Tucker, a abordagem RtL mostrou-se altamente paralelizável, embora o balanceamento de carga entre os nós da árvore de dimensões seja um desafio crítico para a escalabilidade máxima.

5. Significado e Conclusão

Este trabalho apresenta um avanço significativo na computação tensorial ao tornar viável a decomposição de tensores de alta dimensão em ambientes de memória limitada e paralelos.

• Impacto Prático: A capacidade de realizar decomposições sem formar matricizações completas remove uma barreira fundamental para o processamento de grandes dados multidimensionais em clusters modernos.
• Eficiência: A combinação de amostragem e randomização não apenas acelera o cálculo, mas também reduz drasticamente o consumo de energia e memória.
• Futuro: O trabalho abre caminho para pesquisas sobre a análise de precisão em aritmética de ponto flutuante finita e a derivação de limites de erro rigorosos para a variante H-Tucker randomizada.

Em resumo, os autores demonstraram que é possível realizar decomposições tensoriais de alta ordem de forma eficiente, precisa e verdadeiramente paralela, superando as limitações de memória e tempo dos métodos determinísticos tradicionais.