Jump to content

Графовое преобразование Фурье

В математике преобразование Фурье графа это математическое преобразование , которое разлагает матрицу Лапласа графа на собственные значения и собственные векторы . Аналогично классическому преобразованию Фурье , собственные значения представляют частоты , а собственные векторы образуют так называемый базис графа Фурье .

Графовое преобразование Фурье играет важную роль в теории спектральных графов . Он широко применяется в недавних исследованиях алгоритмов обучения со структурой графов , таких как широко используемые сверточные сети .

Определение

[ редактировать ]

Учитывая неориентированный взвешенный граф , где представляет собой набор узлов с ( количество узлов) и это набор ребер, сигнал графа — функция, определенная в вершинах графа . Сигнал отображает каждую вершину на действительное число . Любой графический сигнал можно спроецировать на собственные векторы матрицы Лапласа. . [1] Позволять и быть собственное значение и собственный вектор Лапласа матрицы (собственные значения отсортированы в порядке возрастания, т.е. [2] ), графовое преобразование Фурье (GFT) графического сигнала на вершинах это расширение с точки зрения собственных функций . [3] Он определяется как: [1] [4]

где .

С действительная симметричная матрица , ее собственные векторы образуют ортогональный базис . Следовательно, существует обратное графовое преобразование Фурье (IGFT), и оно записывается как: [4]

Аналогично классическому преобразованию Фурье , преобразование Фурье графа позволяет представить сигнал в двух разных областях: вершинной области и спектральной области графа . Обратите внимание, что определение графового преобразования Фурье и его обратного преобразования зависит от выбора собственных векторов Лапласа, которые не обязательно являются уникальными. [3] Собственные векторы нормализованной матрицы Лапласа также являются возможной основой для определения прямого и обратного преобразования Фурье графа.

Характеристики

[ редактировать ]

Личность Парсеваля

[ редактировать ]

Соотношение Парсеваля справедливо для преобразования Фурье графа: [5] то есть для любого

Это дает нам личность Парсеваля : [3]

Обобщенный оператор свертки

[ редактировать ]

Определение свертки между двумя функциями и не может быть напрямую применено к графическим сигналам, поскольку трансляция сигнала не определена в контексте графов. [4] Однако, заменяя комплексный экспоненциальный сдвиг в классическом преобразовании Фурье собственными векторами Лапласа графа, свертку двух сигналов графа можно определить как: [3]

Свойства оператора свертки

[ редактировать ]

Обобщенный оператор свертки удовлетворяет следующим свойствам: [3]

  • Обобщенная свертка в вершинной области — это умножение в спектральной области графа:
  • Коммутативность :
  • Дистрибутивность :
  • Ассоциативность :
  • Ассоциативность со скалярным умножением: , для любого .
  • Мультипликативное тождество : , где является тождеством обобщенного оператора свертки.
  • Сумма обобщенной свертки двух сигналов равна произведению сумм двух сигналов на константу:

Обобщенный оператор перевода

[ редактировать ]

Как уже говорилось ранее, классический оператор перевода не может быть обобщено на настройку графика. Один из способов определить оператор обобщенного перевода — использовать обобщенную свертку с дельта-функцией с центром в вершине. : [2]

где

Константа нормализации гарантирует, что оператор перевода сохраняет среднее значение сигнала, [4] то есть,

Свойства оператора перевода

[ редактировать ]

Обобщенный оператор свертки удовлетворяет следующим свойствам: [3]

Для любого , и ,

Приложения

[ редактировать ]

Сжатие изображения

[ редактировать ]

Представление сигналов в частотной области является распространенным подходом к сжатию данных. Поскольку сигналы графа могут быть редкими в своей спектральной области графа, преобразование Фурье графа также можно использовать для сжатия изображений . [6] [7]

Уменьшение шума графика

[ редактировать ]

Подобно классическому шумоподавлению сигналов на основе преобразования Фурье, графовые фильтры на основе графового преобразования Фурье могут быть предназначены для шумоподавления графового сигнала. [8]

Классификация данных

[ редактировать ]

Поскольку преобразование Фурье графа позволяет определять свертку на графах, оно позволяет адаптировать обычные сверточные нейронные сети (CNN) для работы с графами. со структурой графа, Алгоритмы полуконтролируемого обучения такие как сверточная сеть графа (GCN), способны распространять метки сигнала графа по всему графу с небольшим подмножеством помеченных узлов, теоретически работая как аппроксимация первого порядка сверток спектрального графа без вычислений. граф Лапласа и его собственное разложение. [9]

Ящик для инструментов

[ редактировать ]

GSPBOX [10] [11] представляет собой набор инструментов для обработки сигналов графов, включая преобразование Фурье графа. Он поддерживает языки Python и MATLAB .

  1. ^ Перейти обратно: а б Рико, Бенджамин; Боргнат, Пьер; Трамбле, Николя; Гонсалвес, Пауло; Вандергейнст, Пьер (01 июля 2019 г.). «Фурье мог бы быть специалистом по данным: от преобразования Фурье графа к обработке сигналов на графиках» . Comptes Rendus Physique . Фурье и наука сегодняшнего дня / Фурье и наука о жизни. 20 (5): 474–488. Бибкод : 2019CRPhy..20..474R . дои : 10.1016/j.crhy.2019.08.003 . ISSN   1631-0705 .
  2. ^ Перейти обратно: а б Шуман, Давид I; Наранг, Сунил К.; Фроссар, Паскаль; Ортега, Антонио; Вандергейнст, Пьер (май 2013 г.). «Новая область обработки сигналов на графиках: распространение многомерного анализа данных на сети и другие нерегулярные области». Журнал обработки сигналов IEEE . 30 (3): 83–98. arXiv : 1211.0053 . Бибкод : 2013ISPM...30...83S . дои : 10.1109/MSP.2012.2235192 . ISSN   1558-0792 . S2CID   1594725 .
  3. ^ Перейти обратно: а б с д и ж Шуман, Давид I; Рико, Бенджамин; Вандергейнст, Пьер (01 марта 2016 г.). «Вершинно-частотный анализ на графах» . Прикладной и вычислительный гармонический анализ . 40 (2): 260–291. arXiv : 1307.5708 . дои : 10.1016/j.acha.2015.02.005 . ISSN   1063-5203 .
  4. ^ Перейти обратно: а б с д Нонато, Луис Густаво (29 августа 2017 г.). «График преобразования Фурье» (PDF) .
  5. ^ Хаммонд, Дэвид К.; Вандергейнст, Пьер; Грибонваль, Реми (01 марта 2011 г.). «Вейвлеты на графах с помощью теории спектральных графов» . Прикладной и вычислительный гармонический анализ . 30 (2): 129–150. arXiv : 0912.3848 . дои : 10.1016/j.acha.2010.04.005 . ISSN   1063-5203 . S2CID   5593503 .
  6. ^ Сандрыгайло, Алексей; Моура, Хосе М.Ф. (май 2013 г.). «Дискретная обработка сигналов на графах: преобразование Фурье графа». Международная конференция IEEE 2013 по акустике, речи и обработке сигналов . IEEE. стр. 6167–6170. дои : 10.1109/icassp.2013.6638850 . ISBN  978-1-4799-0356-6 . S2CID   14704192 .
  7. ^ Ху, Вэй; Чунг, Джин; Ортега, Антонио; Ау, Оскар К. (январь 2015 г.). «Преобразование Фурье графа с многоразрешением для сжатия кусочно-гладких изображений». Транзакции IEEE при обработке изображений . 24 (1): 419–433. Бибкод : 2015ITIP...24..419H . дои : 10.1109/TIP.2014.2378055 . ISSN   1941-0042 . ПМИД   25494508 . S2CID   9539186 .
  8. ^ Сандрыгайло, Алексей; Моура, Хосе МФ (июнь 2014 г.). «Дискретная обработка сигналов на графиках: частотный анализ». Транзакции IEEE по обработке сигналов . 62 (12): 3042–3054. arXiv : 1307.0468 . Бибкод : 2014ITSP...62.3042. . дои : 10.1109/TSP.2014.2321121 . ISSN   1941-0476 . S2CID   12110057 .
  9. ^ Кипф, Томас Н.; Веллинг, Макс (22 февраля 2017 г.). «Полуконтролируемая классификация с использованием сверточных сетей графов». arXiv : 1609.02907 [ cs.LG ].
  10. ^ Перроден, Натанаэль; Паратте, Йохан; Шуман, Дэвид; Мартин, Лайонел; Калофолиас, Василис; Вандергейнст, Пьер; Хаммонд, Дэвид К. (15 марта 2016 г.). «GSPBOX: набор инструментов для обработки сигналов на графиках». arXiv : 1408.5781 [ cs.IT ].
  11. ^ «PyGSP: обработка сигналов графа в Python — документация PyGSP 0.5.1» . pygsp.readthedocs.io . Проверено 22 июня 2020 г.
[ редактировать ]
  • DeepGraphLibrary Бесплатный пакет Python, созданный для простой реализации графовых нейронных сетей.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: fbdc0ae38b41c71a28022dc8b7e0e68a__1719406560
URL1:https://arc.ask3.ru/arc/aa/fb/8a/fbdc0ae38b41c71a28022dc8b7e0e68a.html
Заголовок, (Title) документа по адресу, URL1:
Graph Fourier transform - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)