Una jerarquía de relajaciones convexas para la distancia de variación total

Información Básica

• ID del Artículo: 2401.01086
• Título: A hierarchy of convex relaxations for the total variation distance
• Autor: Jean B. Lasserre
• Clasificación: math.OC (Optimización y Control)
• Fecha de Publicación: Enero de 2024 (arXiv v3: 16 de octubre de 2025)
• Enlace del Artículo: https://arxiv.org/abs/2401.01086

Resumen

En este artículo se propone un esquema numérico para aproximar arbitrariamente con precisión la distancia de variación total entre dos medidas μ y ν que satisfacen la condición de Carleman. El esquema resuelve una serie de problemas de relajación convexa (jerárquicos) cuya secuencia de valores óptimos converge a la distancia de variación total, demostrando además la versatilidad de la jerarquía Moment-SOS. Cada relajación en la jerarquía es un problema de programación semidefinida cuyo tamaño aumenta con la cantidad de momentos involucrados, con soluciones óptimas —un par de pseudomomentos de grado 2n— que convergen a los momentos de la descomposición de Hahn-Jordan de μ-ν cuando n crece.

Antecedentes y Motivación de la Investigación

Importancia del Problema

El cálculo numérico de la distancia de variación total (Total Variation, TV) es un problema importante y desafiante con aplicaciones generalizadas en:

1. Pruebas Estadísticas: utilizadas en pruebas de homogeneidad e independencia
2. Optimización Robusta Distributiva: definición de conjuntos de incertidumbre
3. Ciencia de Datos y Aprendizaje Automático: medidas de distancia entre distribuciones

Limitaciones de los Métodos Existentes

1. Problemas de Estimadores Empíricos: los estimadores empíricos basados en muestras aleatorias suelen ser inconsistentes, particularmente para la distancia TV
2. Desafíos Computacionales: la distancia TV es equivalente a la distancia de Wasserstein con función de costo "desfavorable" c(x,y) = 1_{x≠y}, difícil de calcular eficientemente
3. Espacio Funcional Excesivamente Grande: el espacio de funciones medibles acotadas en la fórmula dual estándar es demasiado grande para evaluarse eficientemente
4. Restricciones de Soporte Compacto: los métodos existentes típicamente requieren soporte compacto

Motivación de la Investigación

Las contribuciones existentes se concentran principalmente en proporcionar límites analíticos para clases específicas de distribuciones, careciendo de un método numérico de propósito general. Este artículo tiene como objetivo proporcionar un esquema computacional práctico bajo supuestos relativamente débiles.

Contribuciones Principales

1. Esquema de Cálculo Numérico: propone una secuencia de relajaciones de programación semidefinida basada en la jerarquía Moment-SOS que puede aproximar la distancia TV con precisión arbitraria
2. Garantías Teóricas: demuestra la monotonía y convergencia de la secuencia de relajaciones, con valores óptimos convergiendo desde abajo a la verdadera distancia TV
3. Tratamiento de Soporte No Compacto: el método es aplicable a medidas con soporte no compacto, requiriendo solo la satisfacción de la condición de Carleman
4. Resolución Exacta de Casos Especiales: para medidas atómicas en el eje real, se obtiene solución exacta cuando el grado de relajación n ≥ maxm₁,m₂
5. Teoría Dual: proporciona programación semidefinida dual, revelando cómo fortalecer la fórmula dual clásica de distancia TV mediante restricción a polinomios y adición de términos de penalización

Detalles de la Metodología

Definición de la Tarea

Dadas dos medidas de Borel finitas μ, ν ∈ M(ℝᵈ)₊, calcular su distancia de variación total: $\|\mu - \nu\|_{TV} = \sup_f \left\{\int f d\mu - \int f d\nu : \|f\|_\infty \leq 1\right\}$

Supuestos Centrales

Supuesto 2.5:

1. Todos los momentos de μ y ν son finitos
2. μ y ν satisfacen la condición: $\int \exp(c|x_i|) d\mu < \infty$, para algún c > 0 y todo i = 1,...,d

Arquitectura del Método

1. Reconstrucción de Programación Lineal Infinidimensional

Reconstruir la distancia TV como LP infinidimensional: $\tau = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu\}$

2. Mejora de Restricciones Clave

Agregar restricciones de dominación para obtener el problema equivalente: $\rho = \inf_{\phi_+,\phi_- \in M(\mathbb{R}^d)_+} \{\phi_+(1) + \phi_-(1) : \phi_+ - \phi_- = \mu - \nu; \phi_+ \leq \mu; \phi_- \leq \nu\}$

3. Conversión de Condiciones de Momentos

Utilizando el Lema 2.2, las restricciones de dominación son equivalentes a condiciones de matrices de momentos: $\phi \leq \mu \Leftrightarrow M_n(\phi) \preceq M_n(\mu), \forall n \in \mathbb{N}$

4. Relajación de Programación Semidefinida

Problema de relajación en el nivel n: $\rho_n = \min_{\phi,\psi} \{\phi(1) + \psi(1) : \phi_\alpha - \psi_\alpha = \mu_\alpha - \nu_\alpha, \forall \alpha \in \mathbb{N}^d_{2n};$$0 \preceq M_n(\phi) \preceq M_n(\mu); 0 \preceq M_n(\psi) \preceq M_n(\nu)\}$

Puntos de Innovación Técnica

1. Papel Clave de las Restricciones de Dominación: aunque redundantes en la formulación infinidimensional, son extremadamente útiles como herramienta de compactificación en el esquema de relajación
2. Utilización Ingeniosa de la Condición de Carleman: garantiza la unicidad de la medida, haciendo que las restricciones de momentos sean equivalentes a las restricciones de dominación
3. Aparición Natural de la Descomposición de Hahn-Jordan: las soluciones óptimas convergen a la descomposición de Hahn-Jordan de μ-ν
4. Restricción Polinomial del Problema Dual: manejo de la restricción ‖f‖∞ ≤ 1 mediante restricción al espacio polinomial y adición de términos de penalización

Configuración Experimental

Herramientas de Implementación

• Software: GloptiPoly 3 para optimización polinomial
• Solucionador: SeDuMi 1.03 para programación semidefinida
• Plataforma: Portátil HP Elitebook Ubuntu 24

Casos de Prueba

1. Medidas Discretas

• Soportes disjuntos: X = {-1.0, 0.0, 1.0, 2.0}, Y = {-0.7, 0.3, 1.3, 2.3}
• Un punto común: X ∩ Y = {-1.0}
• Átomos cercanos: prueba de estabilidad numérica

2. Medidas Gaussianas

• Distribuciones gaussianas con diferentes medias y varianzas N(m₁,σ₁) y N(m₂,σ₂)
• Número de momentos de 2n = 4 a 2n = 8

Métricas de Evaluación

• Proximidad del valor óptimo de relajación ρₙ a la verdadera distancia TV
• Velocidad de convergencia y estabilidad numérica
• Tiempo computacional (todos los resultados completados en 0.35 segundos)

Resultados Experimentales

Resultados Principales

1. Verificación Teórica (Teorema 3.4)

Para medidas atómicas en el eje real, se obtiene solución exacta cuando n ≥ maxm₁,m₂:

• Ejemplo 1: μ = δ₀, ν = δₑ, ρ₁ = 2 (exacto)
• Ejemplo 2: cuatro átomos, un punto común, ρ₄ = 1.499 ≈ 1.5
• Ejemplo 3: átomos disjuntos, ρ₄ = 1.9999 ≈ 2

2. Resultados de Medidas Gaussianas

3. Hallazgos Importantes

• ρ₁ coincide completamente con los límites analíticos inferiores en la literatura 1
• Mejora significativa a partir de n=2, con resultados aún mejores en n=3,4
• Comportamiento cercano a medidas mutuamente singulares con varianza pequeña (distancia TV cercana a 2)

Análisis de Convergencia

Teorema 3.1 garantiza:

1. Cada relajación tiene solución óptima
2. ρₙ ↑ ‖μ-ν‖_ converge monótonamente
3. Las soluciones óptimas convergen a los momentos de la descomposición de Hahn-Jordan

Trabajos Relacionados

Direcciones Principales de Investigación

1. Estimadores Empíricos: estimación de distancia basada en muestras, aunque los estimadores de distancia TV suelen ser inconsistentes
2. Límites Analíticos: límites superiores e inferiores para clases específicas de distribuciones (como gaussianas de alta dimensión, mezclas gaussianas)
3. Métodos de Desigualdades: desigualdad de Pinsker, límites de distancia de Hellinger
4. Transporte Óptimo: algoritmos especializados para métrica de Kantorovich (como algoritmo de Sinkhorn)

Ventajas de Este Artículo

1. Generalidad: aplicable a medidas generales que satisfacen la condición de Carleman
2. Soporte No Compacto: no requiere soporte compacto
3. Convergencia Garantizada: garantía teórica de convergencia monótona
4. Practicidad: puede manejar tanto momentos de forma cerrada como momentos empíricos

Conclusiones y Discusión

Conclusiones Principales

1. Proporciona un esquema numérico de propósito general para el cálculo de distancia TV
2. Logra aproximación de precisión arbitraria bajo supuestos relativamente débiles
3. Cada relajación proporciona un límite inferior garantizado
4. Se obtiene solución exacta para medidas discretas

Limitaciones

1. Sensibilidad a la Dimensión: el método es sensible a la dimensión, actualmente limitado a problemas de baja dimensión
2. Limitaciones del Solucionador de Programación Semidefinida: no se puede esperar resolver problemas de relajación de alto grado
3. Precisión Numérica: pueden surgir problemas numéricos cuando los átomos están demasiado cercanos
4. Requisitos de Tamaño de Muestra: se requiere un tamaño de muestra suficientemente grande al usar momentos empíricos

Direcciones Futuras

1. Proporcionar límites inferiores alternativos computacionalmente más económicos
2. Extensión al tratamiento de problemas de alta dimensión
3. Mejora de la estabilidad numérica
4. Estudios comparativos con otras medidas de distancia

Evaluación Profunda

Fortalezas

1. Rigor Teórico: pruebas completas de convergencia y teoría dual
2. Novedad del Método: primera aplicación de la jerarquía Moment-SOS al cálculo de distancia TV
3. Valor Práctico: puede manejar datos tanto de forma cerrada como de muestras
4. Garantía de Exactitud: solución exacta para casos específicos (medidas atómicas)

Insuficiencias

1. Complejidad Computacional: la complejidad computacional de la programación semidefinida limita la escala de aplicación
2. Limitaciones Experimentales: pruebas principalmente en problemas de baja dimensión y distribuciones simples
3. Comparación Insuficiente con Métodos Existentes: falta comparación sistemática con otros métodos de cálculo de distancia TV

Impacto

1. Contribución Teórica: proporciona un nuevo marco teórico para el cálculo de distancia TV
2. Valor Metodológico: demuestra el potencial de la jerarquía Moment-SOS en el cálculo de medidas de probabilidad
3. Aplicación Práctica: proporciona nuevas herramientas para optimización robusta distributiva y otros campos

Escenarios Aplicables

1. Requisitos de Cálculo Exacto: necesidad de límites inferiores de distancia TV con garantía teórica
2. Problemas de Baja Dimensión: aplicaciones prácticas con dimensión relativamente baja
3. Distribuciones Especiales: gaussianas, distribuciones exponenciales y sus mezclas
4. Distribuciones Discretas: medidas atómicas con soporte finito

Referencias Bibliográficas

El artículo cita 28 referencias relacionadas, abarcando múltiples campos incluyendo transporte óptimo, teoría de momentos, programación semidefinida y medidas de probabilidad. En particular, los trabajos previos del autor sobre la jerarquía Moment-SOS 21,24,26 constituyen la base teórica de este artículo.