Шумоподавление базового преследования

В прикладной математике статистике шумоподавление и с поиском базиса (BPDN) относится к задаче математической оптимизации формы

\min _{x}\left({\frac {1}{2}}\|y-Ax\|_{2}^{2}+\lambda \|x\|_{1}\right),

где $\lambda$ это параметр, который контролирует компромисс между разреженностью и точностью реконструкции, $x$ это $N\times 1$ вектор решения, $y$ это $M\times 1$ вектор наблюдений, $A$ это $M\times N$ преобразовать матрицу и $M<N$ . Это пример выпуклой оптимизации .

Некоторые авторы называют шумоподавление преследования базиса следующей тесно связанной проблемой:

\min _{x}\|x\|_{1}{\text{ subject to }}\|y-Ax\|_{2}^{2}\leq \delta ,

который для любого данного $\lambda$ , эквивалентно неограниченной формулировке для некоторого (обычно неизвестного априори ) значения $\delta$ . Эти две проблемы очень похожи. На практике обычно отдается предпочтение неограниченной формулировке, для которой разрабатываются наиболее специализированные и эффективные вычислительные алгоритмы.

Любой из типов шумоподавления с поиском базиса решает проблему регуляризации с компромиссом между небольшим остатком (что делает $y$ близко к $Ax$ в терминах квадратичной ошибки) и делая $x$ простой в $\ell _{1}$ -норм смысл. Его можно рассматривать как математическое выражение бритвы Оккама , позволяющее найти простейшее возможное объяснение (т. е. такое, которое дает $\min _{x}\|x\|_{1}$ ) способен объяснить наблюдения $y$ .

Точные решения для подавления шума при поиске базиса часто являются лучшим вычислительно доступным приближением недоопределенной системы уравнений. ^{[ нужна ссылка ]} Шумоподавление при поиске базиса имеет потенциальное применение в статистике (см. LASSO метод регуляризации ), сжатии изображений и сжатом измерении .

Когда $\delta =0$ , эта проблема становится базис слежение .

Базовое подавление шума было введено Ченом и Донохо в 1994 году. ^[1] в области обработки сигналов. В статистике он хорошо известен под названием LASSO , после того как был введен Тибширани в 1996 году.

Решение проблемы шумоподавления при поиске базиса

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

Несколько популярных методов решения проблемы шумоподавления с поиском базиса включают в себя алгоритм «в толпе» (быстрый решатель больших и редких задач). ^[2]), гомотопическое продолжение , продолжение с фиксированной точкой (частный случай алгоритма вперед-назад ^[3]) и спектральный проецируемый градиент для минимизации L1 (который фактически решает LASSO , связанную проблему).

Ссылки

^ Чен, Шаобин; Донохо, Д. (1994). «Погоня за базой». Материалы 28-й Асиломарской конференции по сигналам, системам и компьютерам 1994 г. Том. 1. С. 41–44. дои : 10.1109/ACSSC.1994.471413 . ISBN 0-8186-6405-3 . S2CID 96447294 .
^ См. Гилл, Патрик Р.; Ван, Альберт; Мольнар, Алеша (2011). «Алгоритм в толпе для быстрого шумоподавления при поиске базиса». Транзакции IEEE по обработке сигналов . 59 (10): 4595–4605. дои : 10.1109/TSP.2011.2161292 . S2CID 15320645 ; демонстрационный код MATLAB доступен [1] .
^ «Алгоритм вперед-назад» . Архивировано из оригинала 16 февраля 2014 года.

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

Список решателей BPDN на вики-сайте разреженного и низкорангового приближения .

[1] Чен, Шаобин; Донохо, Д. (1994). «Погоня за базой». Материалы 28-й Асиломарской конференции по сигналам, системам и компьютерам 1994 г. Том. 1. С. 41–44. дои : 10.1109/ACSSC.1994.471413 . ISBN 0-8186-6405-3 . S2CID 96447294 .

[2] См. Гилл, Патрик Р.; Ван, Альберт; Мольнар, Алеша (2011). «Алгоритм в толпе для быстрого шумоподавления при поиске базиса». Транзакции IEEE по обработке сигналов . 59 (10): 4595–4605. дои : 10.1109/TSP.2011.2161292 . S2CID 15320645 ; демонстрационный код MATLAB доступен [1] .

[3] «Алгоритм вперед-назад» . Архивировано из оригинала 16 февраля 2014 года.

[1]

[2]

[3]