Hispanopedia Wiki
Articulo de referencia

Transformada de Fourier gráfica

En matemáticas , la transformada de Fourier de grafos es una transformación matemática que descompone la matriz laplaciana de un grafo en valores y vectores propios . De forma a...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , la transformada de Fourier de grafos es una transformación matemática que descompone la matriz laplaciana de un grafo en valores y vectores propios . De forma análoga a la transformada de Fourier clásica , los valores propios representan frecuencias y los vectores propios forman lo que se conoce como una base de Fourier de grafos .

La transformada de Fourier de grafos es importante en la teoría espectral de grafos . Se aplica ampliamente en el estudio reciente de algoritmos de aprendizaje estructurados en grafos , como las redes neuronales convolucionales, ampliamente utilizadas .

Definición

Dado un grafo ponderado no dirigidoGRAMO=(V,mi){\displaystyle G=(V,E)}, dóndeV{\displaystyle V}es el conjunto de nodos con|V|=norte{\displaystyle |V|=N}(norte{\displaystyle N}siendo el número de nodos) ymi{\displaystyle E}es el conjunto de aristas, una señal gráficaF:V→R{\displaystyle f:V\rightarrow \mathbb {R} }es una función definida en los vértices del grafoGRAMO{\displaystyle G}La señalF{\displaystyle f}mapea cada vértice{vi}i=1,…,norte{\displaystyle \{v_{i}\}_{i=1,\ldots ,N}}a un número realF(i){\displaystyle f(i)}Cualquier señal gráfica puede proyectarse sobre los autovectores de la matriz laplaciana .L{\displaystyle L}. [ 1 ] Dejeλl{\displaystyle \lambda _{l}}yμl{\displaystyle \mu _{l}}ser ellel{\displaystyle l_{\text{th}}}autovalor y autovector de la matriz laplacianaL{\displaystyle L}(los valores propios están ordenados en orden ascendente, es decir,0=λ0≤λ1≤⋯≤λnorte−1{\displaystyle 0=\lambda _{0}\leq \lambda _{1}\leq \cdots \leq \lambda _{N-1}}[ 2 ] ), la transformada de Fourier gráfica (GFT)F^{\displaystyle {\hat {f}}}de una señal gráficaF{\displaystyle f}en los vértices deGRAMO{\displaystyle G}es la expansión deF{\displaystyle f}en términos de las funciones propias deL{\displaystyle L}. [ 3 ] Se define como: [ 1 ] [ 4 ]

GRAMOF[F](λl)=F^(λl)=⟨F,μl⟩=∑i=1norteF(i)μl∗(i),{\displaystyle {\mathcal {GF}}[f](\lambda _ {l})={\hat {f}}\left(\lambda _ {l}\right)=\langle f,\mu _ {l}\rangle =\sum _ {i=1}^{N}f(i)\mu _ {l}^{*}(i),}

dóndeμl∗=μlT{\displaystyle \mu _{l}^{*}=\mu _{l}^{\text{T}}}.

DesdeL{\displaystyle L}es una matriz simétrica real , sus autovectores{μl}l=0,⋯,norte−1{\displaystyle \{\mu _{l}\}_{l=0,\cdots ,N-1}}forman una base ortogonal . Por lo tanto, existe una transformada inversa de Fourier gráfica (IGFT), que se escribe como: [ 4 ]

IGRAMOF[F^](i)=F(i)=∑l=0norte−1F^(λl)μl(i){\displaystyle {\mathcal {I}}{\mathcal {G}}{\mathcal {F}}[{\hat {f}}](i)=f(i)=\sum _ {l=0}^{N-1}{\hat {f}}(\lambda _ {l})\mu _ {l}(i)}

De forma análoga a la transformada de Fourier clásica , la transformada de Fourier gráfica proporciona una manera de representar una señal en dos dominios diferentes: el dominio de los vértices y el dominio espectral del grafo . Cabe destacar que la definición de la transformada de Fourier gráfica y su inversa dependen de la elección de los autovectores laplacianos, que no son necesariamente únicos. [ 3 ] Los autovectores de la matriz laplaciana normalizada también constituyen una base posible para definir la transformada de Fourier gráfica directa e inversa.

Propiedades

La identidad de Parseval

La relación de Parseval se cumple para la transformada de Fourier del grafo, [ 5 ] es decir, para cualquierF,h∈Rnorte{\displaystyle f,h\in \mathbb {R} ^{N}}

⟨F,h⟩=⟨F^,h^⟩.{\displaystyle \langle f,h\rangle =\langle {\hat {f}},{\hat {h}}\rangle .}

Esto nos da la identidad de Parseval : [ 3 ]

∑i=1norte|F(i)|2=‖F‖22=⟨F,F⟩=⟨F^,F^⟩=‖F^‖22=∑l=0norte−1|F^(λl)|2.{\displaystyle \sum _{i=1}^{N}|f(i)|^{2}=\|f\|_{2}^{2}=\langle f,f\rangle =\langle {\hat {f}},{\hat {f}}\rangle =\|{\hat {f}}\|_{2}^{2}=\sum _{l=0}^{N-1}\left|{\hat {f}}\left(\lambda _{l}\right)\right|^{2}.}

Operador de convolución generalizado

La definición de convolución entre dos funcionesF{\displaystyle f}ygramo{\displaystyle g}no se puede aplicar directamente a señales de grafos, porque la traslación de la señal no está definida en el contexto de los grafos. [ 4 ] Sin embargo, al reemplazar el desplazamiento exponencial complejo en la transformada de Fourier clásica con los vectores propios laplacianos del grafo, la convolución de dos señales de grafo se puede definir como: [ 3 ]

(F∗gramo)=IGRAMOF[GRAMOF[F]⋅GRAMOF[gramo]],{\displaystyle (f*g)={\mathcal {I}}{\mathcal {G}}{\mathcal {F}}[{\mathcal {G}}{\mathcal {F}}[f]\cdot {\mathcal {G}}{\mathcal {F}}[g]],}
(F∗gramo)(i)=∑l=0norte−1F^(λl)gramo^(λl)μl(i).{\displaystyle (f*g)(i)=\sum _{l=0}^{N-1}{\hat {f}}(\lambda _{l}){\hat {g}}(\lambda _{l})\mu _{l}(i).}

Propiedades del operador de convolución

El operador de convolución generalizado satisface las siguientes propiedades: [ 3 ]

  • La convolución generalizada en el dominio de los vértices es una multiplicación en el dominio espectral del grafo:F∗gramo^=F^gramo^.{\displaystyle {\widehat {f*g}}={\hat {f}}{\hat {g}}.}
  • Conmutatividad :F∗gramo=gramo∗F{\displaystyle f*g=g*f}
  • Distributividad :F∗(gramo+h)=F∗gramo+F∗h{\displaystyle f*(g+h)=f*g+f*h}
  • Asociatividad :(F∗gramo)∗h=F∗(gramo∗h){\displaystyle (f*g)*h=f*(g*h)}
  • Asociatividad con multiplicación escalar :α(F∗gramo)=(αF)∗gramo=F∗(αgramo){\displaystyle \alpha (f*g)=(\alpha f)*g=f*(\alpha g)}, para cualquierα∈R{\displaystyle \alpha \in \mathbb {R} }.
  • Identidad multiplicativa :F∗gramo0=F{\displaystyle f*g_{0}=f}, dóndegramo0(i)=∑l=0norte−1μl(i){\displaystyle g_{0}(i)=\sum _{l=0}^{N-1}\mu _{l}(i)}es una identidad para el operador de convolución generalizado.
  • La suma de la convolución generalizada de dos señales es una constante multiplicada por el producto de las sumas de las dos señales:
∑i=1norte(F∗gramo)(i)=norteF^(0)gramo^(0)=1norte[∑i=1norteF(i)][∑i=1nortegramo(i)].{\displaystyle \sum _{i=1}^{N}(f*g)(i)={\sqrt {N}}{\hat {f}}(0){\hat {g}}(0)={\frac {1}{\sqrt {N}}}\left[\sum _{i=1}^{N}f(i)\right]\left[\sum _{i=1}^{N}g(i)\right].}

Operador de traducción generalizado

Como se indicó anteriormente, el operador de traslación clásicoTv{\displaystyle T_{v}}no se puede generalizar al entorno de grafos. Una forma de definir un operador de traslación generalizado es mediante una convolución generalizada con una función delta centrada en el vértice.norte{\displaystyle n}: [ 2 ](TnorteF)(i)=norte(F∗δnorte)(i)=norte∑l=0norte−1F^(λl)túl∗(norte)túl(i),{\displaystyle \left(T_{n}f\right)(i)={\sqrt {N}}\left(f*\delta _{n}\right)(i){=}{\sqrt {N}}\sum _{l=0}^{N-1}{\hat {f}}\left(\lambda _{l}\right)u_{l}^{*}(n)u_{l}(i),}

dóndeδi(norte)={1,si i=norte,0,de lo contrario.{\displaystyle \delta _{i}(n)={\begin{cases}1,&{\text{si }}i=n,\\0,&{\text{en otro caso.}}\end{cases}}}

La constante de normalizaciónnorte{\displaystyle {\sqrt {N}}}asegura que el operador de traslación preserve la media de la señal, [ 4 ] es decir,

∑i=1norte(TnorteF)(i)=∑i=1norteF(i).{\displaystyle \sum _{i=1}^{N}(T_{n}f)(i)=\sum _{i=1}^{N}f(i).}

Propiedades del operador de traslación

El operador de convolución generalizado satisface las siguientes propiedades: [ 3 ]

Para cualquierF,gramo∈Rnorte{\displaystyle f,g\in \mathbb {R} ^{N}}, yj,k∈{1,2,…,norte}{\displaystyle j,k\in \{1,2,\dots ,N\}},

  • Tj(F∗gramo)=(TjF)∗gramo=F∗(Tjgramo){\displaystyle T_{j}(f*g)=(T_{j}f)*g=f*(T_{j}g)}
  • TjTkF=TkTjF{\displaystyle T_{j}T_{k}f=T_{k}T_{j}f}
  • ∑i=1norte(TjF)(i)=norteF^(0)=∑i=1norteF(i){\displaystyle \sum _{i=1}^{N}(T_{j}f)(i)={\sqrt {N}}{\hat {f}}(0)=\sum _{i=1}^{N}f(i)}
  • ‖TjF‖≠‖F‖{\displaystyle \left\|T_{j}f\right\|\neq \|f\|}

Aplicaciones

Compresión de imágenes

La representación de señales en el dominio de la frecuencia es un enfoque común para la compresión de datos . Dado que las señales gráficas pueden ser dispersas en su dominio espectral, la transformada de Fourier gráfica también puede utilizarse para la compresión de imágenes . [ 6 ] [ 7 ]

Reducción de ruido gráfico

De forma similar a la reducción de ruido clásica de señales basada en la transformada de Fourier, se pueden diseñar filtros de grafos basados ​​en la transformada de Fourier de grafos para la eliminación de ruido en señales de grafos. [ 8 ]

Clasificación de datos

Dado que la transformada de Fourier de grafos permite definir la convolución en grafos, posibilita adaptar las redes neuronales convolucionales (CNN) convencionales para que funcionen con grafos. Los algoritmos de aprendizaje semisupervisado estructurados en grafos , como la red convolucional de grafos (GCN), pueden propagar las etiquetas de una señal de grafo a lo largo del grafo con un pequeño subconjunto de nodos etiquetados, operando teóricamente como una aproximación de primer orden de las convoluciones espectrales de grafos sin calcular el laplaciano del grafo ni su descomposición en valores propios. [ 9 ]

Caja de instrumento

GSPBOX [ 10 ] [ 11 ] es una caja de herramientas para el procesamiento de señales de gráficos, incluida la transformada de Fourier de gráficos. Admite los lenguajes Python y MATLAB .

Referencias

  1. 1 2 Ricaud, Benjamín; Borgnat, Pierre; Tremblay, Nicolás; Goncalves, Paulo; Vandergheynst, Pierre (1 de julio de 2019). "Fourier podría ser un científico de datos: de la transformada gráfica de Fourier al procesamiento de señales en gráficos" . Cuentas Rendus Physique . Fourier y la ciencia de hoy / Fourier et la science d'aujourd'hui. 20 (5): 474– 488. Bibcode : 2019CRPhy..20..474R . doi : 10.1016/j.crhy.2019.08.003 . ISSN 1631-0705 . 
  2. 1 2 Shuman, David I; Narang, Sunil K.; Frossard, Pascal; Ortega, Antonio; Vandergheynst, Pierre (mayo de 2013). "El campo emergente del procesamiento de señales en grafos: extendiendo el análisis de datos de alta dimensión a redes y otros dominios irregulares". IEEE Signal Processing Magazine . 30 (3): 83– 98. arXiv : 1211.0053 . Bibcode : 2013ISPM...30...83S . doi : 10.1109/MSP.2012.2235192 . ISSN 1558-0792 . S2CID 1594725 .  
  3. 1 2 3 4 5 6 Shuman, David I; Ricaud, Benjamin; Vandergheynst, Pierre (2016-03-01). "Análisis de frecuencia de vértices en grafos" . Applied and Computational Harmonic Analysis . 40 (2): 260– 291. arXiv : 1307.5708 . doi : 10.1016/j.acha.2015.02.005 . ISSN 1063-5203 . 
  4. ^ Nonato, Luis Gustavo ( 29 de agosto de 2017). "Transformada gráfica de Fourier" (PDF) .
  5. ↑ Hammond, David K.; Vandergheynst, Pierre; Gribonval, Rémi (2011-03-01). "Ondículas en grafos mediante la teoría espectral de grafos" . Análisis armónico aplicado y computacional . 30 (2): 129– 150. arXiv : 0912.3848 . doi : 10.1016/j.acha.2010.04.005 . ISSN 1063-5203 . S2CID 5593503 .  
  6. ↑ Sandryhaila, Aliaksei; Moura, Jose MF (mayo de 2013). "Procesamiento discreto de señales en grafos: Transformada de Fourier de grafos". 2013 IEEE International Conference on Acoustics, Speech and Signal Processing . IEEE. pp. 6167–6170 . doi : 10.1109/icassp.2013.6638850 . ISBN  978-1-4799-0356-6. S2CID 14704192 . 
  7. ↑ Hu, Wei; Cheung, Gene; Ortega, Antonio; Au, Oscar C. (enero de 2015). "Transformada de Fourier de grafos multirresolución para la compresión de imágenes suaves por partes". IEEE Transactions on Image Processing . 24 (1): 419– 433. Bibcode : 2015ITIP...24..419H . doi : 10.1109/TIP.2014.2378055 . ISSN 1941-0042 . PMID 25494508 . S2CID 9539186 .   
  8. ↑ Sandryhaila, Aliaksei; Moura, José MF (junio de 2014). "Procesamiento de señales discretas en grafos: análisis de frecuencia". IEEE Transactions on Signal Processing . 62 (12): 3042– 3054. arXiv : 1307.0468 . Bibcode : 2014ITSP...62.3042. . doi : 10.1109/TSP.2014.2321121 . ISSN 1941-0476 . S2CID 12110057 .  
  9. ↑ Kipf, Thomas N.; Welling, Max (22 de febrero de 2017). "Clasificación semisupervisada con redes neuronales convolucionales gráficas". arXiv : 1609.02907 [ cs.LG ].
  10. ^ Perraudin, Nathanaël; Paratte, Johan; Humano, David; Martín, Lionel; Kalofolias, Vassilis; Vandergheynst, Pierre; Hammond, David K. (15 de marzo de 2016). "GSPBOX: una caja de herramientas para el procesamiento de señales en gráficos". arXiv : 1408.5781 [ cs.IT ].
  11. ↑ "PyGSP: Procesamiento de señales gráficas en Python — Documentación de PyGSP 0.5.1" . pygsp.readthedocs.io . Consultado el 22 de junio de 2020 .
  • DeepGraphLibrary es un paquete gratuito de Python diseñado para la fácil implementación de redes neuronales gráficas.