Алгебраическая обработка сигналов

Алгебраическая обработка сигналов (ASP) — это новая область теоретической обработки сигналов (SP). В алгебраической теории обработки сигналов набор фильтров рассматривается как (абстрактная) алгебра , набор сигналов рассматривается как модуль или векторное пространство , а свертка рассматривается как представление алгебры . Преимуществом алгебраической обработки сигналов является ее универсальность и портативность.

История

В оригинальной формулировке алгебраической обработки сигналов Пушеля и Муры сигналы собираются в ${\mathcal {A}}$-модуль для некоторой алгебры ${\mathcal {A}}$ фильтров, а фильтрация задается действием ${\mathcal {A}}$ на ${\mathcal {A}}$-модуль.

Определения

Позволять $K$ быть полем , например комплексными числами, и ${\mathcal {A}}$ быть $K$-алгебра (т.е. векторное пространство над $K$ с бинарной операцией $\ast :{\mathcal {A}}\otimes {\mathcal {A}}\to {\mathcal {A}}$ линейно по обоим аргументам), рассматриваемый как набор фильтров. Предполагать ${\mathcal {M}}$ представляет собой векторное пространство, представляющее набор сигналов. Представление ​ ​ ${\mathcal {A}}$ алгебры состоит из гомоморфизма $\rho :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})$ где $\mathrm {End} ({\mathcal {M}})$ — алгебра линейных преобразований $T:{\mathcal {M}}\to {\mathcal {M}}$ с композицией (эквивалентной в конечномерном случае умножению матриц). Для удобства пишем $\rho _{a}$ для эндоморфизма $\rho (a)$. Чтобы быть гомоморфизмом алгебры, $\rho$ должно быть не только линейным преобразованием, но и удовлетворять свойству $$\rho _{a\ast b}=\rho _{b}\circ \rho _{a}\quad \forall a,b\in {\mathcal {A}}$$Учитывая сигнал $x\in {\mathcal {M}}$, свертка сигнала фильтром $a\in {\mathcal {A}}$ дает новый сигнал $\rho _{a}(x)$. Требуется некоторая дополнительная терминология из теории представлений алгебр. Подмножество ${\mathcal {G}}\subseteq {\mathcal {A}}$ Говорят, что алгебра порождает, если каждый элемент ${\mathcal {A}}$ можно представить в виде многочленов от элементов ${\mathcal {A}}$. Изображение генератора $g\in {\mathcal {G}}$ называется оператором сдвига . Практически во всех примерах свертки формируются в виде полиномов по $\mathrm {End} ({\mathcal {M}})$ генерируются операторами сдвига. Однако это не обязательно так для представления произвольной алгебры.

Примеры

Дискретная обработка сигналов

В дискретной обработке сигналов (DSP) пространство сигналов представляет собой набор комплексных функций. ${\mathcal {M}}={\mathcal {L}}^{2}(\mathbb {Z} )$ с ограниченной энергией (т.е. интегрируемые с квадратом функции ). Это означает бесконечный ряд $\sum _{n=-\infty }^{\infty }|(x)_{n}|<\infty$ где $|\cdot |$ — модуль комплексного числа . Оператор сдвига задается линейным эндоморфизмом $(Sx)_{n}=(x)_{n-1}$. Пространство фильтров представляет собой алгебру полиномов с комплексными коэффициентами. ${\mathcal {A}}=\mathbb {C} [z^{-1},z]$ и свертка определяется выражением $\rho _{h}=\sum _{k=-\infty }^{\infty }h_{k}S^{k}$ где $h(t)=\sum _{k=-\infty }^{\infty }h_{k}z^{k}$ является элементом алгебры. Фильтрация сигнала по $h$, то дает $(y)_{n}=\sum _{k=-\infty }^{\infty }h_{k}x_{n-k}$ потому что $(S^{k}x)_{n}=(x)_{n-k}$.

Графическая обработка сигналов

Взвешенный граф — это неориентированный граф. ${\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})$ с псевдометрикой на множестве узлов ${\mathcal {V}}$ написано $a_{ij}$. Сигнал графа — это просто функция с действительным знаком на множестве узлов графа. В нейронных сетях на графах сигналы графа иногда называют функциями. Пространство сигналов представляет собой набор всех сигналов графа. ${\mathcal {M}}=\mathbb {R} ^{\mathcal {V}}$ где ${\mathcal {V}}$ представляет собой набор $n=|{\mathcal {V}}|$ узлы в ${\mathcal {G}}=({\mathcal {V}},{\mathcal {E}})$. Алгебра фильтров — это алгебра многочленов от одной неопределенной ${\mathcal {A}}=\mathbb {R} [t]$. Существует несколько возможных вариантов оператора сдвига графа (GSO). (Не)нормализованная взвешенная матрица смежности $[A]_{ij}=a_{ij}$ является популярным выбором, а также (не)нормализованный граф Лапласа $[L]_{ij}={\begin{cases}\sum _{j=1}^{n}a_{ij}&i=j\\-a_{ij}&i\neq j\end{cases}}$. Выбор зависит от характеристик и конструктивных особенностей. Если $S$ является GSO, то свертка графа является линейным преобразованием $\rho _{h}=\sum _{k=0}^{\infty }h_{k}S^{k}$ для некоторых $h(t)=\sum _{k=0}^{\infty }h_{k}z^{k}$и свертка графического сигнала $\mathbf {x} :{\mathcal {V}}\to \mathbb {R}$ с помощью фильтра $h(t)$ дает новый графический сигнал $\mathbf {y} =\left(\sum _{k=0}^{\infty }h_{k}S^{k}\right)\cdot \mathbf {x}$.

Другие примеры

Другими математическими объектами с собственными предложенными структурами обработки сигналов являются алгебраические модели сигналов. К этим объектам относятся, в том числе, колчаны , графоны , полурешетки , конечные группы и группы Ли , и другие.

Переплетающиеся карты

В рамках теории представлений отношения между двумя представлениями одной и той же алгебры описываются с помощью переплетающихся карт , что в контексте обработки сигналов преобразуется в преобразования сигналов, соответствующие структуре алгебры. Предполагать $\rho :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})$ и $\rho ':{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}}')$ это два разных представления ${\mathcal {A}}$. — Переплетающаяся карта это линейное преобразование. $\alpha :{\mathcal {M}}\to {\mathcal {M}}'$ такой, что

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

Интуитивно это означает, что фильтрация сигнала по $a$ затем преобразуя его с помощью $\alpha$ эквивалентно первому преобразованию сигнала с помощью $\alpha$, затем фильтруем по $a$. преобразование Z- представляет собой прототипный пример переплетающейся карты.

Алгебраические нейронные сети

Вдохновленный недавней точкой зрения о том, что популярные архитектуры графовых нейронных сетей (GNN) на самом деле являются сверточными нейронными сетями (CNN), недавние работы были сосредоточены на разработке новых архитектур нейронных сетей с алгебраической точки зрения. Алгебраическая нейронная сеть представляет собой композицию алгебраических сверток, возможно, с множеством функций, агрегаций функций и нелинейностей.

Внешние ссылки

• Умный проект: Алгебраическая теория обработки сигналов на факультете электротехники и вычислительной техники Университета Карнеги-Меллон.
• Лекция 12: « Алгебраические нейронные сети », Пенсильванский университет (ESE 514).