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

Проблема оптимизации

Преследование базиса — это математическая задача оптимизации вида

${\displaystyle \min _{x}\|x\|_{1}\quad {\text{subject to}}\quad y=Ax,}$

где x — N -мерный вектор решения (сигнал), y — M - мерный вектор наблюдений (измерений), A — матрица преобразования размером M  ×  N (обычно матрица измерений) и M  <  N.

Обычно он применяется в случаях, когда имеется недоопределенная система линейных уравнений y  =  Ax , которая должна быть удовлетворена точно, и требуется найти наиболее разреженное решение в смысле L _{1 .}

Когда желательно добиться точного равенства Ax и y в обмен на более разреженный x , предпочтительным является метод шумоподавления с преследованием базиса .

Задачи поиска базиса можно преобразовать в задачи линейного программирования за полиномиальное время и наоборот, что делает два типа задач полиномиально эквивалентными. ^[1]

Эквивалентность линейному программированию

Задачу преследования базиса можно преобразовать в задачу линейного программирования, сначала заметив, что

${\displaystyle {\begin{aligned}\|x\|_{1}&=|x_{1}|+|x_{2}|+\ldots +|x_{n}|\\&=(x_{1}^{+}+x_{1}^{-})+(x_{2}^{+}+x_{2}^{-})+\ldots +(x_{n}^{+}+x_{n}^{-})\end{aligned}}}$

где . Эта конструкция выводится из ограничения , где значение должно храниться в или в зависимости от того, больше или меньше нуля, соответственно. Хотя диапазон значений и может потенциально удовлетворять этому ограничению, решатели, использующие симплексный алгоритм, найдут решения, где одно или оба из или равны нулю, что приводит к соотношению . ${\displaystyle x_{i}^{+},x_{i}^{-}\geq 0}$ ${\displaystyle x_{i}=x_{i}^{+}-x_{i}^{-}}$ ${\displaystyle |x_{i}|}$ ${\displaystyle x_{i}^{+}}$ ${\displaystyle x_{i}^{-}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}^{+}}$ ${\displaystyle x_{i}^{-}}$ ${\displaystyle x_{i}^{+}}$ ${\displaystyle x_{i}^{-}}$ ${\displaystyle |x_{i}|=(x_{i}^{+}+x_{i}^{-})}$

Из этого расширения задачу можно переформулировать в канонической форме следующим образом: ^[1]

${\displaystyle {\begin{aligned}&{\text{Find a vector}}&&(\mathbf {x^{+}} ,\mathbf {x^{-}} )\\&{\text{that minimizes}}&&\mathbf {1} ^{T}\mathbf {x^{+}} +\mathbf {1} ^{T}\mathbf {x^{-}} \\&{\text{subject to}}&&A\mathbf {x^{+}} -A\mathbf {x^{-}} =\mathbf {y} \\&{\text{and}}&&\mathbf {x^{+}} ,\mathbf {x^{-}} \geq \mathbf {0} .\end{aligned}}}$

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

• Базис преследование шумоподавления
• Сжатое зондирование
• Спектр частот
• Групповое тестирование
• Лассо (статистика)
• Спектральный анализ методом наименьших квадратов
• Соответствующее преследование
• Разреженное приближение

Примечания

1. AM Tillmann Эквивалентность линейного программирования и базисного преследования , PAMM (Труды по прикладной математике и механике) Том 15, 2015, стр. 735-738, DOI: 10.1002/PAMM.201510351

Ссылки и дополнительная литература

• Стивен Бойд, Ливен Ванденберг: Выпуклая оптимизация , Cambridge University Press, 2004, ISBN  9780521833783 , стр. 337–337
• Саймон Фукар, Хольгер Раухут: Математическое введение в компрессионное зондирование . Springer, 2013, ISBN 9780817649487 , стр. 77–110 

Внешние ссылки

• Шаобин Чен, Дэвид Донохо: Basis Pursuit
• Теренс Тао : Сжатое восприятие. Серия лекций Малера (слайды)