Approximation theorems in bilipschitz invariant theory

Resumen Técnico: Aproximación de Invariantes Bilipschitz Óptimos mediante Filtros Máximos

1. Planteamiento del Problema

El artículo aborda el problema de la teoría de invariantes bilipschitz, que busca encontrar incrustaciones de baja distorsión de espacios de órbitas ($\mathbb{R}^d/G$) en espacios euclídeos ($\mathbb{R}^n$).

• Contexto: Dado un grupo finito $G \leq O(d)$ que actúa sobre $\mathbb{R}^d$, el espacio de órbitas $\mathbb{R}^d/G$ se equipara con una métrica de cociente. El objetivo es encontrar un mapa invariante bajo $G$, $f: \mathbb{R}^d \to \mathbb{R}^n$, tal que el mapa inducido $f_\downarrow: \mathbb{R}^d/G \to \mathbb{R}^n$ minimice la distorsión:
  $$\text{dist}(f_\downarrow) = \frac{\beta(f_\downarrow)}{\alpha(f_\downarrow)}$$
  donde $\alpha$ y $\beta$ son las constantes de Lipschitz inferior y superior, respectivamente. La distorsión mínima posible se conoce como la distorsión euclídea $c_2(\mathbb{R}^d/G)$.
• Estado del Arte: Se conocen las distorsiones óptimas exactas para solo tres casos:
  1. Rotaciones planas ($d=2$, subgrupos finitos de $SO(2)$).
  2. Recuperación de fase real ($G = \{\pm I\}$).
  3. Grupos de reflexión finitos.
• El Desafío: Aunque existen métodos universales como los bancos de filtros máximos (max filter banks) que garantizan la existencia de incrustaciones bilipschitz, su distorsión suele ser significativamente mayor que la óptima conocida. Por ejemplo, en el caso de la recuperación de fase, los filtros máximos tienen una distorsión infimal de $\approx 1.659$, mientras que la óptima es $\sqrt{2} \approx 1.414$.

2. Metodología y Enfoque Teórico

Los autores proponen que la distorsión óptima (o casi óptima) puede alcanzarse mediante la composición de un banco de filtros máximos con una transformación lineal.

• Hipótesis Central: La distorsión infimal de las transformaciones lineales de bancos de filtros máximos es igual a la distorsión euclídea del espacio de órbitas. Es decir, la "brecha" de los filtros máximos puros puede cerrarse post-componiendo con un mapa lineal cuidadosamente seleccionado.

• Estrategia de Prueba (Dos Pasos):

  1. Reducción a Inclusión de Espacios de Lipschitz: Demuestran que es suficiente mostrar que las funciones coordenadas de una incrustación bilipschitz óptima conocida residen en el cierre de Lipschitz del espacio generado por los filtros máximos. Si una función óptima $h$ puede aproximarse en norma de Lipschitz por combinaciones lineales de filtros máximos, entonces existe un mapa $f$ (composición de filtros y lineal) con distorsión arbitrariamente cercana a la de $h$.
  2. Demostración de la Inclusión: Proban que las funciones coordenadas óptimas de los tres casos mencionados pertenecen a este cierre, utilizando enfoques fundamentalmente diferentes para cada caso:
     • Rotaciones Planas y Recuperación de Fase: Utilizan análisis armónico (series de Fourier y armónicos esféricos) para expresar las funciones óptimas como combinaciones integrales de filtros máximos. Demuestran que estas integrales pueden aproximarse mediante sumas de Riemann (combinaciones lineales finitas) en la norma de Lipschitz.
     • Grupos de Reflexión: Utilizan la estructura algebraica específica de estos grupos. Demuestran que, en este caso, las funciones óptimas son exactamente combinaciones lineales de filtros máximos (sin necesidad de aproximación), debido a que el espacio generado por los filtros máximos tiene dimensión finita y coincide con el espacio de las funciones coordenadas óptimas.

• Análisis de Espacios Funcionales: El artículo introduce un análisis detallado de las relaciones de inclusión entre cuatro subespacios de funciones Lipschitz homogéneas positivas:

  1. Span de las funciones coordenadas óptimas.
  2. Extensión homogénea de polinomios invariantes ($ext\ P_G$).
  3. Span de los filtros máximos ($span\ M$).
  4. Funciones Lipschitz homogéneas a trozos invariantes ($PL^G_h$).
     Los autores muestran que estas relaciones varían drásticamente según el tipo de grupo, lo que impide una prueba unificada simple.

3. Contribuciones Clave

1. Teorema Principal (Teorema 3): Se prueba que para rotaciones planas, recuperación de fase real y grupos de reflexión, para cualquier $\epsilon > 0$, existe un banco de filtros máximos $\Phi$ y un mapa lineal $L$ tal que la composición $L \circ \Phi$ tiene una distorsión de a lo sumo $c_2(\mathbb{R}^d/G) + \epsilon$. En el caso de grupos de reflexión, la distorsión es exactamente óptima ($\epsilon=0$).
2. Nueva Perspectiva sobre la Reducción de Dimensionalidad: A diferencia de trabajos anteriores donde la reducción de dimensionalidad (post-composición lineal) se usaba solo para mantener la inyectividad ("no hace daño"), aquí se demuestra que la reducción de dimensionalidad es crucial para mejorar la distorsión ("ayuda").
3. Caracterización de la Aproximación: Se establece que las funciones óptimas no son necesariamente filtros máximos puros, sino que residen en su cierre de Lipschitz, lo que justifica teóricamente el uso de capas lineales posteriores en arquitecturas de aprendizaje profundo invariantes.
4. Resultados Numéricos: Se presentan experimentos que sugieren que este fenómeno se generaliza a otros grupos (como grupos simétricos $S_n$, grupos cíclicos $C_n$ y grupos ortogonales $O(d)$), donde las arquitecturas de "Filtro Máximo + Capa Lineal" (LMF) superan consistentemente a los filtros máximos puros y a las redes neuronales ReLU estándar en términos de distorsión empírica.

4. Resultados

• Casos Analíticos:
  • Rotaciones Planas ($d=2$): La distorsión óptima $r \sin(\pi/2r)$ se alcanza asintóticamente.
  • Recuperación de Fase ($G=\{\pm I\}$): La distorsión óptima $\sqrt{2}$ se alcanza asintóticamente.
  • Grupos de Reflexión: La distorsión óptima es $1$ (isometría), y se logra exactamente con una combinación lineal de filtros máximos.
• Experimentos Numéricos:
  • Se evaluaron múltiples configuraciones (polinomios invariantes, extensiones homogéneas, redes ReLU, bancos de filtros entrenados).
  • La arquitectura LMF (Max Filter Bank entrenado + Capa Lineal entrenada) logró consistentemente la distorsión empírica más baja en todos los casos probados, incluyendo conjuntos de datos complejos como distritos congresionales de EE. UU. y formas 2D.
  • En el caso de $\mathbb{R}^2/\{\pm I\}$, la arquitectura LMF acercó la distorsión a $1.42$ (cerca de $\sqrt{2} \approx 1.414$), superando significativamente a los filtros máximos puros ($\approx 1.66$).
  • La visualización de los datos (distritos congresionales y formas) mostró que la incrustación LMF preserva características geométricas relevantes (convexidad, excentricidad) de manera superior a otros métodos.

5. Significado e Impacto

• Teórico: El trabajo cierra la brecha entre la teoría de la distorsión óptima y las construcciones prácticas basadas en filtros máximos. Proporciona una justificación matemática rigurosa para el uso de capas lineales en la salida de redes invariantes a grupos.
• Práctico (Machine Learning): Sugiere que para el procesamiento de señales invariantes y el aprendizaje automático, la arquitectura óptima no es simplemente un banco de filtros, sino un banco de filtros seguido de una transformación lineal aprendida. Esto permite alcanzar límites teóricos de distorsión que antes se consideraban inalcanzables con métodos universales.
• Generalización: Aunque la prueba formal se limita a tres clases de grupos, los resultados numéricos y las preguntas abiertas planteadas sugieren que este principio podría ser universal para cualquier subgrupo cerrado de $O(d)$, abriendo nuevas direcciones de investigación en la teoría de invariantes y el diseño de arquitecturas de redes neuronales.

En resumen, el artículo demuestra que la combinación de filtros máximos (que capturan la estructura no lineal del espacio de órbitas) con una capa lineal (que optimiza la métrica euclídea resultante) es una estrategia poderosa y teóricamente fundamentada para lograr incrustaciones bilipschitz casi óptimas.