Resumo Técnico: Completamento de Matriz Distribucional de Baixo Rank

Definição do Problema

Este artigo aborda o problema do completamento de matrizes distribucionais, uma generalização da clássica tarefa de completamento de matriz de baixo rank. Neste cenário, a matriz alvo $\rho^* \in \mathcal{P}(\mathcal{X})^{m_1 \times m_2}$ consiste em entradas que são distribuições de probabilidade sobre um domínio $\mathcal{X}$, em vez de valores escalares.

O modelo de observação é caracterizado por duas camadas de incompletude:

1. Observação Parcial: Apenas um subconjunto das entradas da matriz é observado, indicado por uma máscara binária $T(i,j)$.
2. Observação Indireta: Mesmo para as entradas observadas, a distribuição subjacente $\rho^*(i,j)$ não é acessível diretamente. Em vez disso, observa-se um conjunto finito de amostras i.i.d. $\{X^{(ij)}_1, \dots, X^{(ij)}_{N_{ij}}\}$ extraídas de $\rho^*(i,j)$, onde o tamanho da amostra $N_{ij}$ pode variar entre as entradas.

O objetivo é recuperar a matriz completa de valores distribuicionais $\rho^*$ (ou sua representação) a partir dessas observações parciais e indiretas. Este problema surge em aplicações como a modelagem da variabilidade do fluxo de tráfego entre localizações ou a análise da distribuição de previsões de lucros entre diferentes trimestres fiscais e instituições.

Metodologia

Embeddings Médios de Kernel (KME)

Para lidar com a natureza de dimensão infinita das distribuições de probabilidade e evitar restrições de variedade associadas a funções de densidade, os autores representam cada distribuição $\rho^*(i,j)$ via seu Kernel Mean Embedding (KME) em um Espaço de Hilbert Reproduzível (RKHS) $\mathcal{H}$:
$$\mu^*(i, j, \cdot) = \mathbb{E}_{X \sim \rho^*(i,j)} [K(X, \cdot)] \in \mathcal{H}$$
Recuperar $\rho^*$ é equivalente a recuperar a matriz de KME $\mu^* \in \mathcal{H}^{m_1 \times m_2}$. A distância entre distribuições é medida usando a Discrepância de Médio Máximo (MMD).

Modelagem de Baixo Rank via Desdobramento Funcional

Os autores propõem uma estrutura de rank de Tucker para a matriz distribicional. Eles visualizam $\mu^*$ como um tensor de três vias no espaço $\mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H}$. Como $\mathcal{H}$ é frequentemente de dimensão infinita, as definições padrão de rank de tensor não se aplicam diretamente.

Para resolver isso, o artigo introduz operadores de desdobramento funcional ($U_1, U_2, U_3$) que mapeiam o tensor em produtos de dois espaços (ex: $U_1: \mathbb{R}^{m_1} \otimes \mathbb{R}^{m_2} \otimes \mathcal{H} \to \mathbb{R}^{m_1} \otimes (\mathbb{R}^{m_2} \otimes \mathcal{H})$). Esses operadores induzem operadores lineares cujos ranks definem o rank multilinear $(r_1, r_2, r_3)$.

• Implicação Estrutural: Um baixo rank multilinear implica que os componentes funcionais dos KMEs residem em um subespaço de baixa dimensão, e as matrizes de funcionais de expectativa associados (ex: matrizes de média) são de baixo rank.

Estrutura de Estimação

Os autores propõem um estimador M regularizado $\hat{\mu}$ definido pela minimização de uma função de perda somada a uma penalidade de norma nuclear:
$$\hat{\mu} = \arg\min_{\mu} \left[ \frac{1}{m_1 m_2} \sum_{(i,j): T(i,j)=1} \left\| \mu(i, j, \cdot) - \hat{\mu}_{emp}(i, j, \cdot) \right\|_{\mathcal{H}}^2 + \lambda \Psi(\mu) \right]$$

• Termo de Perda: A MMD ao quadrado entre o KME estimado e o KME empírico derivado das amostras observadas.
• Regularização: $\Psi(\mu) = \sum_{j=1}^3 \beta_j \|U_j \mu\|_*$, onde $\|\cdot\|_*$ denota a norma nuclear do operador linear induzido. Isso promove o baixo rank em todas as três vias.

Solução Computacional

Apesar da natureza de dimensão infinita de $\mathcal{H}$, o Teorema do Representante garante que a solução $\hat{\mu}$ reside no subespaço de dimensão finita das funções de kernel observadas.

1. O problema é reparametrizado em um problema de otimização de tensor de dimensão finita sobre um tensor de coeficientes $B \in \mathbb{R}^{m_1 \times m_2 \times \tilde{N}}$.
2. Para lidar com grandes tamanhos de amostra, os autores sugerem aproximar a matriz de Gram usando técnicas de aproximação de kernel (ex: método Nyström ou Random Fourier Features).
3. A otimização é resolvida usando um método de Alternating Direction Method of Multipliers (ADMM) acelerado.

Principais Contribuições

1. Formulação de Problema Inovadora: O artigo formaliza o completamento de matrizes para entradas com valores distribuicionais, abordando o desafio de recuperar distribuições a partir de dados amostrais parciais e ruidosos.
2. Estrutura Teórica: Introduz uma definição de rank de Tucker para tensores de valores distribuicionais usando operadores de desdobramento funcional, unindo a lacuna entre dados funcionais de dimensão infinita e análise de tensores de dimensão finita.
3. Inovação Algorítmica: O estimador proposto utiliza regularização de norma nuclear em operadores lineares induzidos. Crucialmente, os autores provam que a solução admite uma representação de dimensão finita, tornando o problema computacionalmente tratável via otimização convexa.
4. Garantias Estatísticas: O artigo estabelece limites de erro não assintóticos para a MMD quadrada agregada.
   • A taxa de convergência coincide com a do completamento de matriz clássico regularizado por norma nuclear para matrizes escalares.
   • Ao contrário das abordagens de vizinhos mais próximos existentes (ex: Feitelberg et al., 2024), a consistência do método proposto não exige que o número de amostras por entrada ($N_{ij}$) divirja. Em vez disso, a consistência é alcançada conforme as dimensões da matriz ($m_1, m_2$) crescem, aproveitando a estrutura de baixo rank global para o compartilhamento de informações.

Resultados Experimentais

Dados Sintéticos

• Configuração: Matrizes simuladas com distribuições de mistura Gaussiana. As comparações foram feitas contra um método de vizinho mais próximo (NN) (Feitelberg et al., 2024) e o completamento de matriz clássico (SOFTIMPUTE) aplicado a médias/variâncias amostrais.
• Descobertas:
  • O método proposto (LRKME) superou consistentemente o método NN tanto em entradas observadas quanto não observadas, particularmente na estimativa de variância e estatísticas de ordem superior.
  • O LRKME também superou o SOFTIMPUTE, demonstrando a vantagem de utilizar informações distribuicionais completas em vez de apenas resumos escalares.
  • Em configurações 2D, o método NN foi excluído devido à intratabilidade computacional de distâncias de Wasserstein multivariadas, enquanto o LRKME permaneceu eficaz.

Aplicação no Mundo Real

• Conjunto de Dados: Dados de viagens de táxi de NYC, modelando a distribuição de contagens diárias de viagens entre 265 locais de origem e destino.
• Desafio: Alta taxa de ausência (>39%) e tamanhos de amostra altamente variáveis por entrada (1 a 3672).
• Descobertas: O LRKME alcançou um erro relativo empírico significativamente menor (0.0015) comparado ao método NN (0.0212) no conjunto de teste. A inspeção visual de casos específicos mostrou que o LRKME captura melhor distribuições de cauda pesada e padrões de concentração em comparação com o estimador NN.

Significância e Alegações

O artigo afirma fornecer o primeiro método para o completamento de matrizes distribuicionais que:

1. Acomoda padrões de observação gerais com tamanhos de amostra variáveis.
2. Estende-se naturalmente para distribuições multidimensionais sem os gargalos computacionais de métodos baseados em Wasserstein.
3. Oferece garantias de consistência global que não dependem do crescimento assintótico das amostras por entrada, baseando-se, em vez disso, na estrutura de baixo rank da matriz.
4. Fornece uma solução computacionalmente eficiente via representação de dimensão finita e otimização convexa.

Os autores posicionam seu trabalho como um passo significativo à frente das abordagens de vizinhos mais próximos existentes, oferecendo um framework mais robusto, teoricamente fundamentado e escalável para imputar dados distribuicionais ausentes.