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

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

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

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

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

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

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

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

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

Удивительно, но при мягких условиях (используя искру (математику) , взаимную когерентность или свойство ограниченной изометрии ) и уровень разреженности решения, можно показать, что проблема разреженного представления имеет единственное решение, и BP и MP гарантированно найдут его идеально. ^{[1] [2] [3]} ${\displaystyle D}$ ${\displaystyle k}$

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

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

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

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

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

где заменяется . ${\displaystyle \lambda }$ ${\displaystyle \epsilon }$

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

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

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

Вариации

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

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

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

Другие структуры : В более широком смысле, проблема разреженной аппроксимации может быть поставлена ​​при принудительном применении определенной желаемой структуры к шаблону ненулевых местоположений в . Два случая, представляющие интерес и тщательно изученные, — это древовидная структура и, в более общем смысле, распределенная поддержка Больцмана. ^[9] ${\displaystyle \alpha }$

Алгоритмы

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

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

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

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

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

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

Приложения

Идеи и алгоритмы разреженной аппроксимации широко использовались в обработке сигналов , обработке изображений , машинном обучении , медицинской визуализации , обработке массивов , интеллектуальном анализе данных и т. д. В большинстве этих приложений неизвестный интересующий сигнал моделируется как разреженная комбинация нескольких атомов из заданного словаря, и это используется в качестве регуляризации проблемы. Эти проблемы обычно сопровождаются механизмом обучения словаря , который стремится наилучшим образом соответствовать модели заданным данным. Использование моделей, вдохновленных разрежением, привело к получению современных результатов в широком наборе приложений. ^{[12] [13] [14]} Недавние работы показывают, что существует тесная связь между моделированием разреженного представления и глубоким обучением. ^[15] ${\displaystyle D}$

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

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

Ссылки

1. Донохо, Д. Л. и Элад, М. (2003). «Оптимально разреженное представление в общих (неортогональных) словарях с помощью минимизации L1» (PDF) . Труды Национальной академии наук . 100 (5): 2197–2202. Bibcode :2003PNAS..100.2197D. doi : 10.1073/pnas.0437847100 . PMC  153464 . PMID  16576749.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
2. Tropp, JA (2004). «Жадность — это хорошо: результаты алгоритмов для разреженной аппроксимации» (PDF) . IEEE Transactions on Information Theory . 50 (10): 2231–2242. CiteSeerX 10.1.1.321.1443 . doi :10.1109/TIT.2004.834793. S2CID  675692. 
3. Донохо, ДЛ (2006). «Для большинства больших недоопределенных систем линейных уравнений минимальное решение в норме l1 также является самым разреженным решением» (PDF) . Сообщения по чистой и прикладной математике . 56 (6): 797–829. doi :10.1002/cpa.20132. S2CID  8510060.
4. Elad, M. (2010). Разреженные и избыточные представления: от теории к приложениям в обработке сигналов и изображений . Springer. CiteSeerX 10.1.1.331.8963 . doi :10.1007/978-1-4419-7011-4. ISBN  978-1441970107.
5. Донохо, Д. Л., Элад, М. и Темпляков, В. (2006). «Стабильное восстановление разреженных сверхполных представлений при наличии шума» (PDF) . IEEE Transactions on Information Theory . 52 (1): 6–18. CiteSeerX 10.1.1.125.5610 . doi :10.1109/TIT.2005.860430. S2CID  14813938. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
6. Tropp, JA (2006). «Просто расслабьтесь: методы выпуклого программирования для идентификации разреженных сигналов в шуме» (PDF) . IEEE Transactions on Information Theory . 52 (3): 1030–1051. CiteSeerX 10.1.1.184.2957 . doi :10.1109/TIT.2005.864420. S2CID  6496872. 
7. Eldar, YC, Kuppinger, P. и Bolcskei, H. (2009). «Блочно-разреженные сигналы: отношения неопределенности и эффективное восстановление». IEEE Transactions on Signal Processing . 58 (6): 3042–3054. arXiv : 0906.3173 . Bibcode : 2010ITSP...58.3042E. doi : 10.1109/TSP.2010.2044837. S2CID  335122.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
8. Tropp, JA, Gilbert, AC и Strauss, MJ (2006). «Алгоритмы для одновременной разреженной аппроксимации. Часть I: Жадное преследование». Обработка сигналов . 86 (3): 572–588. doi :10.1016/j.sigpro.2005.05.030.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
9. Пелег, Т. Элдар, YC и Элад, М. (2012). «Использование статистических зависимостей в разреженных представлениях для восстановления сигналов». Труды IEEE по обработке сигналов . 60 (5): 2286–2303. arXiv : 1010.5734 . Bibcode :2012ITSP...60.2286P. doi :10.1109/TSP.2012.2188520. S2CID  3179803.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
10. Needell, D. и Tropp, JA (2009). "CoSaMP: Итеративное восстановление сигнала из неполных и неточных образцов". Applied and Computational Harmonic Analysis . 26 (3): 301–321. arXiv : 0803.2392 . doi : 10.1016/j.acha.2008.07.002.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
11. Зибулевский, М. и Элад, М. (2010). "Оптимизация L1-L2 в обработке сигналов и изображений" (PDF) . Журнал обработки сигналов IEEE . 27 (3): 76–88. Bibcode : 2010ISPM...27...76Z. doi : 10.1109/MSP.2010.936023. S2CID  2783691.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
12. Баранюк, RG Candes, E. Elad, M. и Ma, Y. (2010). «Применение разреженного представления и сжатого зондирования». Труды IEEE . 98 (6): 906–909. doi :10.1109/JPROC.2010.2047424.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
13. Elad, M. Figueiredo, MAT, и Ma, Y. (2010). «О роли разреженных и избыточных представлений в обработке изображений» (PDF) . Труды IEEE . 98 (6): 972–982. CiteSeerX 10.1.1.160.465 . doi :10.1109/JPROC.2009.2037655. S2CID  10992685. Архивировано из оригинала (PDF) 2018-01-17. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
14. Plumbley, MD Blumensath, T. Daudet, L. Gribonval, R. и Davies, ME (2010). «Разреженные представления в аудио и музыке: от кодирования до разделения источников». Труды IEEE . 98 (6): 995–1005. CiteSeerX 10.1.1.160.1607 . doi :10.1109/JPROC.2009.2030345. S2CID  4461063. {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
15. Папян, В. Романо, Ю. и Элад, М. (2017). «Сверточные нейронные сети, проанализированные с помощью свёрточного разреженного кодирования» (PDF) . Журнал исследований машинного обучения . 18 (83): 1–52. arXiv : 1607.08194 . Bibcode :2016arXiv160708194P.{{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )