Надежный анализ главных компонент - Robust principal component analysis

Надежный анализ главных компонентов (RPCA) является модификацией широко используемой статистической процедуры Анализ главных компонентов (PCA), который хорошо работает в отношении грубо искаженные наблюдения. Для Robust PCA существует ряд различных подходов, в том числе идеализированная версия Robust PCA, которая направлена ​​на восстановление матрицы L низкого ранга0 из сильно искаженных измерений M = L0 + S0.[1] Это разложение в матрицах низкого ранга и разреженных матрицах может быть достигнуто с помощью таких методов, как метод поиска главных компонентов (PCP),[1] Стабильный PCP,[2] Квантованный PCP,[3] Блочная PCP,[4] и местный PCP.[5] Затем используются методы оптимизации, такие как Расширенный множитель Лагранжа Метод (ALM[6]), Метод переменного направления (ADM[7]), Быстрая чередующаяся минимизация (FAM[8]), Методом наименьших квадратов с итеративным взвешиванием (IRLS [9][10][11]) или чередующиеся проекции (AP[12][13]).

Алгоритмы

Невыпуклый метод

Гарантия самого современного уровня алгоритм для робастной задачи PCA (с входной матрицей ) является алгоритмом альтернативного типа минимизации.[12] В вычислительная сложность является где вход - это суперпозиция низкого ранга (ранга ) и разреженная матрица измерения и - желаемая точность восстановленного решения, т.е. где является истинным компонентом низкого ранга и - оценочная или восстановленная низкоранговая составляющая. Интуитивно этот алгоритм выполняет проекции невязки на набор матриц низкого ранга (через СВД операция) и разреженных матриц (через жесткую пороговую обработку по каждому элементу) попеременно - то есть проекция низкого ранга разности входной матрицы и разреженной матрицы, полученных на данной итерации, с последующей разреженной проекцией разности входной матрица и матрица низкого ранга, полученные на предыдущем шаге, и повторение двух шагов до тех пор, пока конвергенция.

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

Выпуклое расслабление

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

Приложения

У RPCA есть много реальных важных приложений, особенно когда исследуемые данные могут быть естественно смоделированы как низкоранговые и разреженные. Следующие примеры вдохновлены современными проблемами в Информатика, и в зависимости от приложений интересующим может быть компонент с низким рангом или разреженный компонент:

Видеонаблюдение

Учитывая последовательность видео наблюдения фреймы, часто требуется выделить действия, которые выделяются на фоне. Если мы складываем видеокадры как столбцы матрицы M, то компонент L низкого ранга0 естественно соответствует стационарному фону и разреженной компоненте S0 фиксирует движущиеся объекты на переднем плане.[1][14]

Распознавание лица

Изображения выпуклой, Ламбертовская поверхность при изменении освещенности охватывают подпространство малой размерности.[15] Это одна из причин эффективности низкоразмерных моделей для данных изображений. В частности, изображения человеческого лица легко аппроксимировать подпространством низкой размерности. Правильное получение этого подпространства имеет решающее значение во многих приложениях, таких как распознавание лица и выравнивание. Оказывается, RPCA можно успешно применить к этой проблеме, чтобы точно восстановить лицо.[1]

Обзоры

  • Надежный PCA [14]
  • Динамический RPCA [16]
  • Разложение на низкоранговые плюс аддитивные матрицы [17]
  • Младшие модели[18]

Книги, журналы и семинары

Книги

  • Т. Боуманс, Н. Айбат, Э. Захза. Справочник по устойчивой низкоранговой и разреженной матричной декомпозиции: приложения в обработке изображений и видео, CRC Press, Taylor and Francis Group, май 2016 г. (дополнительная информация: http://www.crcpress.com/product/isbn/9781498724623 )
  • З. Линь, Х. Чжан, "Модели низкого ранга в визуальном анализе: теории, алгоритмы и приложения", Academic Press, Elsevier, июнь 2017 г. (дополнительная информация: https://www.elsevier.com/books/low-rank-models-in-visual-analysis/lin/978-0-12-812731-5 )

Журналы

Мастерские

  • RSL-CV 2015: Семинар по устойчивому обучению подпространству и компьютерному зрению в связи с ICCV 2015 (для получения дополнительной информации: http://rsl-cv2015.univ-lr.fr/workshop/ )
  • RSL-CV 2017: Семинар по устойчивому обучению подпространству и компьютерному зрению в связи с ICCV 2017 (для получения дополнительной информации: http://rsl-cv.univ-lr.fr/2017/ )

Сессии

  • Специальная сессия на тему «Онлайн-алгоритмы для статического и динамического надежного PCA и измерения сжатия» в связи с SSP 2018. (Дополнительная информация: https://ssp2018.org/ )

Ресурсы и библиотеки

Сайты

Библиотеки

В Библиотека LRS (разработан Эндрюс Собрал ) предоставляет набор алгоритмов низкоранговой и разреженной декомпозиции в MATLAB. Библиотека была разработана для обнаружения движущихся объектов в видео, но ее также можно использовать для других задач компьютерного зрения / машинного обучения. В настоящее время LRSLibrary предлагает более 100 алгоритмов, основанных на матрица и тензор методы.

использованная литература

  1. ^ а б c d Эммануэль Дж. Кандес; Сяодун Ли; Йи Ма; Джон Райт (2009). «Надежный анализ главных компонентов?». Журнал ACM. 58 (3): 1–37. Дои:10.1145/1970392.1970395.
  2. ^ Дж. Райт; Ю. Пэн; Y. Ma; А. Ганеш; С. Рао (2009). «Робастный анализ главных компонент: точное восстановление поврежденных матриц низкого ранга с помощью выпуклой оптимизации». Системы обработки нейронной информации, НИПС 2009.
  3. ^ С. Беккер; Э. Кандес, М. Грант (2011). «TFOCS: Гибкие методы первого порядка для минимизации ранга». Симпозиум по оптимизации матриц низкого ранга, Конференция SIAM по оптимизации.
  4. ^ Г. Тан; А. Нехорай (2011). «Надежный анализ главных компонент на основе низкоранговой и блочно-разреженной матричной декомпозиции». Ежегодная конференция по информационным наукам и системам, СНПЧ 2011: 1–5. Дои:10.1109 / СНПЧ.2011.5766144. ISBN  978-1-4244-9846-8.
  5. ^ Б. Вольберг; Р. Чартран; Дж. Тейлер (2012). «Поиск локальных главных компонентов для нелинейных наборов данных». Международная конференция по акустике, речи и обработке сигналов, ICASSP 2012: 3925–3928. Дои:10.1109 / ICASSP.2012.6288776. ISBN  978-1-4673-0046-9.
  6. ^ З. Линь; М. Чен; Л. Ву; Ю. Ма (2013). «Метод расширенных множителей Лагранжа для точного восстановления поврежденных матриц низкого ранга». Журнал структурной биологии. 181 (2): 116–27. arXiv:1009.5055. Дои:10.1016 / j.jsb.2012.10.010. ЧВК  3565063. PMID  23110852.
  7. ^ X. Юань; Дж. Ян (2009). "Разложение матриц разреженного и низкого ранга методами чередования направлений". Оптимизация онлайн.
  8. ^ П. Родригес; Б. Вольберг (2013). «Быстрое преследование главного компонента посредством попеременной минимизации». Международная конференция IEEE по обработке изображений, ICIP 2013: 69–73. Дои:10.1109 / ICIP.2013.6738015. ISBN  978-1-4799-2341-0.
  9. ^ К. Гийон; Т. Боуманс; Э. Захза (2012). «Обнаружение переднего плана с помощью надежной разложения матрицы низкого ранга, включая пространственно-временные ограничения». Международный семинар по проблемам базовой модели, ACCV 2012.
  10. ^ К. Гийон; Т. Боуманс; Э. Захза (2012). «Обнаружение переднего плана с помощью надежной матричной факторизации низкого ранга, включая пространственные ограничения с итеративной регрессией с повторным взвешиванием». Международная конференция по распознаванию образов, ICPR 2012.
  11. ^ К. Гийон; Т. Боуманс; Э. Захза (2012). «Обнаружение движущихся объектов с помощью надежной матричной декомпозиции низкого ранга по схеме IRLS». Международный симпозиум по визуальным вычислениям, ISVC 2012.
  12. ^ а б П., Нетрапалли; У., Ниранджан; С., Сангхави; А., Анандкумар; П., Джайн (2014). «Невыпуклый прочный PCA». Достижения в системах обработки нейронной информации. 1410: 1107–1115. arXiv:1410.7660. Bibcode:2014arXiv1410.7660N.
  13. ^ а б C., HanQin; К., Цзянь-Фэн; W., Ke (2019). «Ускоренные альтернативные прогнозы для надежного анализа главных компонентов». Журнал исследований в области машинного обучения. 20 (1): 685--717. arXiv:1711.05519. Bibcode:2017arXiv171105519C.
  14. ^ а б Т. Боуманс; Э. Захза (2014). «Надежный PCA через поиск основных компонентов: обзор для сравнительной оценки в области видеонаблюдения». Компьютерное зрение и понимание изображений. 122: 22–34. Дои:10.1016 / j.cviu.2013.11.009.
  15. ^ Р. Басри; Д. Джейкобс. «Ламбертовское отражение и линейные подпространства». Цитировать журнал требует | журнал = (Помогите)
  16. ^ Н. Васвани; Т. Боуманс; С. Джавед; П. Нараянамурти (2017). «Надежный PCA и надежное отслеживание подпространства». Препринт. 35 (4): 32–55. arXiv:1711.09492. Bibcode:2017arXiv171109492V. Дои:10.1109 / MSP.2018.2826566.
  17. ^ Т. Боуманс; А. Собрал; С. Джавед; С. Юнг; Э. Захзаг (2015). «Разложение на низкоранговые и аддитивные матрицы для разделения фона / переднего плана: обзор для сравнительной оценки с крупномасштабным набором данных». Обзор компьютерных наук. 23: 1–71. arXiv:1511.01245. Bibcode:2015arXiv151101245B. Дои:10.1016 / j.cosrev.2016.11.001.
  18. ^ З. Линь (2016). «Обзор моделей низкого ранга в анализе данных». Большие данные и информационная аналитика. 1 (2): 139–161. Дои:10.3934 / bdia.2016001.

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