Rápida aproximación espectral de grafos estructurados con aplicaciones a filtrado de grafos
Autores: Coutino, Mario; Chepuri, Sundeep Prabhakar; Maehara, Takanori; Leus, Geert
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Rápida aproximación espectral de grafos estructurados con aplicaciones a filtrado de grafos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Teoría de Fourier
Graficar la transformada de Fourier
Graficar frecuencias
Graficar modos
Descomposición espectral
Procesamiento de señales gráficas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 29
Citaciones: Sin citaciones
Para analizar y sintetizar señales en redes o grafos, la teoría de Fourier se ha extendido a dominios irregulares, lo que ha llevado a lo que se conoce como transformada de Fourier en grafos. Desafortunadamente, a diferencia de la transformada de Fourier tradicional, cada grafo exhibe una transformada de Fourier en grafo diferente. Por lo tanto, para analizar las propiedades del dominio de frecuencia del grafo de una señal de grafo, es necesario calcular los modos de Fourier en grafo y las frecuencias de grafo para el grafo en estudio. Aunque para encontrar estas frecuencias y modos de grafo, se requiere una costosa descomposición espectral del grafo, e incluso puede resultar prohibitiva, existen familias de grafos que tienen propiedades que podrían ser explotadas para una aproximación rápida del espectro del grafo. En este trabajo, nuestro objetivo es identificar estas familias y proporcionar un enfoque de dividir y conquistar para calcular una descomposición espectral aproximada del grafo. Utilizando la misma descomposición, se obtienen resultados sobre la reducción de la complejidad de la filtración de grafos. Estos resultados representan un intento de aprovechar las propiedades topológicas subyacentes de los grafos para idear modelos computacionales generales para el procesamiento de señales de grafo.
Descripción
Para analizar y sintetizar señales en redes o grafos, la teoría de Fourier se ha extendido a dominios irregulares, lo que ha llevado a lo que se conoce como transformada de Fourier en grafos. Desafortunadamente, a diferencia de la transformada de Fourier tradicional, cada grafo exhibe una transformada de Fourier en grafo diferente. Por lo tanto, para analizar las propiedades del dominio de frecuencia del grafo de una señal de grafo, es necesario calcular los modos de Fourier en grafo y las frecuencias de grafo para el grafo en estudio. Aunque para encontrar estas frecuencias y modos de grafo, se requiere una costosa descomposición espectral del grafo, e incluso puede resultar prohibitiva, existen familias de grafos que tienen propiedades que podrían ser explotadas para una aproximación rápida del espectro del grafo. En este trabajo, nuestro objetivo es identificar estas familias y proporcionar un enfoque de dividir y conquistar para calcular una descomposición espectral aproximada del grafo. Utilizando la misma descomposición, se obtienen resultados sobre la reducción de la complejidad de la filtración de grafos. Estos resultados representan un intento de aprovechar las propiedades topológicas subyacentes de los grafos para idear modelos computacionales generales para el procesamiento de señales de grafo.