Tree-Adaptive Multiscale Kernel Lasso in Samplet Coordinates

Resumen Técnico: Lasso Multiescala Adaptativa a Árbol en Coordenadas de Samplet

1. Planteamiento del Problema

Los métodos basados en núcleos (kernel-based methods) son herramientas potentes para la aproximación de funciones a partir de datos dispersos, con aplicaciones en cuantificación de incertidumbre, optimización y aprendizaje automático. Sin embargo, su aplicabilidad a problemas a gran escala está limitada por dos factores críticos:

• Costo Computacional y Memoria: Las matrices de núcleo son densas y mal condicionadas, lo que hace que su ensamblaje y solución sean prohibitivos para grandes conjuntos de datos ($N$ grande).
• Complejidad de Datos Heterogéneos: Los datos dispersos a menudo exhiben estructuras multiescala y variabilidad local (singularidades), lo que requiere una densidad de puntos no uniforme para una representación eficiente.

El objetivo de este trabajo es desarrollar un marco unificado que combine la compresión de matrices de núcleo, la selección adaptativa de sitios de datos y la regresión dispersa para lograr reconstrucciones precisas con un costo computacional reducido.

2. Metodología Propuesta

El enfoque propuesto integra tres componentes principales en un marco cohesivo:

A. Compresión Basada en Samplets (Samplets)

• Se utiliza una representación de samplets, que forman un análisis de multiresolución de medidas discretas con signo.
• A diferencia de las wavelets clásicas, los samplets están diseñados específicamente para datos dispersos.
• Transforman la matriz de núcleo $K$ en una base donde la matriz resultante ($K_\Sigma$) es cuasi-dispersa para núcleos asintóticamente suaves.
• Esto permite comprimir la matriz a un número de entradas no nulas de orden $O(N \log N)$, manteniendo una precisión controlada mediante un umbral de admisibilidad.

B. Selección Adaptativa de Sitios de Datos (Tree-Adaptive Subsampling)

• Se introduce una estrategia para reducir el número de centros de datos antes de resolver el problema de regresión.
• Se define una energía local en un árbol de clusters jerárquico basado en la norma del espacio de Hilbert de núcleo reproducente (RKHS) nativo.
• Se comparan dos normas para la selección:
  • Norma $X'$ (Euclídea): Conservadora, distribuye puntos uniformemente.
  • Norma $H'$ (RKHS): Depende del núcleo, concentra puntos en regiones de alta energía y correlación (donde el núcleo es menos localizado).
• Mediante un recorrido de árbol de abajo hacia arriba (acumulación de energía) y de arriba hacia abajo (propagación), se identifica un subárbol de "alta energía". Se selecciona un único punto representativo por cada hoja de este subárbol, reduciendo drásticamente el tamaño del problema ($M \ll N$).

C. Formulación Lasso Multiescala y Solución Numérica

• Formulación: Se plantea un problema de mínimos cuadrados regularizado con $\ell_1$ (Lasso) en el dominio de los samplets. Esto fomenta soluciones dispersas y permite la selección automática de núcleos en configuraciones multiescala (multi-kernel).
  $$\min_{\beta} \frac{1}{2} \|Th - K_\Sigma \beta\|_2^2 + \sum w_i |\beta_i|$$
• Algoritmo de Solución: Se emplea un método de Newton Semisuave con Región de Confianza (TR-SSN) basado en una formulación de mapa normal.
• Estabilización: Para manejar el mal condicionamiento de las matrices de núcleo, se utiliza una actualización en línea de la SVD de rango bajo sobre el conjunto activo de coeficientes. Esto evita la formación de factorizaciones densas y mantiene la estabilidad numérica.
• Estrategia de Continuación: Se utiliza un bucle externo que reduce progresivamente el peso de la regularización $\ell_1$ para mejorar la robustez y la identificación de la dispersión.

3. Contribuciones Clave

1. Marco Unificado: Combina compresión de samplets, submuestreo adaptativo guiado por la energía del RKHS y regresión Lasso multiescala.
2. Eficiencia Computacional: Reduce el problema de $O(N^2)$ o $O(N^3)$ a escalas manejables mediante la compresión de la matriz y la reducción del número de centros de datos.
3. Selección Inteligente de Datos: La estrategia de submuestreo adaptativo no solo reduce el tamaño, sino que concentra los puntos en regiones de alta variabilidad y singularidad, capturando la complejidad intrínseca de los datos en lugar de su tamaño bruto.
4. Robustez Numérica: El uso de TR-SSN con SVD en línea permite resolver problemas mal condicionados sin sacrificar la precisión ni la velocidad de convergencia.
5. Selección Automática de Escalas: En entornos multi-kernel, la penalización $\ell_1$ selecciona automáticamente las longitudes de escala relevantes, eliminando la necesidad de ajuste manual de hiperparámetros para cada escala.

4. Resultados Numéricos

Los experimentos se realizaron en 2D y 3D con hasta $1.3 \times 10^6$ puntos de datos:

• Validación de Submuestreo: Se demostró que la selección basada en la norma $H'$ produce subconjuntos significativamente más pequeños que la norma $X'$, manteniendo o mejorando la precisión de reconstrucción al concentrarse en regiones críticas.
• Benchmark Multiescala (2D): En un problema con sumas de gaussianas de diferentes escalas, el enfoque de núcleo múltiple comprimido con samplets logró el menor error relativo ($\approx 5.5 \times 10^{-7}$) y la mayor dispersión (solo 10/720 coeficientes activos en el núcleo más fino), superando a los modelos de núcleo único denso.
• Reconstrucción 3D a Gran Escala (Stanford Bunny): Se aplicó el método a un problema de reflectancia en una nube de puntos de $1.3$ millones de vértices. El método redujo los centros a 5,127 y logró una reconstrucción precisa con una representación dispersa, demostrando escalabilidad a problemas 3D complejos.
• Eficiencia: Los experimentos mostraron que el enfoque logra reconstrucciones precisas con representaciones mucho más dispersas y una eficiencia computacional superior en comparación con métodos de escala única no adaptativos.

5. Significado e Impacto

Este trabajo representa un avance significativo en el tratamiento de problemas de aproximación de datos dispersos a gran escala. Al integrar la compresión algebraica (samplets) con la selección geométrica adaptativa (árboles de energía) y la optimización dispersa (Lasso), el método permite:

• Escalar métodos basados en núcleos a problemas que antes eran computacionalmente inviables.
• Manejar datos heterogéneos y multiescala de manera natural.
• Obtener modelos interpretables y compactos (soluciones dispersas) que capturan la física o la geometría subyacente de los datos sin el ruido de los puntos redundantes.

La metodología es particularmente relevante para aplicaciones en econometría financiera, dinámica de fluidos computacional y visualización científica, donde los datos son masivos, dispersos y poseen estructuras multiescala complejas.