Соответствующее преследование

Алгоритм многомерных данных

Сигнал и его вейвлет-представление. Каждый пиксель на тепловой карте (вверху) представляет атом (вейвлет, центрированный по времени в соответствии с горизонтальным положением и с частотой, соответствующей высоте). Цвет пикселя дает внутреннее произведение соответствующего вейвлет-атома с сигналом (внизу). Соответствующее преследование должно представлять сигнал всего несколькими атомами, например, тремя в центрах четко видимых эллипсов.

Matching chase (MP) — это алгоритм разреженного приближения , который находит «наилучшие соответствующие» проекции многомерных данных на диапазон сверхполного (т.е. избыточного) словаря . Основная идея заключается в приближенном представлении сигнала из гильбертова пространства как взвешенной суммы конечного числа функций (называемых атомами), взятых из . Приближение с атомами имеет вид ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle H}$ ${\displaystyle g_{\gamma _{n}}}$ ${\displaystyle D}$ ${\displaystyle N}$

${\displaystyle f(t)\approx {\hat {f}}_{N}(t):=\sum _{n=1}^{N}a_{n}g_{\gamma _{n}}(t)}$

где - th столбец матрицы , а - скалярный весовой коэффициент (амплитуда) для атома . Обычно не каждый атом в будет использоваться в этой сумме. Вместо этого, сопоставление преследования выбирает атомы по одному, чтобы максимально (жадно) уменьшить ошибку аппроксимации. Это достигается путем нахождения атома, который имеет наивысшее внутреннее произведение с сигналом (предполагая, что атомы нормализованы), вычитания из сигнала аппроксимации, которая использует только этот один атом, и повторения процесса до тех пор, пока сигнал не будет удовлетворительно разложен, т. е. норма остатка не станет малой, где остаток после вычисления и обозначается как ${\displaystyle g_{\gamma _{n}}}$ ${\displaystyle \gamma _{n}}$ ${\displaystyle D}$ ${\displaystyle a_{n}}$ ${\displaystyle g_{\gamma _{n}}}$ ${\displaystyle D}$ ${\displaystyle \gamma _{N}}$ ${\displaystyle a_{N}}$

${\displaystyle R_{N+1}=f-{\hat {f}}_{N}}$.

Если сходится быстро к нулю, то для получения хорошего приближения к , необходимо всего несколько атомов . Такие разреженные представления желательны для кодирования и сжатия сигналов. Точнее, проблема разреженности, которую соответствие преследованию призвано приблизительно решить, заключается в следующем: ${\displaystyle R_{n}}$ ${\displaystyle f}$

${\displaystyle \min _{x}\|f-Dx\|_{2}^{2}\ {\text{ subject to }}\ \|x\|_{0}\leq N,}$

где — псевдонорма (т.е. число ненулевых элементов ). В предыдущей записи ненулевые элементы — это . Точное решение проблемы разреженности — NP-трудная задача , поэтому используются методы аппроксимации, такие как MP. ${\displaystyle \|x\|_{0}}$ ${\displaystyle L_{0}}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle x_{\gamma _{n}}=a_{n}}$

Для сравнения рассмотрим представление сигнала с помощью преобразования Фурье — его можно описать с помощью приведенных выше терминов, где словарь строится из синусоидальных базисных функций (минимально возможный полный словарь). Главным недостатком анализа Фурье в обработке сигналов является то, что он извлекает только глобальные особенности сигналов и не адаптируется к анализируемым сигналам . Взяв чрезвычайно избыточный словарь, мы можем искать в нем атомы (функции), которые наилучшим образом соответствуют сигналу . ${\displaystyle f}$ ${\displaystyle f}$

Алгоритм

Пример извлечения неизвестного сигнала (серая линия) из нескольких измерений (черные точки) с использованием алгоритма ортогонального сопоставления (фиолетовые точки показывают извлеченные коэффициенты).

Если содержит большое количество векторов, поиск наиболее разреженного представления является вычислительно неприемлемым для практических приложений. В 1993 году Маллат и Чжан ^[1] предложили жадное решение, которое они назвали «Matching Pursuit». Для любого сигнала и любого словаря алгоритм итеративно генерирует отсортированный список индексов атомов и скаляров весов, которые формируют субоптимальное решение проблемы разреженного представления сигнала. ${\displaystyle D}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle D}$

Алгоритм Соответствия Преследования Вход: Сигнал: , словарь с нормализованными столбцами . ${\displaystyle f(t)}$ ${\displaystyle D}$ ${\displaystyle g_{i}}$ Вывод: Список коэффициентов и индексов для соответствующих атомов . ${\displaystyle (a_{n})_{n=1}^{N}}$ ${\displaystyle (\gamma _{n})_{n=1}^{N}}$ Инициализация:  ${\displaystyle R_{1}\,\leftarrow \,f(t)}$; ; ${\displaystyle n\,\leftarrow \,1}$ Повторить: Найти с максимальным внутренним произведением ; ; ; ; ${\displaystyle g_{\gamma _{n}}\in D}$ ${\displaystyle |\langle R_{n},g_{\gamma _{n}}\rangle |}$ ${\displaystyle a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle }$ ${\displaystyle R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}}$ ${\displaystyle n\,\leftarrow \,n+1}$ До остановки состояния (например: ) ${\displaystyle \|R_{n}\|<\mathrm {threshold} }$ возвращаться

• "←" обозначает назначение . Например, " largest ← item " означает, что значение largest изменяется на значение item .
• « return » завершает алгоритм и выводит следующее значение.

В обработке сигналов концепция поиска соответствия связана со статистическим поиском проекций , при котором находятся «интересные» проекции; те, которые больше отклоняются от нормального распределения, считаются более интересными.

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

• Алгоритм сходится (т.е. ) для любого элемента , который находится в пространстве, охватываемом словарем. ${\displaystyle R_{n}\to 0}$ ${\displaystyle f}$
• Ошибка монотонно уменьшается. ${\displaystyle \|R_{n}\|}$
• Поскольку на каждом шаге остаток ортогонален выбранному фильтру, уравнение сохранения энергии выполняется для каждого : ${\displaystyle N}$

${\displaystyle \|f\|^{2}=\|R_{N+1}\|^{2}+\sum _{n=1}^{N}{|a_{n}|^{2}}}$.

• В случае, если векторы в ортонормальны, а не избыточны, то МП является формой анализа главных компонент. ${\displaystyle D}$

Приложения

Соответствующее преследование применялось к кодированию сигналов, изображений ^[2] и видео, ^{[3] [4]} представлению и распознаванию форм, ^[5] кодированию 3D-объектов, ^[6] и в междисциплинарных приложениях, таких как мониторинг состояния конструкций. ^[7] Было показано, что оно работает лучше, чем кодирование на основе DCT для низких скоростей передачи данных как по эффективности кодирования, так и по качеству изображения. ^[8] Основная проблема с соответствием преследованием заключается в вычислительной сложности кодера. В базовой версии алгоритма большой словарь необходимо искать на каждой итерации. Улучшения включают использование приблизительных представлений словаря и неоптимальных способов выбора наилучшего соответствия на каждой итерации (извлечение атомов). ^[9] Алгоритм соответствия преследование используется в MP/SOFT, методе моделирования квантовой динамики. ^[10]

MP также используется при изучении словаря . ^{[11] [12]} В этом алгоритме атомы изучаются из базы данных (в общем случае, это естественные сцены, такие как обычные изображения), а не выбираются из общих словарей.

Совсем недавним применением МП является его использование в кодировании линейных вычислений ^[13] для ускорения вычисления произведений матрицы на вектор.

Расширения

Популярным расширением Matching Pursuit (MP) является его ортогональная версия: Orthogonal Matching Pursuit ^{[14] [15]} (OMP). Главное отличие от MP заключается в том, что после каждого шага все извлеченные до сих пор коэффициенты обновляются путем вычисления ортогональной проекции сигнала на подпространство, охватываемое набором выбранных до сих пор атомов. Это может привести к результатам, лучшим, чем стандартный MP, но требует больше вычислений. Было показано, что OMP имеет гарантии стабильности и производительности при определенных ограниченных условиях изометрии . ^[16] Инкрементный многопараметрический алгоритм (IMP), опубликованный за три года до MP, работает так же, как OMP. ^[17]

Расширения, такие как Multichannel MP ^[18] и Multichannel OMP ^[19], позволяют обрабатывать многокомпонентные сигналы. Очевидное расширение Matching Pursuit — на несколько позиций и масштабов, путем расширения словаря до словаря вейвлет-базиса. Это можно эффективно сделать с помощью оператора свертки без изменения основного алгоритма. ^[20]

Matching chase относится к области сжатого зондирования и был расширен исследователями в этом сообществе. Известные расширения: Orthogonal Matching Pursuit (OMP), ^[21] Stagewise OMP (StOMP), ^[22] compressionive sampling matching chaser chase (CoSaMP), ^[23] Generalized OMP (gOMP), ^[24] и Multipath Matching Pursuit (MMP). ^[25]

Смотрите также

• ЧИСТЫЙ алгоритм
• Обработка изображений
• Спектральный анализ методом наименьших квадратов
• Анализ главных компонент (PCA)
• Проекция преследования
• Обработка сигнала
• Разреженное приближение
• Пошаговая регрессия

Ссылки

1. Маллат, С.Г.; Чжан, З. (1993). «Соответствие преследований с помощью частотно-временных словарей». Труды IEEE по обработке сигналов . 1993 (12): 3397–3415. Bibcode : 1993ITSP...41.3397M. doi : 10.1109/78.258082. S2CID  14427335.
2. Перринет, Л. (2015). «Разреженные модели для компьютерного зрения». Biologically Inspired Computer Vision . 14 : 319–346. arXiv : 1701.06859 . doi :10.1002/9783527680863.ch14. ISBN 9783527680863. S2CID  2085413.
3. Бержо, Ф.; Маллат, С. (1995). «Соответствующее преследование изображений». Труды., Международная конференция по обработке изображений . Том 1. С. 53–56. doi :10.1109/ICIP.1995.529037. ISBN 978-0-7803-3122-8. S2CID  721789.
4. Нефф, Р.; Захор, А. (1997). «Кодирование видео с очень низкой скоростью передачи данных на основе поиска соответствия». Труды IEEE по схемам и системам для видеотехнологий . 7 (1): 158–171. doi :10.1109/76.554427. S2CID  15317511.
5. Мендельс, Ф.; Вандергейнст, П.; Тиран, Дж. П. (2006). «Соответствие представления и распознавания формы на основе преследования с использованием масштабного пространства». Международный журнал систем и технологий визуализации . 16 (5): 162–180. doi :10.1002/ima.20078. S2CID  5132416.
6. Tosic, I.; Frossard, P.; Vandergheynst, P. (2005). «Прогрессивное кодирование 3D-объектов на основе сверхполных разложений». IEEE Transactions on Circuits and Systems for Video Technology . 16 (11): 1338–1349. doi :10.1109/tcsvt.2006.883502. S2CID  3031513.
7. Чакраборти, Дебеджо; Коввали, Нараян; Вэй, Джун; Папандреу-Суппаппола, Антония; Кохран, Дуглас; Чаттопадхай, Адити (2009). «Мониторинг состояния конструкций с классификацией повреждений в болтовых конструкциях с использованием частотно-временных методов». Журнал интеллектуальных материальных систем и конструкций . 20 (11): 1289–1305. doi :10.1177/1045389X08100044. S2CID  109511712.
8. Перринет, Л.У.; Сэмуэлидес, М.; Торп, С. (2002). «Разреженное кодирование спайков в асинхронной многослойной нейронной сети с прямой связью с использованием Matching Pursuit». Нейрокомпьютинг . 57C : 125–34. doi : 10.1016/j.neucom.2004.01.010.^{[ постоянная мертвая ссылка ]}
9. Линь, Цзянь-Лян; Хванг, Вэнь-Лян; Пей, Су-Чан (2007). «Быстрое видеокодирование с преследованием путем комбинирования аппроксимации словаря и извлечения атомов». Труды IEEE по схемам и системам для видеотехнологий . 17 (12): 1679–1689. CiteSeerX 10.1.1.671.9670 . doi :10.1109/tcsvt.2007.903120. S2CID  8315216. 
10. Wu, Yinghua; Batista, Victor S. (2003). «Соответствие-преследование для моделирования квантовых процессов». J. Chem. Phys . 118 (15): 6720–6724. Bibcode :2003JChPh.118.6720W. doi :10.1063/1.1560636. S2CID  37544146.
11. Perrinet, LP (2010). «Роль гомеостаза в обучении разреженным представлениям». Neural Computation . 22 (7): 1812–1836. arXiv : 0706.3177 . doi : 10.1162/neco.2010.05-08-795. PMC 2929690. PMID  20235818 . 
12. Аарон, М.; Элад, М.; Брукштейн, А.М. (2006). «K-SVD: алгоритм проектирования сверхполных словарей для разреженного представления». Труды IEEE по обработке сигналов . 54 (11): 4311–4322. Bibcode : 2006ITSP...54.4311A. doi : 10.1109/tsp.2006.881199. S2CID  7477309.
13. Мюллер, Ральф Р.; Геде, Бернхард; Берейхи, Али (2021). «Кодирование линейных вычислений». arXiv : 2102.00398 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
14. Пати, Й.; Резаифар, Р.; Кришнапрасад, П. (1993). «Ортогональное сопоставление: рекурсивное функциональное приближение с приложениями к вейвлет-разложению». Труды 27-й Асиломарской конференции по сигналам, системам и компьютерам . С. 40–44. CiteSeerX 10.1.1.348.5735 . doi :10.1109/acssc.1993.342465. ISBN  978-0-8186-4120-6. S2CID  16513805. {{cite book}}: |journal=проигнорировано ( помощь )
15. Дэвис, Г.; Маллат, С.; Чжан, З. (1994). «Адаптивные частотно-временные разложения с соответствующими преследованиями». Optical Engineering . 33 (7): 2183. Bibcode :1994OptEn..33.2183D. doi :10.1117/12.173207.
16. Ding, J.; Chen, L.; Gu, Y. (2013). «Анализ возмущений ортогонального поиска соответствия». Труды IEEE по обработке сигналов . 61 (2): 398–410. arXiv : 1106.3373 . Bibcode :2013ITSP...61..398D. doi :10.1109/TSP.2012.2222377. ISSN  1941-0476. S2CID  17166658.
17. Mather, John (1990). "Инкрементный многопараметрический алгоритм". Протокол конференции 1990 года Двадцать четвертая Асиломарская конференция по сигналам, системам и компьютерам, 1990. Том 1. стр. 368. doi :10.1109/ACSSC.1990.523362. ISBN 0-8186-2180-X. ISSN  1058-6393. S2CID  61327933.
18. "Кусочно-линейное разделение источников", Р. Грибонвал, Proc. SPIE '03, 2003
19. Тропп, Джоэл ; Гилберт, А.; Штраус, М. (2006). «Алгоритмы для одновременных разреженных приближений; Часть I: Жадное преследование». Signal Proc. – Разреженные приближения в обработке сигналов и изображений . 86 (3): 572–588. Bibcode : 2006SigPr..86..572T. doi : 10.1016/j.sigpro.2005.05.030.
20. Перрине, Лоран У. (2015). «Разреженные модели для компьютерного зрения». Биологически вдохновленное компьютерное зрение . стр. 319–346. arXiv : 1701.06859 . doi :10.1002/9783527680863.ch14. ISBN 9783527680863. S2CID  2085413.
21. Тропп, Джоэл А.; Гилберт, Анна К. (2007). «Восстановление сигнала из случайных измерений с помощью ортогонального сопоставления» (PDF) . Труды IEEE по теории информации . 53 (12): 4655–4666. doi :10.1109/tit.2007.909108. S2CID  6261304.
22. Донохо, Дэвид Л.; Цайг, Яаков; Дрори, Иддо; Жан-Люк, Старк (2006). «Разреженное решение недоопределенных линейных уравнений с помощью поэтапного ортогонального поиска соответствия». Труды IEEE по теории информации . 58 (2): 1094–1121. doi :10.1109/tit.2011.2173241. S2CID  7923170.
23. Needell, D.; Tropp, JA (2009). "CoSaMP: Итеративное восстановление сигнала из неполных и неточных выборок". Applied and Computational Harmonic Analysis . 26 (3): 301–321. arXiv : 0803.2392 . doi : 10.1016/j.acha.2008.07.002. S2CID  1642637.
24. Ван, Дж.; Квон, С.; Шим, Б. (2012). «Обобщенное ортогональное сопоставление». Труды IEEE по обработке сигналов . 60 (12): 6202–6216. arXiv : 1111.6664 . Bibcode : 2012ITSP...60.6202J. doi : 10.1109/TSP.2012.2218810. S2CID  2585677.
25. Квон, С.; Ван, Дж.; Шим, Б. (2014). «Multipath Matching Pursuit». Труды IEEE по теории информации . 60 (5): 2986–3001. arXiv : 1308.4791 . doi : 10.1109/TIT.2014.2310482. S2CID  15134308.