Approximation theorems in bilipschitz invariant theory

Título: Teoremas de Aproximação na Teoria Invariante Bilipschitz

Autores: Jameson Cahill, Joseph W. Iverson, Dustin G. Mixon e Nathan Willey.

1. O Problema

A teoria invariante bilipschitz preocupa-se com a construção de mergulhos (embeddings) de baixa distorção de espaços de órbitas em espaços euclidianos.

• Contexto: Dado um grupo finito $G \le O(d)$ agindo no espaço euclidiano $\mathbb{R}^d$, o espaço de órbitas $\mathbb{R}^d/G$ é formado pelas classes de equivalência $[x] = G \cdot x$.
• Objetivo: Encontrar um mapa invariante $f: \mathbb{R}^d \to \mathbb{R}^n$ tal que o mapa induzido $f_\downarrow: \mathbb{R}^d/G \to \mathbb{R}^n$ minimize a distorção bilipschitz. A distorção é definida como a razão entre a constante de Lipschitz superior ($\beta$) e a inferior ($\alpha$).
• Estado da Arte: Até o momento, os valores exatos da distorção euclidiana mínima ($c_2(\mathbb{R}^d/G)$) e os mapas que a alcançam são conhecidos apenas para três casos específicos:
  1. Rotações planares ($G \le SO(2)$).
  2. Recuperação de fase real ($G = \{\pm I\}$).
  3. Grupos de reflexão finitos.
• Desafio: Métodos universais, como "bancos de filtros máximos" (max filter banks), produzem mergulhos bilipschitz, mas frequentemente com uma distorção significativamente maior do que o ótimo teórico conhecido para esses casos específicos.

2. Metodologia

Os autores propõem uma abordagem universal baseada na composição de um banco de filtros máximos com uma transformação linear.

• Filtros Máximos (Max Filtering): Dado um template $y$, o filtro é definido como $\langle\langle [x], [y] \rangle\rangle = \max_{g \in G} \langle x, gy \rangle$. Um banco de filtros utiliza múltiplos templates para criar um mapa vetorial.
• Hipótese Central: A distorção mínima (ou próxima dela) pode ser alcançada pela composição $L \circ \Phi$, onde $\Phi$ é um banco de filtros máximos e $L$ é uma transformação linear.
• Estratégia de Prova:
  1. Redução a Espaços de Funções: O problema de minimizar a distorção é reduzido a demonstrar que as funções coordenadas de um mergulho bilipschitz ótimo residem no fecho de Lipschitz da extensão linear dos filtros máximos.
  2. Análise de Inclusão de Espaços: Os autores investigam a relação entre quatro subespaços de funções Lipschitz homogêneas positivas invariantes por $G$:
     • O espaço gerado pelas funções coordenadas do mergulho ótimo ($h$).
     • A extensão homogênea de polinômios invariantes na esfera.
     • O fecho de Lipschitz dos filtros máximos.
     • As funções lineares por partes (piecewise linear) invariantes.
  3. Técnicas Específicas por Caso:
     • Para rotações planares e recuperação de fase, utilizam análise harmônica (séries de Fourier e harmônicos esféricos) para expressar os mergulhos ótimos como combinações integrais de filtros máximos.
     • Para grupos de reflexão, exploram a estrutura geométrica das câmaras de Weyl e a finitude dimensional do espaço gerado pelos filtros máximos.

3. Principais Contribuições

1. Teorema Principal (Teorema 3): Para os três casos clássicos (rotações planares, recuperação de fase real e grupos de reflexão), prova-se que para qualquer $\epsilon > 0$, existe um banco de filtros máximos $\Phi$ e uma transformação linear $L$ tal que a distorção de $L \circ \Phi$ é no máximo $c_2(\mathbb{R}^d/G) + \epsilon$.

   • No caso de grupos de reflexão, a distorção exata é alcançada ($\epsilon=0$) com dimensão $m=d$.
   • Nos outros casos, a dimensão intermediária $m$ cresce à medida que $\epsilon \to 0$, mas a camada linear final realiza uma redução dimensional significativa.

2. Teorema de Inclusão de Espaços (Teorema 5): Estabelecem as relações de inclusão estrita ou igualdade entre os espaços de funções relevantes para cada caso:

   • Rotações Planas: O espaço ótimo está contido estritamente nos polinômios invariantes, que estão contidos estritamente no fecho dos filtros máximos.
   • Recuperação de Fase: O espaço ótimo está contido nos polinômios, que estão contidos nos filtros máximos, que estão contidos estritamente nas funções lineares por partes.
   • Grupos de Reflexão: O espaço ótimo é igual ao espaço gerado pelos filtros máximos (ambos iguais a um subespaço de dimensão finita).

3. Diferenciação de Abordagens: Demonstram que não existe uma prova unificada simples para os três casos, pois as interações entre os filtros máximos e outros espaços de funções (como polinômios ou funções lineares por partes) variam fundamentalmente entre os casos.

4. Resultados

• Teóricos:

  • Confirmam que a "diferença" (gap) entre a distorção dos bancos de filtros máximos puros e a distorção euclidiana ótima pode ser fechada (ou quase fechada) através de uma pós-composição linear.
  • Mostram que, ao contrário de teoremas anteriores que apenas garantiam a injetividade após redução de dimensão ("não faz mal"), este trabalho prova que a redução de dimensão via linearização ajuda a atingir a distorção ótima ("ajuda!").

• Numéricos:

  • Realizaram experimentos em diversos grupos (incluindo $S_5$, $C_5$, $O(2)$, e dados reais como distritos congressuais e formas 2D).
  • Compararam arquiteturas treinadas: Bancos de Filtros Máximos (MF), Camada Linear + Filtros Aleatórios (LRMF), Camada Linear + Filtros Treinados (LMF) e Redes Neurais ReLU.
  • Conclusão Numérica: O modelo LMF (Linear Layer + Max Filter Bank treinado) consistentemente atingiu a menor distorção empírica, aproximando-se ou igualando-se aos limites teóricos ótimos conhecidos, superando significativamente os filtros puros e as redes neurais padrão em termos de preservação de métrica invariante.

5. Significância

• Para Processamento de Sinais e Aprendizado de Máquina: O trabalho fornece uma justificativa teórica robusta para o uso de arquiteturas que combinam filtros de máxima invariância com camadas lineares. Isso é crucial para tarefas onde a simetria do grupo é fundamental (como visão computacional e processamento de sinais).
• Avanço Teórico: Resolve a questão de saber se os filtros máximos são suficientes para aproximar mergulhos ótimos, mostrando que, embora o espaço gerado por eles possa não conter o mapa ótimo diretamente, sua combinação com uma transformação linear é suficiente.
• Aplicações Práticas: Os resultados numéricos em dados reais (distritos congressuais e formas geométricas) sugerem que essa abordagem é viável e superior para aprender representações de baixa distorção em dados com simetrias de grupo complexas, oferecendo uma ferramenta prática para engenharia de características invariantes.

Em resumo, o artigo estabelece que a composição de filtros máximos com transformações lineares é uma estratégia universal e quase ótima para mergulhar espaços de órbitas em espaços euclidianos, unindo teoria de aproximação, análise harmônica e aprendizado de máquina.