Uncertainty Principle for Vertex-Time Graph Signal Processing

Resumen Técnico: Principio de Incertidumbre para el Procesamiento de Señales en Grafos de Vértice-Tiempo

Planteamiento del Problema
Los marcos existentes de Procesamiento de Señales en Grafos (GSP, por sus siglas en inglés) se centran primordialmente en la localización dentro del dominio de los vértices o en el clásico dominio de tiempo-frecuencia. Si bien se han establecido principios de incertidumbre tanto para señales de grafos (vértice vs. espectral) como para señales de tiempo continuo (tiempo vs. frecuencia), carece de un marco unificado que aborde señales definidas sobre dominios irregulares de vértice-tiempo. Las aplicaciones del mundo real, como las redes de sensores y sociales, a menudo encuentran observaciones dispersas, irregulares o restringidas donde los sensores registran datos en intervalos desiguales, fallan intermitentemente o informan solo para subconjuntos de la red. Los métodos convencionales, tales como la Transformada de Fourier de Tiempo-Vértice de Tiempo Corto (STVFT) y la Transformada de Wavelet Espectral de Tiempo-Vértice (STVWT), dependen de bases fijas o supuestos de muestreo regulares, lo que los hace inadecuados para capturar la energía de la señal concentrada sobre subconjuntos de vértices e intervalos de tiempo irregulares o dependientes de los datos. Además, los métodos de aprendizaje de grafos existentes suelen ignorar los compromisos intrínsecos entre la localización de vértice y la espectral.

Metodología
El artículo propone un principio de incertidumbre generalizado para señales de grafos de vértice-tiempo que unifica los principios clásicos de tiempo-frecuencia y de incertidumbre de grafos. La metodología procede a través de los siguientes pasos:

1. Formulación Teórica:

   • Los autores definen una transformada de Fourier conjunta (JFT) para señales de vértice-tiempo $f: \mathcal{V} \times \mathcal{T} \to \mathbb{C}$, mapeando señales desde el dominio de vértice-tiempo al dominio espectral-frecuencial ($\Lambda \times \Omega$).
   • Introducen la dispersión de vértice-tiempo ($\alpha_{VT}$) y la dispersión espectral-frecuencial ($\beta_{SF}$) basadas en la concentración de energía sobre subespacios cerrados de $L^2(\mathcal{V} \times \mathcal{T})$ y $L^2(\Lambda \times \Omega)$, respectivamente.
   • El Teorema 1 establece el principio de incertidumbre, definiendo una región factible $\Theta$ para el par $(\alpha_{VT}, \beta_{SF})$. Esta región está acotada por el autovalor más grande del operador de composición $\Pi_{SF}\Pi_{VT}\Pi_{SF}$, donde $\Pi$ denota operadores de proyección ortogonal.
   • El artículo identifica las condiciones bajo las cuales las señales pueden lograr una localización perfecta en ambos dominios simultáneamente y caracteriza las señales que maximizan la concentración cuando la localización perfecta es imposible.

2. Aprendizaje de Diccionarios de Vértice-Tiempo (Reconstrucción de Señales):

   • Aprovechando el principio de incertidema, los autores diseñan un Diccionario de Concentración de Energía Conjunta (JECD).
   • Proponen dos construcciones específicas para los átomos del diccionario:
     • Subespacio de Soporte Limitado: Los átomos se construyen como productos tensoriales de autovectores de grafos localizados en un subconjunto de vértices $V'$ y Funciones Esferoidales Proladas de Sólidas (PSWFs) localizadas en un intervalo de tiempo $T'$. Los parámetros ($V'$, centro de tiempo $t_c$, duración $\ell$) se optimizan mediante un algoritmo codicioso y minimización alternante para maximizar la concentración de energía en los datos observados.
     • Subespacio de Núcleo de Calor Gaussiano: Los átomos se forman utilizando átomos de calor de grafo y núcleos gaussianos temporales. Las escalas de difusión ($\tau_v, \tau_t$) se seleccionan mediante una búsqueda de cuadrícula para maximizar una puntuación de concentración.
   • La reconstrucción de la señal se realiza resolviendo un problema de codificación dispersa utilizando el diccionario aprendido, acomodando datos irregulares y faltantes sin requerir el remuestreo.

3. Inferencia de la Topología del Grafo:

   • El artículo introduce un algoritmo de Aprendizaje de Grafos con Concentración de Energía (ECGL).
   • Este enfoque aprende el Laplaciano del grafo $L$ (y sus autovectores $U$) maximizando la concentración de energía espectral-frecuencial mientras respeta el compromiso de localización vértice-espectral dictado por el principio de incertidumbre.
   • La optimización estima conjuntamente la base de Fourier del grafo, los coeficientes dispersos y la matriz Laplaciana, incorporando regularización de variación total y restricciones para asegurar Laplacianos combinatorios válidos.

Contribuciones Clave

1. Principio de Incertidumbre Generalizado: La formulación de un principio de incertidumbre unificado para señales de grafos de vértice-tiempo que extiende las formulaciones existentes de grafos y de tiempo continuo a través de una medida de localización basada en subespacios.
2. Señales de Concentración Máxima: La identificación de una clase de señales de grafos de vértice-tiempo que logran la concentración máxima en ambos dominios de vértice-tiempo y espectral-frecuencial, sirviendo como átomos fundamentales para un nuevo diccionario.
3. Nuevo Marco de Reconstrucción: El desarrollo del método JECD, que aprende bases concentradas en la energía adaptadas a patrones de observación irregulares, mejorando la precisión de la reconstrucción bajo restricciones prácticas.
4. Enfoque de Aprendizaje de Grafos: La propuesta de ECGL, un método de inferencia de grafos que incorpora explícitamente los compromisos de localización del principio de incertidumbre para aprender topologías de grafos que se alinean con las estructuras intrínsecas de las señales.

Resultados Experimentales
Los autores validan su enfoque utilizando conjuntos de datos sintéticos y del mundo real:

• Reconstrucción de Señales: Experimentos con el conjunto de datos de COVID-19 de California (58 condados durante 2 años) y datos de flujo de tráfico muestran que JECD supera a los modelos de referencia (JFT, STVFT, STVWT y una extensión ingenua del principio de incertidumbre de grafos). JECD logra una ganancia promedio de 4 dB en la precisión de la reconstrucción y demuestra una robustez superior, manteniendo un rendimiento estable incluso con niveles de ruido tan bajos como 0 dB.
• Subespacio Gaussiano: En grafos sintéticos de Erdős-Rényi, la base de núcleo de calor gaussiano logró el menor Error Cuadrático Relativo (RSE) a través de varias Relaciones Señal-Ruido (SNR), superando a los métodos competidores incluso en regímenes de baja SNR.
• Inferencia de la Topología del Grafo: En un grafo sintético, ECGL superó a la Variación Total de Aprendizaje de Grafos (TV-GL) y al Aprendizaje de Grafos Asistido por la Señal Estimada (ESA-GL). ECGL logró un coeficiente de correlación más alto (0.9288 vs. ~0.927) entre los Laplacianos aprendidos y los reales e incrementó la recuperación de aristas en aproximadamente un 4.7%.

Significancia
El artículo afirma que su principal significancia radica en cerrar la brecha entre el análisis de tiempo-frecuencia clásico y el procesamiento de señales en grafos para escenarios de tiempo continuo e irregulares. Al caracterizar rigurosamente los compromisos entre la localización de vértice-tiempo y la espectral-frecuencial, el trabajo proporciona una base teórica para diseñar diccionarios que se adapten a soportes basados en datos en lugar de rejillas fijas. Esto es particularmente valioso para aplicaciones que involucran la recolección de datos intermitentes o asíncronos, como las redes de sensores, donde los métodos tradicionales fallan en capturar concentraciones de energía localizadas. Además, la integración del principio de incertidumbre en el aprendizaje de grafos ofrece una forma fundamentada de inferir estructuras de grafos que respetan las restricciones físicas o estructurales de las señales subyacentes.