Tensor CUR Decomposition under the Linear-Map-Based Tensor-Tensor Multiplication

Resumo Técnico: Decomposição Tensor CUR sob Multiplicação de Tensores Baseada em Mapas Lineares

1. O Problema

A decomposição de tensores de baixo posto é fundamental para a compressão e representação de grandes conjuntos de dados multidimensionais (como vídeos e imagens hiperespectrais). O desafio central reside em preservar a estrutura multi-via (multiway) dos dados, evitando o "achatamento" (flattening) que ignora as correlações entre as dimensões.

Embora a Decomposição de Valores Singulares (SVD) para tensores tenha avançado através do conceito de multiplicação de tensores baseada em mapas lineares (uma generalização do T-product), poucas outras decomposições matriciais clássicas foram estendidas para esse novo framework algébrico. O artigo busca preencher essa lacuna introduzindo a decomposição Tensor CUR dentro deste contexto.

2. Metodologia

A abordagem baseia-se na álgebra de tensores que mimetiza operações matriciais.

• Multiplicação $*_M$: Define-se a multiplicação de dois tensores $A$ e $B$ através de um mapa linear $M$. A operação é realizada transformando os tensores para um domínio via produto de modo-3 ($\times_3 M$), realizando o produto elemento a elemento (facewise product $\triangle$) e retornando ao domínio original usando o inverso (ou pseudoinverso) de $M$.
• Construção da Decomposição $*_M$-CUR:
  1. Selecionam-se conjuntos de índices de colunas ($J$) e linhas ($I$) para formar os tensores $C$ (colunas), $R$ (linhas) e $U$ (interseção).
  2. O tensor original $A$ é mapeado para o domínio $\text{b}A = A \times_3 M$.
  3. Em cada fatia frontal (frontal slice) do domínio transformado, aplica-se a decomposição CUR matricial clássica.
  4. A aproximação final é reconstruída no domínio original como: $A \approx C *_M U^+ *_M R$.
• Seleção de Índices: Para a aplicação prática, utiliza-se o método Q-DEIM (Q-Discrete Empirical Interpolation Method) para selecionar os índices de forma eficiente.

3. Principais Contribuições

• Extensão Algébrica: Introdução da decomposição CUR para o framework de multiplicação baseada em mapas lineares, cobrindo casos onde $M$ é invertível, sobrejetivo ou injetivo.
• Análise Teórica:
  • Condições de Exatidão: Demonstração de que, se $M$ for invertível e o multirank de $U$ for igual ao de $A$, a reconstrução é exata.
  • Análise de Perturbação: Estabelecimento de limites de erro que provam que a decomposição é robusta a pequenas perturbações nos dados originais.
• Versatilidade de Mapas: O método permite o uso de diferentes transformações (DCT, DFT, DST e mapas baseados em dados $U_3$), permitindo adaptar a decomposição à natureza do sinal.

4. Resultados Experimentais

O desempenho foi testado na tarefa de separação de primeiro plano e fundo (foreground-background separation) em vídeos.

• Métricas Quantitativas: Comparando com métodos como a decomposição robusta de matrizes, a decomposição BM (Bhattacharya–Messner) e a SS-SVD, o método $*_M$-CUR apresentou resultados competitivos ou superiores em métricas como PSNR (Relação Sinal-Ruído de Pico) e AGE (Erro de Nível de Cinza Médio).
• Qualidade Visual: As imagens de reconstrução do primeiro plano mostraram menos ruído visual e contornos de objetos mais nítidos do que os métodos de comparação.
• Eficiência Computacional: O método mostrou-se significativamente mais rápido que a decomposição BM, que pode ser de 50 a 500 vezes mais lenta.

5. Significância

Este trabalho é significativo por fornecer uma ferramenta poderosa para a análise de dados multidimensionais que preserva a estrutura intrínseca dos tensores de forma mais fiel que métodos tradicionais. Ao unificar a decomposição CUR com a álgebra de mapas lineares, os autores oferecem um método que é simultaneamente teoricamente robusto, computacionalmente eficiente e visualmente superior para aplicações de processamento de vídeo e compressão de dados.