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

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

История

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

Определения

Пусть будет полем , например комплексными числами, и будет -алгеброй (т. е. векторным пространством над с бинарной операцией , линейной по обоим аргументам), рассматриваемой как набор фильтров. Предположим, что является векторным пространством, представляющим набор сигналов. Представление состоит из гомоморфизма алгебры , где - алгебра линейных преобразований с композицией (эквивалентной, в конечномерном случае, умножению матриц). Для удобства мы запишем для эндоморфизма . Чтобы быть гомоморфизмом алгебры, должно быть не только линейным преобразованием, но и удовлетворять свойству При наличии сигнала свертка сигнала фильтром дает новый сигнал . Необходима некоторая дополнительная терминология из теории представлений алгебр. Говорят, что подмножество порождает алгебру , если каждый элемент из может быть представлен в виде полиномов от элементов из . Образ генератора называется оператором сдвига . Во всех практически всех примерах свертки формируются как полиномы в , порожденные операторами сдвига. Однако это не обязательно так для представления произвольной алгебры. К {\displaystyle К} А {\displaystyle {\mathcal {A}}} К {\displaystyle К} К {\displaystyle К} ∗ : А ⊗ А → А {\displaystyle \ast :{\mathcal {A}}\otimes {\mathcal {A}}\to {\mathcal {A}}} М {\displaystyle {\mathcal {M}}} А {\displaystyle {\mathcal {A}}} ρ : А → Э н г ( М ) {\displaystyle \rho :{\mathcal {A}}\to \mathrm {End} ({\mathcal {M}})} Э н г ( М ) {\displaystyle \mathrm {Конец} ({\mathcal {M}})} Т : М → М {\displaystyle T:{\mathcal {M}}\to {\mathcal {M}}} ρ а {\displaystyle \rho _{a}} ρ ( а ) {\displaystyle \ро (а)} ρ {\displaystyle \ро} ρ а ∗ б = ρ б ∘ ρ а ∀ а , б ∈ А {\displaystyle \rho _{a\ast b}=\rho _{b}\circ \rho _{a}\quad \forall a,b\in {\mathcal {A}}} х ∈ М {\displaystyle x\in {\mathcal {M}}} а ∈ А {\displaystyle a\in {\mathcal {A}}} ρ а ( х ) {\displaystyle \rho _{a}(x)} G ⊆ A {\displaystyle {\mathcal {G}}\subseteq {\mathcal {A}}} A {\displaystyle {\mathcal {A}}} A {\displaystyle {\mathcal {A}}} g ∈ G {\displaystyle g\in {\mathcal {G}}} E n d ( M ) {\displaystyle \mathrm {End} ({\mathcal {M}})}

Примеры

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

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

Обработка графических сигналов

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

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

Другие математические объекты с их собственными предлагаемыми фреймворками обработки сигналов являются алгебраическими моделями сигналов. Эти объекты включают в себя колчаны , [2] графоны , [3] полурешетки , [4] конечные группы и группы Ли , [5] и другие.

Переплетение карт

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

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

Интуитивно это означает, что фильтрация сигнала с последующим его преобразованием с помощью эквивалентна первоначальному преобразованию сигнала с помощью , а затем фильтрации с помощью . Преобразование z [1] является прототипическим примером переплетающейся карты. a {\displaystyle a} α {\displaystyle \alpha } α {\displaystyle \alpha } a {\displaystyle a}

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

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

Ссылки

  1. ^ ab Puschel, M.; Moura, J. (2008). «Алгебраическая теория обработки сигналов: основы и одномерное время». 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. ^ Парада-Майорга, Алехандро; Рисс, Ганс; Рибейро, Алехандро; Грист, Роберт (22 октября 2020 г.). «Обработка сигналов колчана (QSP)». arXiv : 2010.11525 [eess.SP].
  3. ^ Руис, Луана; Шамон, Луис Ф.О.; Рибейро, Алехандро (2021). «Обработка графоновых сигналов». Транзакции IEEE по обработке сигналов . 69 : 4961–4976 . arXiv : 2003.05030 . Бибкод : 2021ITSP...69.4961R. дои :10.1109/TSP.2021.3106857. ISSN  1053-587X. S2CID  212657497.
  4. ^ Пушель, Маркус; Сейферт, Бастиан; Вендлер, Крис (2021). «Дискретная обработка сигналов на решетках встреч/соединений». Труды IEEE по обработке сигналов . 69 : 3571– 3584. arXiv : 2012.04358 . Bibcode : 2021ITSP...69.3571P. doi : 10.1109/TSP.2021.3081036. ISSN  1053-587X. S2CID  227736440.
  5. ^ Бернардини, Риккардо; Ринальдо, Роберто (2021). «Демистификация методов групп Ли для обработки сигналов: учебное пособие». Журнал IEEE Signal Processing . 38 (2): 45– 64. Bibcode : 2021ISPM...38b..45B. doi : 10.1109/MSP.2020.3023540. ISSN  1053-5888. S2CID  232071730.
  6. ^ Гама, Фернандо; Исуфи, Элвин; Леус, Герт; Рибейро, Алехандро (2020). «Графы, свертки и нейронные сети: от графовых фильтров к графовым нейронным сетям». Журнал обработки сигналов IEEE . 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). «Алгебраические нейронные сети: устойчивость к деформациям». 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). «Сверточная фильтрация и нейронные сети с некоммутативными алгебрами». Труды IEEE по обработке сигналов . 71 : 2683. arXiv : 2108.09923 . Bibcode : 2023ITSP...71.2683P. doi : 10.1109/TSP.2023.3293716.
  • Интеллектуальный проект: Алгебраическая теория обработки сигналов на кафедре электротехники и вычислительной техники Университета Карнеги-Меллона.
  • Лекция 12: «Алгебраические нейронные сети», Пенсильванский университет (ESE 514).
Retrieved from "https://en.wikipedia.org/w/index.php?title=Algebraic_signal_processing&oldid=1224574682"