WikiDer > Основная цель шумоподавления

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

${ displaystyle min _ {x} left ({ frac {1} {2}} | y-Ax | _ {2} ^ {2} + lambda | x | _ {1} верно),}$

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

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

${ displaystyle min _ {x} | x | _ {1} { text {при условии}} | y-Ax | _ {2} ^ {2} leq delta,}$

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

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

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

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

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

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

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

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

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

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

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