Соответствие алгоритмов преследования

Избыточные словари и разреженность

Представление сигнала в конкретном базисе включает нахождение уникального набора коэффициентов расширения в этом базисе. Хотя существует много преимуществ для представления сигнала в базисе, в частности, ортогональном базисе, существуют также недостатки.

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

Реальные сигналы часто содержат функции, которые запрещают разреженное представление в любом едином базисе. Для этих сигналов вы хотите возможность выбирать векторы из множества, не ограниченного одним базисом. Поскольку вы хотите убедиться, что можете представлять каждый вектор в пространстве, словарь векторов, из которых вы выбираете, должен охватывать пространство. Однако, поскольку набор не ограничивается одним базисом, словарь не является линейно независимым.

Поскольку векторы в словаре не являются линейно независимым множеством, представление сигнала в словаре не является уникальным. Однако, создав избыточный словарь, можно расширить свой сигнал в наборе векторов, которые адаптируются к временным частотным или временным характеристикам вашего сигнала. Вы можете свободно создавать словарь, состоящий из объединения нескольких основ. Для примера можно сформировать основание для пространства квадратно-интегрируемых функций, состоящих из вейвлета пакетного базиса и локального косинусоидного базиса. Вейвлет базиса пакета хорошо адаптирована к сигналам с различным поведением в различных частотных интервалах. Локальный базис косинуса хорошо адаптирован к сигналам с различным поведением в различных временных интервалах. Способность выбирать векторы из каждой из этих основ значительно увеличивает вашу способность редко представлять сигналы с меняющимися характеристиками.

Нелинейное приближение в словарях

Определите словарь как набор элементарных базовых блоков с единичной нормой для вашего пространства сигналов. Эти векторы с единичной нормой называются атомами. Если атомы словаря охватывают все пространство сигналов, словарь завершен.

Если атомы словаря образуют линейно-зависимый набор, словарь является избыточным. В большинстве приложений поиска соответствия словарь является полным и избыточным.

Позвольте {, _k} обозначить атомы словаря. Предположим, что словарь полон и избыточен. Нет уникального способа представить сигнал из пространства как линейную комбинацию атомов.

$x = \sum_{k} α_{k} ϕ_{k}$

Важный вопрос заключается в том, существует ли наилучший способ. Интуитивно удовлетворяющий способ выбора наилучшего представления - это выбор, _{который} с сигналом дает самые большие скалярные произведения (в абсолютном значении). Для примера, лучший сингл

$max_{k} | < x, ϕ_{k} > |$

который для атома единичной нормы является величиной скалярной проекции на подпространство, простираемое на

Центральной задачей в сопоставлении преследования является то, как вы выбираете оптимальное M -термовое расширение своего сигнала в словаре .

Basic Matching Pursuit

Предположим, что, словарь атомов обозначается как матрица N на M с M > N. Если полный, избыточный словарь образует систему координат для пространства сигналов, можно получить вектор коэффициента расширения минимальной L2 нормы при помощи оператора системы координат.

$Φ^{†} = Φ^{*} {(Φ Φ^{*})}^{- 1}$

Однако вектор коэффициентов, возвращенный оператором системы координат, не сохраняет разреженность. Если сигнал разрежен в словаре, коэффициенты расширения, полученные с помощью оператора канонической системы координат, обычно не отражают эту разреженность. Разреженность вашего сигнала в словаре является признаком, который вы обычно хотите сохранить. Соответствие преследованию адресует сохранение разреженности непосредственно.

Matching pursuit является жадным алгоритмом, который вычисляет лучшее нелинейное приближение к сигналу в полном, избыточном словаре. Совпадающее преследование создает последовательность разреженных приближений к сигналу пошагово. Позвольте Φ = _{φk}, обозначают словарь атомов нормы модуля. Позволь f быть твоим сигналом.

Начните, определив R⁰f = f
Начните поиск соответствия, выбрав атом из словаря, который максимизирует абсолютное значение скалярного произведения с R⁰f = f. Обозначить атом _как
Сформируйте невязку R¹f путем вычитания ортогональной проекции R⁰f в пространство, охватываемое

$R^{1} f = R^{0} f - 〈 R^{0} f, ϕ_{p} 〉 ϕ_{p}$
Итерация путем повторения шагов 2 и 3 на невязке.

$R^{m + 1} f = R^{m} f - 〈 R^{m} f, ϕ_{k} 〉 ϕ_{k}$
Остановите алгоритм, когда вы достигнете некоторого заданного критерия остановки.

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

Чтобы проиллюстрировать это, рассмотрим следующий пример. Пример не предназначен для представления рабочего совпадающего алгоритма преследования.

Рассмотрим следующий словарь для евклидова 2-пространства. Этот словарь является системой координат равной нормы.

${(\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 1 / 2 \\ \sqrt{3} / 2 \end{matrix}), (\begin{matrix} - 1 / \sqrt{2} \\ - 1 / \sqrt{2} \end{matrix})}$

Предположим, что у вас есть следующий сигнал.

$(\begin{matrix} 1 \\ 1 / 2 \end{matrix})$

Следующий рисунок иллюстрирует этот пример. Атомы словаря имеют красный цвет. Вектор сигнала в синем цвете.

Создайте этот словарь и сигнал в MATLAB^®.

dictionary = [1 0; 1/2 sqrt(3)/2; -1/sqrt(2) -1/sqrt(2)]';
x = [1 1/2]';

Вычислите внутренние (скалярные) продукты между атомами сигнала и словаря.

scalarproducts = dictionary'*x;

Самый большой скалярный продукт по абсолютному значению происходит между сигналом и [-1/sqrt(2); -1/sqrt(2)]. Это ясно, потому что угол между этими двумя векторами почти и равен

Сформируйте невязку путем вычитания ортогональной проекции сигнала на [-1/sqrt(2); -1/sqrt(2)] от сигнала. Затем вычислите скалярные произведения остаточного (нового сигнала) с оставшимися атомами словаря. Не обязательно включать [-1/sqrt(2); -1/sqrt(2)] потому что невязка ортогональна этому вектору по конструкции.

residual = x-scalarproducts(3)*dictionary(:,3);
scalarproducts = dictionary(:,1:2)'*residual;

Самый большой скалярный продукт по абсолютному значению получен с [1;0]. Лучшими двумя атомами в словаре из двух итераций являются [-1/sqrt(2); -1/sqrt(2)] и [1;0]. Если вы итератируете невязку, вы видите, что выход больше не ортогональен выбранному первому атому. Другими словами, алгоритм ввел компонент, который не ортогональен диапазону выбранного первого атома. Этот факт и связанные с ним осложнения со сходимостью аргументируют в пользу ортогонального совпадения преследования (OMP).

Ортогональное совпадение преследования

В ортогональном поиске соответствия (OMP), невязка всегда ортогональен диапазону уже выбранных атомов. Это приводит к сходимости для d -мерного вектора после наиболее d шагов .

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

Алгоритм OMP:

Обозначите свой сигнал по f. Инициализируйте невязку R⁰f = f.
Выберите атом, который максимизирует абсолютное значение скалярного произведения с R⁰f = f. Обозначить атом _как
Сформируйте матрицу, Φ, с ранее выбранными атомами в качестве столбцов. Задайте оператор ортогональной проекции на диапазон столбцов Φ.

$P = Φ {(Φ^{*} Φ)}^{- 1} Φ^{*}$
Примените оператор ортогональной проекции к невязке.
Обновите невязку.

$R^{m + 1} f = (I - P) R^{m} f$
I - матрица тождеств.

Ортогональное совпадение обеспечивает, чтобы компоненты в диапазоне ранее выбранных атомов не вводились на последующих стадиях.

Слабое ортогональное совпадение преследования

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

$| 〈 x, ϕ_{p} 〉 | \geq α \max_{k} | 〈 x, ϕ_{k} 〉 |, α \in (0, 1]$

Это известно как слабое совпадение преследования.

Документация