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

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

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

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

{\ Displaystyle f (t) \ приблизительно {\ hat {f}} _ {N} (t): = \ sum _ {n = 1} ^ {N} a_ {n} g _ {\ gamma _ {n}} (t)}

{\ Displaystyle f (t) \ приблизительно {\ hat {f}} _ {N} (t): = \ sum _ {n = 1} ^ {N} a_ {n} g _ {\ gamma _ {n}} (t)}

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

{\ Displaystyle R_ {N + 1} = е - {\ шляпа {f}} _ {N}}

{\ Displaystyle R_ {N + 1} = е - {\ шляпа {f}} _ {N}}

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

{\ displaystyle \ min _ {x} \ | f-Dx \ | _ {2} ^ {2} \ {\ text {при условии}} \ \ | x \ | _ {0} \ leq N,}

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

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

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

Содержание

1 Алгоритм
2 свойства
3 Приложения
4 расширения
5 См. Также
6 Ссылки

Алгоритм

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

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

Algorithm Matching Pursuit Input: Signal:  $f(t)$  $f(t)$ , dictionary  $D$  $D$  with normalized columns  $g_{i}$  $g_{i}$ . Output: List of coefficients  $(a_{n})_{n=1}^{N}$  $(a_{n})_{n=1}^{N}$  and indices for corresponding atoms  $(\gamma _{n})_{n=1}^{N}$  $(\gamma _{n})_{n=1}^{N}$ . Initialization:  $R_{1}\,\leftarrow \,f(t)$  $R_{1}\,\leftarrow \,f(t)$ ;  $n\,\leftarrow \,1$  $n\,\leftarrow \,1$ ; Repeat: Find  $g_{\gamma _{n}}\in D$  $g_{\gamma _{n}}\in D$  with maximum inner product  $|\langle R_{n},g_{\gamma _{n}}\rangle |$  $|\langle R_{n},g_{\gamma _{n}}\rangle |$ ;  $a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle$  $a_{n}\,\leftarrow \,\langle R_{n},g_{\gamma _{n}}\rangle$ ;  $R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}$  $R_{n+1}\,\leftarrow \,R_{n}-a_{n}g_{\gamma _{n}}$ ;  $n\,\leftarrow \,n+1$  $n\,\leftarrow \,n+1$ ; Until stop condition (for example:  $\|R_{n}\|lt;\mathrm {threshold}$  $\|R_{n}\|lt;\mathrm {threshold}$ ) return

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

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

Свойства

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

{\ Displaystyle \ | е \ | ^ {2} = \ | R_ {N + 1} \ | ^ {2} + \ sum _ {n = 1} ^ {N} {| a_ {n} | ^ {2 }}}

{\ Displaystyle \ | е \ | ^ {2} = \ | R_ {N + 1} \ | ^ {2} + \ sum _ {n = 1} ^ {N} {| a_ {n} | ^ {2 }}}

В случае, если векторы в являются ортонормированными, а не избыточными, тогда MP является формой анализа главных компонент ${\ displaystyle D}$ $D$

Приложения

Поиск соответствия применяется к кодированию сигналов, изображений и видео, представлению и распознаванию форм, кодированию трехмерных объектов и в междисциплинарных приложениях, таких как мониторинг состояния конструкций. Было показано, что оно работает лучше, чем кодирование на основе DCT, для низких скоростей передачи как по эффективности кодирования, так и по качеству изображения. Основная проблема с поиском соответствия - вычислительная сложность кодировщика. В базовой версии алгоритма поиск в большом словаре нужно искать на каждой итерации. Улучшения включают использование приблизительных словарных представлений и неоптимальных способов выбора наилучшего соответствия на каждой итерации (извлечение атомов). Алгоритм согласованного преследования используется в MP / SOFT, методе моделирования квантовой динамики.

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

Расширения

Популярным расширением Matching Pursuit (MP) является его ортогональная версия: Orthogonal Matching Pursuit (OMP). Основное отличие от MP состоит в том, что после каждого шага все коэффициенты, извлеченные на данный момент, обновляются путем вычисления ортогональной проекции сигнала на подпространство, охватываемое набором выбранных атомов. Это может привести к результатам лучше, чем стандартный MP, но требует больше вычислений. Было показано, что OMP имеет гарантии стабильности и производительности при определенных ограниченных условиях изометрии.

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

Поиск совпадений связан с областью сжатого зондирования и был расширен исследователями в этом сообществе. Известными расширениями являются поиск по ортогональному согласованию (OMP), поэтапный OMP (StOMP), поиск по согласованию с компрессионной выборкой (CoSaMP), обобщенный OMP (gOMP) и многолучевой поиск по согласованию (MMP).

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

Рекомендации