Hispanopedia Wiki
Articulo de referencia

Procesamiento algebraico de señales

El procesamiento algebraico de señales (PAS) es un área emergente del procesamiento teórico de señales (PS). En la teoría algebraica del procesamiento de señales, un conjunto de...

Hispanopedia WikiContenido en espanolLectura gratuita

El procesamiento algebraico de señales (PAS) es un área emergente del procesamiento teórico de señales (PS). En la teoría algebraica del procesamiento de señales, un conjunto de filtros se trata como un álgebra (abstracta) , un conjunto de señales como un módulo o espacio vectorial , y la convolución como una representación algebraica . La ventaja del procesamiento algebraico de señales radica en su generalidad y portabilidad.

Historia

En la formulación original del procesamiento de señales algebraicas de Puschel y Moura, las señales se recogen en unA{\displaystyle {\mathcal {A}}}-módulo para alguna álgebraA{\displaystyle {\mathcal {A}}}de filtros, y el filtrado viene dado por la acción deA{\displaystyle {\mathcal {A}}}en elA{\displaystyle {\mathcal {A}}}-módulo. [ 1 ]

Definiciones

DejarK{\displaystyle K}ser un campo , por ejemplo los números complejos, yA{\displaystyle {\mathcal {A}}}ser unK{\displaystyle K}-álgebra (es decir, un espacio vectorial sobreK{\displaystyle K}con una operación binaria∗:A⊗A→A{\displaystyle \ast :{\mathcal {A}}\otimes {\mathcal {A}}\to {\mathcal {A}}} que es lineal en ambos argumentos) tratado como un conjunto de filtros. SupongamosMETRO{\displaystyle {\mathcal {M}}}es un espacio vectorial que representa un conjunto de señales. Una representación deA{\displaystyle {\mathcal {A}}}consiste en un homomorfismo de álgebraρ:A→minorted(METRO){\displaystyle \rho :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})} dondeminorted(METRO){\displaystyle \mathrm {End} ({\mathcal {M}})}es el álgebra de las transformaciones linealesT:METRO→METRO{\displaystyle T:{\mathcal {M}}\to {\mathcal {M}}}con composición (equivalente, en el caso de dimensión finita, a la multiplicación de matrices ). Para mayor comodidad, escribimosρa{\displaystyle \rho _{a}}para el endomorfismoρ(a){\displaystyle \rho (a)}. Ser un homomorfismo de álgebra,ρ{\displaystyle \rho }No solo debe ser una transformación lineal, sino que también debe satisfacer la propiedadρa∗b=ρb∘ρa∀a,b∈A{\displaystyle \rho _{a\ast b}=\rho _{b}\circ \rho _{a}\quad \forall a,b\in {\mathcal {A}}}Dada una señalincógnita∈METRO{\displaystyle x\in {\mathcal {M}}}, convolución de la señal mediante un filtroa∈A{\displaystyle a\in {\mathcal {A}}}produce una nueva señalρa(incógnita){\displaystyle \rho _{a}(x)}. Se necesita terminología adicional de la teoría de representación de álgebras. Un subconjuntoGRAMO⊆A{\displaystyle {\mathcal {G}}\subseteq {\mathcal {A}}}Se dice que genera el álgebra si cada elemento deA{\displaystyle {\mathcal {A}}}pueden representarse como polinomios en los elementos deGRAMO{\displaystyle {\mathcal {G}}}La imagen de un generadorgramo∈GRAMO{\displaystyle g\in {\mathcal {G}}}se denomina operador de desplazamiento . En prácticamente todos los ejemplos, las convoluciones se forman como polinomios enminorted(METRO){\displaystyle \mathrm {End} ({\mathcal {M}})}generado por operadores de desplazamiento. Sin embargo, esto no es necesariamente así para una representación de un álgebra arbitraria.

Ejemplos

Procesamiento de señales discretas

En el procesamiento de señales discretas (DSP), el espacio de señales es el conjunto de funciones de valor complejo.METRO=L2(Z){\displaystyle {\mathcal {M}}={\mathcal {L}}^{2}(\mathbb {Z} )}con energía acotada (es decir, funciones de cuadrado integrable ). Esto significa la serie infinita∑norte=−∞∞|(incógnita)norte|<∞{\displaystyle \sum _{n=-\infty }^{\infty }|(x)_{n}|<\infty }dónde|⋅|{\displaystyle |\cdot |}es el módulo de un número complejo . El operador de desplazamiento viene dado por el endomorfismo lineal.(Sincógnita)norte=(incógnita)norte−1{\displaystyle (Sx)_{n}=(x)_{n-1}}El espacio de filtros es el álgebra de polinomios con coeficientes complejos.A=do[z−1,z]{\displaystyle {\mathcal {A}}=\mathbb {C} [z^{-1},z]}y la convolución viene dada por ρh=∑k=−∞∞hkSk{\displaystyle \rho _{h}=\sum _{k=-\infty }^{\infty }h_{k}S^{k}}dóndeh(t)=∑k=−∞∞hkzk{\displaystyle h(t)=\sum _{k=-\infty }^{\infty }h_{k}z^{k}}es un elemento del álgebra. Filtrar una señal porh{\displaystyle h}, entonces produce(y)norte=∑k=−∞∞hkincógnitanorte−k{\displaystyle (y)_{n}=\sum _{k=-\infty }^{\infty }h_{k}x_{n-k}}porque(Skincógnita)norte=(incógnita)norte−k{\displaystyle (S^{k}x)_{n}=(x)_{n-k}}.

Procesamiento de señales gráficas

Un grafo ponderado es un grafo no dirigido.GRAMO=(V,mi){\displaystyle {\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})}con pseudométrica en el conjunto de nodosV{\displaystyle {\mathcal {V}}}escritoaij{\displaystyle a_{ij}}Una señal gráfica es simplemente una función de valor real en el conjunto de nodos del grafo. En las redes neuronales gráficas, las señales gráficas a veces se denominan características. El espacio de señales es el conjunto de todas las señales gráficas.METRO=RV{\displaystyle {\mathcal {M}}=\mathbb {R} ^{\mathcal {V}}}dóndeV{\displaystyle {\mathcal {V}}}es un conjunto denorte=|V|{\displaystyle n=|{\mathcal {V}}|}nodos enGRAMO=(V,mi){\displaystyle {\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})}El álgebra de filtros es el álgebra de polinomios en una indeterminadaA=R[t]{\displaystyle {\mathcal {A}}=\mathbb {R} [t]}. Existen algunas opciones posibles para un operador de desplazamiento de grafos (GSO). La matriz de adyacencia ponderada (no) normalizada de[A]ij=aij{\displaystyle [A]_{ij}=a_{ij}}es una opción popular, al igual que el laplaciano de grafos (no) normalizado.[L]ij={∑j=1norteaiji=j−aiji≠j{\displaystyle [L]_{ij}={\begin{cases}\sum _{j=1}^{n}a_{ij}&i=j\\-a_{ij}&i\neq j\end{cases}}}La elección depende de consideraciones de rendimiento y diseño. SiS{\displaystyle S}es el GSO, entonces una convolución gráfica es la transformación lineal ρh=∑k=0∞hkSk{\displaystyle \rho _{h}=\sum _{k=0}^{\infty }h_{k}S^{k}}para algunosh(t)=∑k=0∞hkzk{\displaystyle h(t)=\sum _{k=0}^{\infty }h_{k}z^{k}}y convolución de una señal gráficaincógnita:V→R{\displaystyle \mathbf {x} :{\mathcal {V}}\to \mathbb {R} } mediante un filtroh(t){\displaystyle h(t)}genera una nueva señal gráficay=(∑k=0∞hkSk)⋅incógnita{\displaystyle \mathbf {y} =\left(\sum _{k=0}^{\infty }h_{k}S^{k}\right)\cdot \mathbf {x} }.

Otros ejemplos

Otros objetos matemáticos con sus propios marcos de procesamiento de señales propuestos son los modelos de señales algebraicas. Estos objetos incluyen carcajes , [ 2 ] grafones , [ 3 ] semirretículos , [ 4 ] grupos finitos y grupos de Lie , [ 5 ] y otros.

Mapas entrelazados

En el marco de la teoría de la representación , las relaciones entre dos representaciones de la misma álgebra se describen con mapas entrelazados que, en el contexto del procesamiento de señales, se traducen en transformaciones de señales que respetan la estructura del álgebra. Supongamos queρ:A→minorted(METRO){\displaystyle \rho :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})} yρ′:A→minorted(METRO′){\displaystyle \rho ':{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}}')}son dos representaciones diferentes deA{\displaystyle {\mathcal {A}}}Un mapa entrelazado es una transformación lineal .α:METRO→METRO′{\displaystyle \alpha :{\mathcal {M}}\to {\mathcal {M}}'} tal que

α∘ρa=ρa′∘α∀a∈A{\displaystyle \alpha \circ \rho _{a}=\rho '_{a}\circ \alpha \quad \forall a\in {\mathcal {A}}}

Intuitivamente, esto significa que filtrar una señal pora{\displaystyle a}luego transformándolo conα{\displaystyle \alpha }es equivalente a transformar primero una señal conα{\displaystyle \alpha }, luego filtrando pora{\displaystyle a}. La transformación z [ 1 ] es un ejemplo prototípico de un mapa entrelazado.

Redes neuronales algebraicas

Inspirados por una perspectiva reciente que sostiene que las arquitecturas populares de redes neuronales gráficas (GNN) son en realidad redes neuronales convolucionales (CNN), [ 6 ] el trabajo reciente se ha centrado en desarrollar nuevas arquitecturas de redes neuronales desde el punto de vista algebraico. [ 7 ] [ 8 ] Una red neuronal algebraica es una composición de convoluciones algebraicas, posiblemente con múltiples características y agregaciones de características, y no linealidades.

Referencias

  1. 1 2 Puschel, M.; Moura, J. (2008). "Teoría del procesamiento de señales algebraicas: fundamentos y tiempo unidimensional". IEEE Transactions on Signal Processing . 56 (8): 3572– 3585. arXiv : cs/0612077 . Bibcode : 2008ITSP...56.3572P . doi : 10.1109/TSP.2008.925261 . ISSN 1053-587X . S2CID 206797175 .  
  2. ↑ Parada-Mayorga, Alejandro; Riess, Hans; Ribeiro, Alejandro; Ghrist, Robert (22 de octubre de 2020). "Procesamiento de señales de carcaj (QSP)". arXiv : 2010.11525 [ eess.SP ].
  3. ↑ Ruiz, Luana; Chamon, Luiz FO; Ribeiro, Alejandro (2021). "Procesamiento de señales de grafón". Transacciones IEEE sobre procesamiento de señales . 69 : 4961–4976 . arXiv : 2003.05030 . Código Bib : 2021ITSP...69.4961R . doi : 10.1109/TSP.2021.3106857 . ISSN 1053-587X . S2CID 212657497 .  
  4. ↑ Puschel, Markus; Seifert, Bastian; Wendler, Chris (2021). "Procesamiento de señales discretas en redes de encuentro/unión". IEEE Transactions on Signal Processing . 69 : 3571– 3584. arXiv : 2012.04358 . Bibcode : 2021ITSP...69.3571P . doi : 10.1109/TSP.2021.3081036 . ISSN 1053-587X . S2CID 227736440 .  
  5. ↑ Bernardini, Riccardo; Rinaldo, Roberto (2021). "Desmitificando los métodos de grupos de Lie para el procesamiento de señales: un tutorial". IEEE Signal Processing Magazine . 38 (2): 45– 64. Bibcode : 2021ISPM...38b..45B . doi : 10.1109/MSP.2020.3023540 . ISSN 1053-5888 . S2CID 232071730 .  
  6. ↑ Gama, Fernando; Isufi, Elvin; Leus, Geert; Ribeiro, Alejandro (2020). "Grafos, convoluciones y redes neuronales: de filtros de grafos a redes neuronales de grafos". IEEE Signal Processing Magazine . 37 (6): 128– 138. arXiv : 2003.03777 . Bibcode : 2020ISPM...37f.128G . doi : 10.1109/MSP.2020.3016143 . ISSN 1053-5888 . S2CID 226292855 .  
  7. ↑ Parada-Mayorga, Alejandro; Ribeiro, Alejandro (2021). "Redes neuronales algebraicas: estabilidad ante deformaciones". IEEE Transactions on Signal Processing . 69 : 3351–3366 . arXiv : 2009.01433 . Bibcode : 2021ITSP...69.3351P . doi : 10.1109/TSP.2021.3084537 . ISSN 1053-587X . S2CID 221517145 .  
  8. ↑ Parada-Mayorga, Alejandro; Butler, Landon; Ribeiro, Alejandro (2023). "Filtrado convolucional y redes neuronales con álgebras no conmutativas". IEEE Transactions on Signal Processing . 71 : 2683. arXiv : 2108.09923 . Bibcode : 2023ITSP...71.2683P . doi : 10.1109/TSP.2023.3293716 .
  • Proyecto inteligente: Teoría algebraica del procesamiento de señales en el Departamento de Ingeniería Eléctrica e Informática de la Universidad Carnegie Mellon.
  • Clase 12: " Redes neuronales algebraicas ", Universidad de Pensilvania (ESE 514).