Towards Scalable Persistence-Based Topological Optimization

Resumen Técnico: Hacia la Optimización Topológica Basada en Persistencia Escalable

Enunciado del Problema
La optimización topológica basada en persistencia busca deformar una nube de puntos $X \subset \mathbb{R}^d$ para minimizar objetivos de la forma $L(X) = \ell(\text{Dgm}(X))$, donde $\text{Dgm}(X)$ es un diagrama de persistencia. Aunque teóricamente sólida debido a la estabilidad de la homología persistente, la implementación práctica enfrenta dos cuellos de botella acoplados:

1. Necesidad de Muestreo: Calcular la homología persistente en nubes de puntos grandes es computacionalmente prohibitivo, lo que hace necesario el muestreo. Sin embargo, el muestreo uniforme estándar introduce un sesgo de densidad, a menudo sobremuestreando regiones densas mientras pasa por alto áreas de frontera escasas críticas para las características topológicas.
2. Escasez del Gradiente: El gradiente topológico es altamente disperso; solo un pequeño conjunto de puntos "ancla" (aquellos involucrados en símplices críticos de nacimiento/muerte) recibe actualizaciones no nulas. La mayoría de los puntos tienen gradientes cero, lo que ralentiza la optimización.
3. Escalabilidad del Suavizado: Un remedio reciente, la interpolación difeomórfica (Carrière et al., 2024), extiende los gradientes dispersos a un campo vectorial ambiental suave utilizando interpolación en Espacios de Hilbert de Núcleo Reproductivo (RKHS). Sin embargo, esto requiere resolver un sistema lineal de núcleo en cada iteración, lo que se vuelve dominante computacionalmente ($O(|I|^3)$) en configuraciones a gran escala.

Metodología
Los autores proponen una pipeline escalable que aborda tanto los problemas de muestreo como de extensión de gradientes mediante dos componentes principales:

1. Muestreo mediante Cortes Aleatorios:
   En lugar de un muestreo uniforme, los autores introducen un muestreador estructurado inspirado en el transporte óptimo cortado.

   • Mecanismo: En cada iteración, se extrae una dirección aleatoria $u$. Los puntos se proyectan sobre esta línea 1D ($t_i = \langle x_i, u \rangle$) y se ordenan. La submuestra se forma seleccionando puntos en rangos equidistantes en esta lista ordenada.
   • Beneficio: Esto asegura una cobertura geométrica global y mitiga el sesgo de densidad. Al imponer una estratificación de rangos, el método evita que los grupos densos monopolicen el presupuesto de muestra, garantizando que las regiones escasas (por ejemplo, fronteras entre grupos) estén consistentemente representadas.

2. Convolución Gaussiana de Nadaraya-Watson (NW):
   Para reemplazar el costoso sistema de resolución de núcleo RKHS, los autores proponen utilizar un estimador NW rápido para suavizar los gradientes de ancla dispersos en un campo vectorial global.

   • Mecanismo: Dados los puntos de ancla $x_i$ con gradientes $g_i$, el campo en cualquier punto $x$ se define como un promedio ponderado: $\bar{v}(x) = \sum_{i \in I} w_i(x) g_i$, donde los pesos $w_i(x)$ son afinidades gaussianas normalizadas $\exp(-\|x-x_i\|^2 / 2\sigma^2)$.
   • Ventajas:
     • Eficiencia Computacional: Evita resolver un sistema lineal, reduciendo significativamente el costo.
     • Comportamiento Geométrico: A diferencia de la interpolación RKHS, que utiliza núcleos no normalizados y puede hacer que la magnitud del campo desaparezca lejos de los anclajes, el suavizado NW impone una combinación convexa ($\sum w_i = 1$). Esto asegura que el campo permanezca no nulo y se comporte como un promedio baricéntrico local, proporcionando una propagación más robusta de señales dispersas a través del dominio.
   • Garantías Teóricas: El artículo proporciona límites sobre el error de aproximación de anclajes y establece continuidad Lipschitz global para el campo NW, mostrando que la constante Lipschitz escala con $1/\sigma^2$.

3. Aprendizaje Adaptativo del Ancho de Banda:
   Reconociendo que el parámetro de ancho de banda $\sigma$ impacta críticamente el rendimiento, los autores proponen aprender $\sigma$ en línea mediante retropropagación. Parametrizan $\sigma(\theta) = \sigma_0 \exp(\theta)$ y actualizan $\theta$ para minimizar una pérdida de anticipación, permitiendo que la escala de suavizado se adapte al régimen de optimización local.

Contribuciones Clave

• Cortes Aleatorios: Un esquema de muestreo ligero que mejora la cobertura geométrica y reduce el sesgo de densidad sin requerir agrupamiento ni muestreo de punto más lejano.
• Suavizado NW: Un reemplazo para la interpolación exacta de núcleos que ofrece una convolución gaussiana rápida y normalizada para extender gradientes topológicos dispersos, evitando resoluciones lineales de tiempo cúbico.
• Análisis Teórico: Pruebas de límites de aproximación de anclajes y estimaciones Lipschitz globales para el operador de suavizado NW.
• Validación Empírica: Demostración de aceleraciones y valores de objetivo mejorados en tareas 2D y 3D.

Resultados Experimentales
Los autores evaluaron su método en una tarea de aumento topológico 3D utilizando la nube de puntos de Stanford Bunny ($n \approx 36,000$), con el objetivo de fortalecer características topológicas 2D (cavidades).

• Líneas Base: Comparado contra (i) Descenso de gradiente disperso Vanilla (sin suavizado), (ii) Interpolación Difeomórfica Exacta de Núcleo y (iii) El método propuesto de Convolución NW.
• Rendimiento:
  • Valor del Objetivo: El método de Convolución NW logró una pérdida significativamente menor ($-0.01869$) en comparación con los métodos Vanilla ($-0.00026$) y de Núcleo ($-0.00151$).
  • Tiempo de Ejecución: El método NW mantuvo un tiempo de ejecución por época ($2.573$s) comparable a la línea base Vanilla ($2.044$s) y fue un orden de magnitud más rápido que el método de Núcleo ($19.979$s).
• Sensibilidad: Los experimentos en un círculo 2D ruidoso demostraron una alta sensibilidad al ancho de banda $\sigma$, motivando el uso de la estrategia de aprendizaje adaptativo propuesta.

Significado y Afirmaciones
El artículo afirma abordar un cuello de botella práctico central en la optimización basada en persistencia: la compensación entre la escasez de los gradientes topológicos y el costo computacional de suavizarlos. Al combinar cortes aleatorios con suavizado NW, los autores proporcionan una pipeline que es tanto escalable como efectiva.

Los autores mantienen un tono modesto respecto a su contribución. Declaran que su trabajo es principalmente un paso hacia hacer la optimización impulsada por persistencia más escalable y práctica para configuraciones que involucran grandes conjuntos de puntos y cálculos repetidos de PH. Señalan explícitamente que su evaluación actual se limita a benchmarks sintéticos controlados y de geometría estándar (Stanford Bunny, formas 2D) y que aún no demuestran un impacto de extremo a extremo en tareas del mundo real posteriores. El trabajo se posiciona como una mejora metodológica del propio bucle de optimización en lugar de un nuevo dominio de aplicación.