Algebraisk signalbehandling

Algebraisk signalbehandling (ASP) är ett framväxande område för teoretisk signalbehandling (SP). I den algebraiska teorin om signalbehandling behandlas en uppsättning filter som en (abstrakt) algebra , en uppsättning signaler behandlas som en modul eller vektorrum , och faltning behandlas som en algebra-representation . Fördelen med algebraisk signalbehandling är dess generalitet och portabilitet.

Historia

I den ursprungliga formuleringen av algebraisk signalbehandling av Puschel och Moura, samlas signalerna i en ${\mathcal {A}}$ -modul för någon algebra ${\mathcal {A}}$ av filter , och filtrering ges av åtgärden av ${\mathcal {A}}$ på ${\mathcal {A}}$ -modulen.

Definitioner

Låt $K$ vara ett fält , till exempel de komplexa talen, och ${\mathcal {A}}$ vara en $K$ -algebra (dvs. ett vektorrum över $K$ med en binär operation ${\displaystyle \ast :{\mathcal {A}}\otimes {\mathcal {A}}\to {\mathcal {A}}} som är linjär i$ båda argument) behandlas som en uppsättning filter. Antag att ${\mathcal {M}}$ är ett vektorrum som representerar en uppsättning signaler. En representation av ${\mathcal {A}}$ består av en algebrahomomorfism ρ $\displaystyle \rho :{\mathcal {A}}\to \mathrm {Slut} ({\mathcal {M}})}$ där $\mathrm {End} ({\mathcal {M}})$ är algebra för linjära transformationer $T :{\mathcal {M}}\to {\mathcal {M}}$ med sammansättning (motsvarande, i det finita dimensionella fallet, matrismultiplikation). För enkelhetens skull skriver vi $\rho _{a}$ för endomorfismen $\rho (a)$ . För att vara en algebrahomomorfism $\rho$ inte bara vara en linjär transformation, utan även uppfylla egenskapen

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

Givet en signal $x\in {\mathcal {M}}$ ger faltning av signalen med ett filter $\displaystyle a\in {\mathcal {A}}}$ { en ny signal $\rho _{a}(x)$ . Ytterligare terminologi behövs från representationsteorin för algebror. En delmängd ${\mathcal {G}}\subseteq {\mathcal {A}}$ sägs generera algebra om varje element i ${\mathcal {A}}$ kan representeras som polynom i elementen i ${\mathcal {A}}$ . Bilden av en generator $g\in {\mathcal {G}}$ kallas en skiftoperator . I alla praktiskt taget alla exempel bildas faltningar som polynom i $\mathrm {End} ({\mathcal {M}})$ genererade av skiftoperatorer. Detta är dock inte nödvändigt för en representation av en godtycklig algebra.

Exempel

Diskret signalbehandling

I diskret signalbehandling (DSP) är signalutrymmet uppsättningen av komplexa funktioner ${\mathcal {M}}={\mathcal {L}}^{2}(\ mathbb {Z} )$ med begränsad energi (dvs. kvadratintegrerbara funktioner ). Detta betyder den oändliga serien $\sum _{n=-\infty }^{\infty }|(x)_{n}|<\infty$ där $|\cdot |$ är modulen för ett komplext tal . Skiftoperatorn ges av den linjära endomorfismen $(Sx)_{n}=(x)_{n-1}$ . Filterutrymmet är algebra för polynom med komplexa koefficienter ${\mathcal {A}}=\mathbb {C} [z^{-1},z]$ och faltning ges av $\rho _{h}=\summa _{k=-\infty }^{\infty }h_{k}S^{k}$ där $h(t)=\summa _{k=-\infty }^{\infty }h_{k}z^{k}$ är ett element i algebra. Filtrering av en signal med $h$ , ger sedan $(y)_{n}=\summa _{k=-\infty }^{\infty }h_{k}x_{nk}$ eftersom $(S^{k}x)_{n}=(x)_{ nk}$ .

Grafsignalbehandling

En viktad graf är en oriktad graf ${\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})$ med pseudometrisk på noduppsättningen ${\mathcal {V}}$ skrivet $a_{ij}$ . En grafsignal är helt enkelt en verkligt värderad funktion på uppsättningen av noder i grafen. I grafiska neurala nätverk kallas grafsignaler ibland för funktioner. Signalutrymmet är mängden av alla grafsignaler ${\mathcal {M}}=\mathbb {R} ^{\mathcal {V}}$ där ${\mathcal {V} }$ är en uppsättning av $n=|{\mathcal {V}}|$ noder i ${\mathcal {G}}=({\mathcal {V}},{\mathcal {E} })$ . Filteralgebra är algebra för polynom i ett obestämt ${\mathcal {A}}=\mathbb {R} [t]$ . Det finns några möjliga val för en grafskiftsoperator (GSO). Den (o)normaliserade viktade närliggande matrisen för $[A]_{ij}=a_{ij}$ är ett populärt val, liksom den (o)normaliserade grafen Laplacian $[L]_{ij}={\begin{cases}\sum _{j=1}^ {n}a_{ij}&i=j\\-a_{ij}&i\neq j\end{cases}}$ . Valet beror på prestanda och designöverväganden. Om $S$ är GSO, så är en graffaltning den linjära transformationen $\rho _{h}=\summa _{k=0}^{ \infty }h_{k}S^{k}$ för vissa $h(t)=\sum _{k=0}^{\infty }h_ {k}z^{k}$ och faltning av en grafsignal $\mathbf {x} :{\mathcal {V}}\to \mathbb {R}$ av ett filter $h(t)$ ger en ny grafsignal $\mathbf {y} =\left(\sum _{k=0}^ {\infty }h_{k}S^{k}\right)\cdot \mathbf {x}$ .

Andra exempel

Andra matematiska objekt med egna föreslagna ramverk för signalbehandling är algebraiska signalmodeller. Dessa objekt inkluderar inklusive kogger , grafoner , semilattices , finita grupper och Lie-grupper och andra.

Sammanflätade kartor

Inom ramen för representationsteorin beskrivs relationer mellan två representationer av samma algebra med sammanflätade kartor som i samband med signalbehandling översätts till transformationer av signaler som respekterar algebrastrukturen. Antag $\rho :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})$ och ${\displaystyle \rho ':{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}}')} är två olika$ representationer av ${\mathcal {A }}$ . En sammanflätad karta är en linjär transformation $\alpha :{\mathcal {M}}\to {\mathcal {M}}'$ så att

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

Intuitivt betyder detta att att filtrera en signal med $a$ och sedan transformera den med $\alpha$ motsvarar att först transformera en signal med ${\displaystyle \alpha } ,$ sedan filtrera med $a$ . z -transformen är ett prototypiskt exempel på en sammanflätad karta.

Algebraiska neurala nätverk

Inspirerad av ett senare perspektiv att populära grafiska neurala nätverksarkitekturer (GNN) i själva verket är konvolutionella neurala nätverk (CNN), har det senaste arbetet fokuserats på att utveckla nya neurala nätverksarkitekturer från en algebraisk synvinkel. Ett algebraiskt neuralt nätverk är en sammansättning av algebraiska faltningar, möjligen med flera funktioner och egenskapsaggregationer och olinjäriteter.

externa länkar

• Smart Project: Algebraic Theory of Signal Processing vid institutionen för elektro- och datateknik vid Carnegie Mellon University.
• Föreläsning 12: " Algebraic Neural Networks ," University of Pennsylvania (ESE 514).