Defensa de tesis de maestría — Paula Cardoso

"Inferencia de Grafos a partir de Señales con restricciones de soporte"

Esta tesis se enmarca en el área de la inferencia de la topología de grafos latentes a partir de señales observadas, provenientes de dichos grafos. Consideramos el problema de inferencia conjunta de grafos distintos, pero bajo la hipótesis de que comparten el soporte.
Se estudia el modelo basado en el procesamiento de señales en grafos (Graph Signal Processing), en particular con la noción de suavidad de la señal calculada mediante la variación total y la matriz Laplaciana. Específicamente, en este modelo suponemos que las señales son generadas con distribución dada por $\mathcal{N}(0, L{\dagger})$ donde $L$ es la matriz Laplaciana del grafo. Kalofolias propone un método para inferir el grafo subyacente a partir de señales observadas, que minimiza la variación total e incluye regularizadores logarítmicos y de norma $l_2$ para evitar soluciones triviales y distribuir los pesos entre las aristas. En esta tesis se propone agregar a esta formulación un regularizador de tipo Group Lasso, para inferir conjuntamente varios grafos con una estructura común. Esta penalización por bloques fuerza a que las entradas homólogas de las matrices de adyacencia inferidas sean cero o no cero conjuntamente, promoviendo la esparcidad conjunta del soporte.
La formulación mencionada resulta en un problema de optimización convexo pero no diferenciable. Para resolver este problema se estudian herramientas de análisis convexo y optimización convexa no diferenciable. En particular, se estudian los métodos proximales y operadores promediados, y se desarrolla un algoritmo iterativo basado en una generalización del teorema de punto fijo, debido a Krasnosel'skii-Mann.
Finalmente, se evalúa el desempeño del método propuesto, demostrando que en el régimen usual de largos de señal menores que la cantidad de parámetros a inferir, la regularización propuesta mejora la inferencia en comparación con estimar cada grafo de forma independiente.