Algebraic signal processing

Algebraic signal processing (ASP) is an emerging area of theoretical signal processing (SP). In the algebraic theory of signal processing, a set of filters is treated as an (abstract) algebra, a set of signals is treated as a module or vector space, and convolution is treated as an algebra representation. The advantage of algebraic signal processing is its generality and portability.

History

In the original formulation of algebraic signal processing by Puschel and Moura, the signals are collected in an ${\displaystyle {\mathcal {A}}}$-module for some algebra ${\displaystyle {\mathcal {A}}}$ of filters, and filtering is given by the action of ${\displaystyle {\mathcal {A}}}$ on the ${\displaystyle {\mathcal {A}}}$-module. ^[1]

Definitions

Let ${\displaystyle K}$ be a field, for instance the complex numbers, and ${\displaystyle {\mathcal {A}}}$ be a ${\displaystyle K}$-algebra (i.e. a vector space over ${\displaystyle K}$ with a binary operation ${\displaystyle \ast$ :{\mathcal {A}}\otimes {\mathcal {A}}\to {\mathcal {A}}} that is linear in both arguments) treated as a set of filters. Suppose ${\displaystyle {\mathcal {M}}}$ is a vector space representing a set signals. A representation of ${\displaystyle {\mathcal {A}}}$ consists of an algebra homomorphism ${\displaystyle \rho$ :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})} where ${\displaystyle \mathrm {End} ({\mathcal {M}})}$ is the algebra of linear transformations ${\displaystyle T:{\mathcal {M}}\to {\mathcal {M}}}$ with composition (equivalent, in the finite-dimensional case, to matrix multiplication). For convenience, we write ${\displaystyle \rho _{a}}$ for the endomorphism ${\displaystyle \rho (a)}$. To be an algebra homomorphism, ${\displaystyle \rho }$ must not only be a linear transformation, but also satisfy the property

$${\displaystyle \rho _{a\ast b}=\rho _{b}\circ \rho _{a}\quad \forall a,b\in {\mathcal {A}}}$$

Given a signal ${\displaystyle x\in {\mathcal {M}}}$, convolution of the signal by a filter ${\displaystyle a\in {\mathcal {A}}}$ yields a new signal ${\displaystyle \rho _{a}(x)}$. Some additional terminology is needed from the representation theory of algebras. A subset ${\displaystyle {\mathcal {G}}\subseteq {\mathcal {A}}}$ is said to generate the algebra if every element of ${\displaystyle {\mathcal {A}}}$ can be represented as polynomials in the elements of ${\displaystyle {\mathcal {A}}}$. The image of a generator ${\displaystyle g\in {\mathcal {G}}}$ is called a shift operator. In all practically all examples, convolutions are formed as polynomials in ${\displaystyle \mathrm {End} ({\mathcal {M}})}$ generated by shift operators. However, this is not necessarily the case for a representation of an arbitrary algebra.

Examples

Discrete Signal Processing

In discrete signal processing (DSP), the signal space is the set of complex-valued functions ${\displaystyle {\mathcal {M}}={\mathcal {L}}^{2}(\mathbb {Z} )}$ with bounded energy (i.e. square-integrable functions). This means the infinite series ${\displaystyle \sum _{n=-\infty }^{\infty }|(x)_{n}|<\infty }$ where ${\displaystyle |\cdot |}$ is the modulus of a complex number. The shift operator is given by the linear endomorphism ${\displaystyle (Sx)_{n}=(x)_{n-1}}$. The filter space is the algebra of polynomials with complex coefficients ${\displaystyle {\mathcal {A}}=\mathbb {C} [z^{-1},z]}$ and convolution is given by ${\displaystyle \rho _{h}=\sum _{k=-\infty }^{\infty }h_{k}S^{k}}$ where ${\displaystyle h(t)=\sum _{k=-\infty }^{\infty }h_{k}z^{k}}$ is an element of the algebra. Filtering a signal by ${\displaystyle h}$, then yields ${\displaystyle (y)_{n}=\sum _{k=-\infty }^{\infty }h_{k}x_{n-k}}$ because ${\displaystyle (S^{k}x)_{n}=(x)_{n-k}}$.

Graph Signal Processing

A weighted graph is an undirected graph ${\displaystyle {\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})}$ with pseudometric on the node set ${\displaystyle {\mathcal {V}}}$ written ${\displaystyle a_{ij}}$. A graph signal is simply a real-valued function on the set of nodes of the graph. In graph neural networks, graph signals are sometimes called features. The signal space is the set of all graph signals ${\displaystyle {\mathcal {M}}=\mathbb {R} ^{\mathcal {V}}}$ where ${\displaystyle {\mathcal {V}}}$ is a set of ${\displaystyle n=|{\mathcal {V}}|}$ nodes in ${\displaystyle {\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})}$. The filter algebra is the algebra of polynomials in one indeterminate ${\displaystyle {\mathcal {A}}=\mathbb {R} [t]}$. There a few possible choices for a graph shift operator (GSO). The (un)normalized weighted adjacency matrix of ${\displaystyle [A]_{ij}=a_{ij}}$ is a popular choice, as well as the (un)normalized graph Laplacian ${\displaystyle [L]_{ij}={\begin{cases}\sum _{j=1}^{n}a_{ij}&i=j\\-a_{ij}&i\neq j\end{cases}}}$. The choice is dependent on performance and design considerations. If ${\displaystyle S}$ is the GSO, then a graph convolution is the linear transformation ${\displaystyle \rho _{h}=\sum _{k=0}^{\infty }h_{k}S^{k}}$ for some ${\displaystyle h(t)=\sum _{k=0}^{\infty }h_{k}z^{k}}$, and convolution of a graph signal ${\displaystyle \mathbf {x}$ :{\mathcal {V}}\to \mathbb {R} } by a filter ${\displaystyle h(t)}$ yields a new graph signal ${\displaystyle \mathbf {y} =\left(\sum _{k=0}^{\infty }h_{k}S^{k}\right)\cdot \mathbf {x} }$.

Other Examples

Other mathematical objects with their own proposed signal-processing frameworks are algebraic signal models. These objects include including quivers, ^[2] graphons, ^[3] semilattices, ^[4] finite groups, and Lie groups, ^[5] and others.

Intertwining Maps

In the framework of representation theory, relationships between two representations of the same algebra are described with intertwining maps which in the context of signal processing translates to transformations of signals that respect the algebra structure. Suppose ${\displaystyle \rho$ :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})} and ${\displaystyle \rho ':{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}}')}$ are two different representations of ${\displaystyle {\mathcal {A}}}$. An intertwining map is a linear transformation ${\displaystyle \alpha$ :{\mathcal {M}}\to {\mathcal {M}}'} such that

${\displaystyle \alpha \circ \rho _{a}=\rho '_{a}\circ \alpha \quad \forall a\in {\mathcal {A}}}$

Intuitively, this means that filtering a signal by ${\displaystyle a}$ then transforming it with ${\displaystyle \alpha }$ is equivalent to first transforming a signal with ${\displaystyle \alpha }$, then filtering by ${\displaystyle a}$. The z transform ^[1] is a prototypical example of an intertwining map.

Algebraic Neural Networks

Inspired by a recent perspective that popular graph neural networks (GNNs) architectures are in fact convolutional neural networks (CNNs), ^[6] recent work has been focused on developing novel neural network architectures from the algebraic point-of-view. ^{[7] [8]} An algebraic neural network is a composition of algebraic convolutions, possibly with multiple features and feature aggregations, and nonlinearities.

References

1. Puschel, M.; Moura, J. (2008). "Algebraic Signal Processing Theory: Foundation and 1-D Time". IEEE Transactions on Signal Processing. 56 (8): 3572–3585. 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 (2020-10-22). "Quiver Signal Processing (QSP)". arXiv: 2010.11525 [eess.SP].
3. Ruiz, Luana; Chamon, Luiz F. O.; Ribeiro, Alejandro (2021). "Graphon Signal Processing". IEEE Transactions on Signal Processing. 69: 4961–4976. arXiv: 2003.05030 . Bibcode:2021ITSP...69.4961R. doi:10.1109/TSP.2021.3106857. ISSN   1053-587X. S2CID   212657497.
4. Puschel, Markus; Seifert, Bastian; Wendler, Chris (2021). "Discrete Signal Processing on Meet/Join Lattices". 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). "Demystifying Lie Group Methods for Signal Processing: A 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). "Graphs, Convolutions, and Neural Networks: From Graph Filters to Graph Neural Networks". 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). "Algebraic Neural Networks: Stability to Deformations". 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 (2022). "Convolutional Filtering and Neural Networks with Non Commutative Algebras". arXiv: 2108.09923 [cs.LG].

External links

• Smart Project: Algebraic Theory of Signal Processing at the Department of Electrical and Computer Engineering at Carnegie Mellon University.
• Lecture 12: "Algebraic Neural Networks," University of Pennsylvania (ESE 514).