Разреженное приближение

разреженного приближения (также известная как разреженное представление Теория ) имеет дело с разреженными решениями для систем линейных уравнений . Методы поиска этих решений и их использования в приложениях нашли широкое применение в обработке изображений , обработке сигналов , машинном обучении , медицинской визуализации и многом другом.

Разреженное разложение

Бесшумные наблюдения

Рассмотрим линейную систему уравнений $x=D\alpha$, где $D$ является недоопределенным $m\times p$ матрица $(m<p)$ и $x\in \mathbb {R} ^{m},\alpha \in \mathbb {R} ^{p}$. Матрица $D$ (обычно считается полным рангом) называется словарем, а $x$ является сигналом интереса. Основная проблема разреженного представления определяется как поиск максимально разреженного представления. $\alpha$ удовлетворяющий $x=D\alpha$. В связи с неопределённостью характера $D$, эта линейная система допускает, вообще говоря, бесконечно много возможных решений, и среди них мы ищем решение с наименьшим количеством ненулевых значений. Формально мы решаем

$\min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}x=D\alpha ,$

где $\|\alpha \|_{0}=\#\{i:\alpha _{i}\neq 0,\,i=1,\ldots ,p\}$ это $\ell _{0}$ псевдонорма, которая подсчитывает количество ненулевых компонентов $\alpha$. Эта задача, как известно, является NP-трудной со сведением к NP-полным задачам выбора подмножества в комбинаторной оптимизации .

Редкость $\alpha$ подразумевается, что лишь немногие ( $k\ll m<p$) компоненты в нем ненулевые. Основной мотивацией столь разреженной декомпозиции является желание дать как можно более простое объяснение происходящему. $x$ как линейная комбинация как можно меньшего количества столбцов из $D$, также называемые атомами. Таким образом, сигнал $x$ можно рассматривать как молекулу, состоящую из нескольких фундаментальных элементов, взятых из $D$.

Хотя поставленная выше задача действительно является NP-сложной, ее решение часто можно найти с помощью аппроксимационных алгоритмов. Одним из таких вариантов является выпуклая релаксация задачи, полученная с помощью $\ell _{1}$-норма вместо $\ell _{0}$, где $\|\alpha \|_{1}$ просто суммирует абсолютные значения записей в $\alpha$. Это известно как алгоритм поиска базиса (BP), который можно обрабатывать с помощью любого решателя линейного программирования . Альтернативный метод аппроксимации — это жадный метод, такой как поиск совпадений (MP), который находит местоположение ненулевых значений по одному.

Удивительно, но в мягких условиях на $D$ (используя искру (математика) , взаимную когерентность или свойство ограниченной изометрии ) и уровень разреженности решения, $k$, можно показать, что проблема разреженного представления имеет единственное решение, и BP и MP гарантированно найдут его идеально.

Шумные наблюдения

Часто наблюдаемый сигнал $x$ шумно. Ослабляя ограничение равенства и вводя $\ell _{2}$-норма для термина подгонки данных, проблема разреженной декомпозиции становится

$\min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2},$

или представить в лагранжевой форме:

$\min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{0}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},$

где $\lambda$ заменяет $\epsilon$.

Как и в бесшумном случае, эти две задачи в целом являются NP-сложными, но их можно аппроксимировать с помощью алгоритмов преследования. Точнее, изменение $\ell _{0}$ к $\ell _{1}$-норма, получаем

$\min _{\alpha \in \mathbb {R} ^{p}}\lambda \|\alpha \|_{1}+{\frac {1}{2}}\|x-D\alpha \|_{2}^{2},$

который известен как базовое подавление шума . Точно так же поиск совпадений можно использовать для аппроксимации решения вышеупомянутых задач, находя местоположения ненулевых значений по одному, пока не будет достигнут порог ошибки. Здесь также теоретические гарантии предполагают, что BP и MP приводят к почти оптимальным решениям в зависимости от свойств $D$ и мощность решения $k$. Другой интересный теоретический результат относится к случаю, когда $D$ является унитарной матрицей . В этом предположении поставленные выше задачи (как с $\ell _{0}$ или $\ell _{1}$) допускают решения замкнутой формы в виде нелинейной усадки.

Вариации

Существует несколько вариантов основной задачи разреженной аппроксимации.

Структурированная разреженность : в исходной версии задачи можно выбрать любой атом в словаре. В структурированной (блочной) модели разреженности вместо индивидуального выбора атомов необходимо выбирать группы из них. Эти группы могут пересекаться и иметь разный размер. Цель состоит в том, чтобы представлять $x$ так что он разрежен при создании этой блочной структуры.

Совместное (совместное) разреженное кодирование : исходная версия проблемы определена для одного сигнала. $x$. В модели совместного (совместного) разреженного кодирования доступен набор сигналов, каждый из которых, как полагают, возникает из (почти) одного и того же набора атомов из $D$. В этом случае задача преследования направлена ​​на восстановление набора разреженных представлений, которые лучше всего описывают данные, одновременно заставляя их использовать одну и ту же (или близкую) поддержку.

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

Алгоритмы

Как уже упоминалось выше, существуют различные алгоритмы аппроксимации (также называемые алгоритмами преследования ), которые были разработаны для решения проблемы разреженного представления:

$\min _{\alpha \in \mathbb {R} ^{p}}\|\alpha \|_{0}{\text{ subject to }}\|x-D\alpha \|_{2}^{2}\leq \epsilon ^{2}.$

Ниже мы упомянем некоторые из этих основных методов.

• Поиск совпадений — это жадный итерационный алгоритм для приблизительного решения вышеуказанной проблемы. Он работает путем постепенного поиска местоположений ненулевых значений в $\alpha$ по одному. Основная идея состоит в том, чтобы на каждом этапе найти столбец (атом) в $D$ который лучше всего коррелирует с текущим остатком (инициализированным $x$), а затем обновляем этот остаток, чтобы учесть новый атом и его коэффициент. Соответствующее преследование может выбрать один и тот же атом несколько раз.
• Поиск ортогонального сопоставления очень похож на поиск сопоставления, с одним существенным отличием: на каждом этапе алгоритма все ненулевые коэффициенты обновляются методом наименьших квадратов . Как следствие, остаток ортогонален уже выбранным атомам, и, следовательно, атом нельзя выбрать более одного раза.
• Поэтапные жадные методы: улучшенные варианты вышеперечисленных представляют собой алгоритмы, которые работают жадно, добавляя две важные функции: (i) возможность добавлять группы ненулевых значений за раз (вместо одного ненулевого числа за раунд); и (ii) включение этапа обрезки в каждом раунде, на котором несколько атомов удаляются с носителя. Представителями этого подхода являются алгоритм Subspace-Pursuit и CoSaMP.

• Преследование базиса решает выпуклую расслабленную версию задачи, заменяя $\ell _{0}$ путем $\ell _{1}$-норм. Обратите внимание, что это только определяет новую цель, оставляя открытым вопрос об алгоритме, который будет использоваться для получения желаемого решения. Обычно такими алгоритмами считаются IRLS , LARS и итеративные методы мягкого сжатия.

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

Приложения

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

См. также

• Сжатое зондирование
• Редкое изучение словаря
• К-СВД
• Лассо (статистика)
• Регуляризация (математика) и обратные задачи