Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization

Resumen Técnico: Estimación Robusta del Espacio Tangente mediante LEGO

Planteamiento del Problema
La estimación de los espacios tangentes de una variedad de datos es una tarea fundamental en el análisis de datos geométricos, que sustenta aplicaciones tales como el aprendizaje de variedades, la eliminación de ruido de datos, la detección de fronteras y la estimación de la dimensión intrínseca local. El enfoque estándar, el Análisis de Componentes Principales Local (LPCA), construye una matriz de covarianza local a partir de los $k$-vecinos más cercanos para identificar la base tangente. Sin embargo, el LPCA sufre un compromiso crítico con respecto al tamaño de la vecindad: las vecindades pequeñas son altamente susceptibles a la corrupción por ruido, mientras que las vecindades más grandes introducen sesgo debido a la curvatura subyacente y al alcance (reach) de la variedad. La selección de un tamaño de vecindad óptimo requiere típicamente conocimiento previo de las características geométricas y de ruido que a menudo no están disponibles, lo que convierte el problema en mal planteado en entornos de alto ruido.

Metodología: LEGO
Los autores proponen LEGO (Laplacian Eigenvector Gradient Orthogonalization), un método espectral que aprovecha la estructura global de los datos para guiar la estimación del espacio tangente local. En lugar de depender únicamente de vecindades locales, LEGO estima el espacio tangente en cada punto de datos mediante la ortogonalización de los gradientes de los autovectores de baja frecuencia del Laplaciano del grafo construido a partir de los datos ruidosos.

El algoritmo procede de la siguiente manera:

1. Construcción del Grafo: Se construye un Laplaciano de grafo $L$ a partir de la nube de puntos ruidosa utilizando métodos basados en núcleos (por ejemplo, paseo aleatorio, auto-ajustado o núcleos doblemente estocásticos).
2. Estimación del Gradiente: Se estiman los gradientes de los primeros $m$ autovectores de baja frecuencia ($\phi_1, \dots, \phi_m$) en cada punto de datos. Para asegurar la fidelidad local y la estabilidad numérica, estos gradientes se modelan como vectores en el subespacio generado por los primeros $m_0$ autovectores ($m_0 \gg m$).
3. Regularización: Se aplica un término de regularización de Tikhonov al proceso de estimación del gradiente para evitar la explosión numérica en configuraciones de bajo ruido o de rango deficiente. El parámetro de regularización $\eta_j$ se deriva de la geometría de la vecindad local, con un hiperparámetro $\beta$ que controla la potencia de la penalización por distancia.
4. Ortogonalización: En cada punto $j$, los vectores de gradiente estimados $\hat{\nabla}\phi(X_j)$ se ortogonalizan (vía SVD) para extraer la base ortonormal $Q_j$ del espacio tangente de dimensión $d$. Si la dimensión intrínseca $d$ es desconocida, esta se infiere a partir de los valores singulares de la matriz de gradiente.

Justificaciones Teóricas
El artículo proporciona dos marcos teóricos complementarios para justificar la robustez de LEGO:

1. Perspectiva de la Geometría Diferencial:
   Los autores modelan los datos ruidosos como muestras de un entorno tubular $T_{\epsilon r}$ que rodea una subvariedad limpia de dimensión $d$ ($B$). Analizan los autofunciones de Neumann del Laplaciano en este tubo.

   • Hallazgo Clave: Establecen cotas que muestran que el autovalor $\lambda$ de una autofunción escala como $\Omega(\epsilon^{-2} E^\perp_B(\phi))$ con respecto a su "energía vertical" (gradiente en la dirección del ruido) y como $O(E_B(\phi))$ con respecto a su "energía horizontal" (gradiente a lo largo de la variedad).
   • Implicación: Las autofunciones con gradientes significativos en la dirección del ruido deben tener autovalores altos. Por el contrario, las autofunciones de baja frecuencia tienen gradientes concentrados en el espacio horizontal (tangente), lo que hace que sus gradientes sean estimadores robustos del haz tangente.

2. Perspectiva de la Teoría de Matrices Aleatorias:
   Los autores analizan la estabilidad de los autovectores del Laplaciano bajo ruido sub-gaussiano utilizando un modelo de "información más ruido" donde la proxidad de la varianza del ruido $\epsilon$ escala como $O(1/\sqrt{n \log n})$.

   • Hallazgo Clave: Demuestran que el Laplaciano del grafo ruidoso converge al Laplaciano limpio en norma de operador a una tasa de $O(n^{-1/2})$. Según el teorema de Davis-Kahan, siempre que los brechas de autovalores (eigengaps) del Laplaciano limpio no decaigan demasiado rápido, los autovectores del Laplaciano ruidoso permanecen cercanos a los del limpio.
   • Implicación: Bajo estas condiciones, las componentes horizontales de los gradientes estimados a partir de datos ruidosos convergen a las de los datos limpios, asegurando la estabilidad de las estimaciones del espacio tangente.

Contribuciones Clave

• Propuesta Algorítmica: Introducción de LEGO, un algoritmo espectral para la estimación robusta del espacio tangente que evita el compromiso del tamaño de la vecindad inherente al LPCA.
• Marco Teórico: Derivación de leyes de escala asintótica para los gradientes de los autovectores bajo un modelo de ruido tubular y prueba de la estabilidad de los autovectores bajo perturbaciones de ruido sub-gaussiano.
• Guía de Hiperparámetros: Derivación teórica que sugiere $\beta = 1/2$ como el parámetro de regularización de Tikhonov óptimo cuando las características del ruido son desconocidas.
• Validación Empírica: Experimentos exhaustivos que demuestran la superioridad de LEGO sobre el LPCA en entornos ruidosos.

Resultados
Los experimentos numéricos en conjuntos de datos sintéticos (Swiss roll de alta relación de aspecto, toro truncado) y datos del mundo real (conjunto de datos Puppets) demuestran que:

• Precisión: LEGO produce estimaciones del espacio tangente significativamente más robustas al ruido que el LPCA. La discrepancia entre los espacios tangentes estimados y los reales (ground-truth) permanece baja incluso a medida que aumentan los niveles de ruido, mientras que las estimaciones de LPCA se degradan rápidamente.
• Desempeño en Tareas Derivadas: Las mejoras en las estimaciones del espacio tangente conducen a mejoras marcadas en tareas posteriores:
  • Aprendizaje de Variedades: LEGO produce incrustaciones (embeddings) de 2D precisas que preservan la topología intrínseca (por ejemplo, revelando la estructura toroidal del conjunto de datos Puppets), mientras que las incrustaciones basadas en LPCA colapsan o se vuelven no inyectivas.
  • Detección de Fronteras: Los puntos de frontera detectados mediante LEGO se alinean estrechamente con la verdad de campo, mientras que el LPCA falla en identificar las fronteras con precisión en condiciones de ruido.
  • Estimación de la Dimensión Intrínseca: LEGO concentra correctamente la varianza funcional en las dimensiones intrínsecas reales, mientras que el LPCA asigna erróneamente la varianza a las direcciones de ruido.

Significancia
El artículo afirma que LEGO ofrece una alternativa fundamentada a los métodos locales al utilizar información espectral global para filtrar el ruido. Al demostrar que los autovectores de baja frecuencia del Laplaciano del grafo se alinean naturalmente con el haz tangente de la variedad subyacente mientras suprimen los componentes de ruido, los autores proporcionan una solución robusta al problema de la selección del tamaño de la vecindad. Este enfoque permite un análisis geométrico preciso en regímenes de alto ruido donde los métodos locales estándar fallan, facilitando un aprendizaje de variedades y una reducción de dimensionalidad más fiables.