Основная цель шумоподавления - Basis pursuit denoising

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

внешняя ссылка

• Список Решатели BPDN на вики по аппроксимациям с низким и низким рангом.