Разреженное кодирование некоторых идей алгоритма (MP/OMP/BP)

MP(Matching Pursuits)

1.Основная идея:Из словарной матрицы D (библиотека сверхполных атомов) выберите1Атом (то есть столбец), который лучше всего соответствует сигналу y, построить разреженную аппроксимацию и найти невязку сигнала, а затем продолжить выборАтом, который лучше всего соответствует остатку сигнала, итеративно сигнал y может быть линейно суммирован этими атомами плюс конечное остаточное значение. Ясно, что если остаточные значения находятся в пренебрежимо малом диапазоне, сигнал y является линейной комбинацией этих атомов.

2.Как выбрать атом, который лучше всего соответствует сигналу y?

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

r0=y;

Подумайте: почемуpi*???Не следует ли вычислять вектор проекции pi*/|Pi|^2?

OMP(Orthogonal Matching Pursuits)

1.Основная идея:В алгоритме МП вертикальная проекция сигнала (остатка) на выбранные атомы неортогональна, что делает результаты каждой итерации не много оптимальными, а субоптимальными, и для сходимости требуется много итераций. Улучшения алгоритма OMP:Ортогонализация всех выбранных атомов на каждом шаге разложения, что ускоряет сходимость алгоритма OMP при том же требовании к точности.

2.Как ортогонализовать:

Разница между алгоритмами OMP и MP,Его невязка ортогональна каждому из предыдущих компонентов, поэтому этот алгоритм имеет на одну ортогональность больше, и ортогонален только самый последний выбранный элемент в МП.

3.Шаги алгоритма:

BP(Basis Pursuits)

1. Основная идея: задача оптимизации

Поскольку a не выполняет неотрицательных ограничений, а u>0, v>0, размер u и v не ограничен;

PS: абсолютное значение целевой функции удалено для решения:

Итак, задача оптимизации становится:

Решение:

Недостатки: алгоритмы оптимизации, такие как BP, имеют более высокую вычислительную сложность и большее время реконструкции, чем жадные алгоритмы, такие как MP и OMP.

FOCUSS(focal underdetermined system solver)

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

использованная литература

Алгоритм MP и алгоритм OMP и их идеи

Введение в игру преследования (MP)

Основное преследование (BP) для алгоритмов реконструкции сжатых измерений