Основные статьи о матричных разложениях

18

Недавно я прочитал книгу Скилликорна о разложении матриц, и был немного разочарован, поскольку она была нацелена на студенческую аудиторию. Я хотел бы составить (для себя и других) краткую библиографию основных работ (обзоров, но также прорывных работ) по разложению матриц. Я имею в виду, прежде всего, что-то о SVD / PCA (и надежных / разреженных вариантах) и NNMF, поскольку они, безусловно, наиболее часто используются. У всех вас есть какие-либо рекомендации / предложения? Я сдерживаю свой, чтобы не смещать ответы. Я бы попросил ограничить каждый ответ 2-3 работами.

PS: я называю эти два разложения наиболее используемыми при анализе данных . Конечно, QR, Cholesky, LU и Polar очень важны в численном анализе. Это не главное в моем вопросе.

matrix-decomposition svd numerics gappy
источник

Ответы:

16

Откуда вы знаете, что SVD и NMF являются наиболее часто используемыми матричными разложениями, а не LU, Cholesky и QR? Моим личным любимым «прорывом» должен был быть гарантированный QR-алгоритм, позволяющий выявить ранг,

  • Чан, Тони Ф. "Ранг выявления QR-факторизаций". Линейная алгебра и ее приложения Тома 88-89, апрель 1987, страницы 67-82. DOI: 10.1016 / 0024-3795 (87) 90103-0

... развитие более ранней идеи QR с поворотом столбцов:

  • Бусингер, Питер; Голуб, Джин Х. (1965). Линейные решения наименьших квадратов преобразованиями Домхолдера. Numerische Mathematik, том 7, номер 3, 269-276, DOI: 10.1007 / BF01436084

A ( ?) Классический учебник:

  • Голуб, Джин Н .; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.), Джонс Хопкинс, ISBN 978-0-8018-5414-9 .

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

Редактировать: немного больше поисковик находит документ, резюме которого предполагает, что мы могли бы быть немного в перекрестных морских свиньях. Мой вышеупомянутый текст исходил из «числовой линейной алгебры» (NLA); возможно, вас больше волнует «прикладная статистика / психометрия» (AS / P)? Не могли бы вы уточнить?

оборота
источник
2
Я бы сказал «учебник» сам, с Матричными Алгоритмами Стюарта ( обе части ). Я бы сам дал список пионерских работ, но ОП действительно должен объяснить, хочет ли он точки зрения чисел или статистики (я могу помочь с первым, но не так сильно с последним).
JM не является статистиком
1
+1 для Голуба и Ван Лоанна. И, да, окончательная статья уместна.
Шаббычеф
2
Я отредактировал свой вопрос, чтобы уточнить, что я сосредоточен на статистической части. Я согласен со всеми, что Голуб и Ван Лоан являются стандартным справочником для матричных разложений. Но это опускает тему очень крупномасштабной декомпозиции через случайные проекции. Обзорная статья, которую я бы включил в свой список: «Поиск структуры со случайностью: стохастические алгоритмы для построения приближенных матричных разложений», автор Halko et al.
gappy
4

Для NNMF Ли и Сын описывают итерационный алгоритм, который очень прост в реализации. На самом деле они дают два одинаковых алгоритма, один для минимизации невязки Фробениуса, другой для минимизации расхождения Кульбака-Лейблера в аппроксимации и исходной матрице.

shabbychef
источник
3

Может быть, вы можете найти интересное

  1. [Обучение с матричной факторизацией] Кандидатская диссертация Натана Сребро,
  2. Исследование различных методов матричной факторизации для больших рекомендательных систем , Габор Такач и др. и почти такая же техника, описанная здесь

Последние две ссылки показывают, как разрозненные матричные факторизации используются в совместной фильтрации. Тем не менее, я считаю, что SGD-подобные алгоритмы факторизации могут быть полезны где-то еще (по крайней мере, их чрезвычайно легко кодировать)

Бижей
источник
2

Виттен, Тибширани - Пенализованная матричная декомпозиция

http://www.biostat.washington.edu/~dwitten/Papers/pmd.pdf

http://cran.r-project.org/web/packages/PMA/index.html

Мартинссон, Рохлин, Шлам, Тигерт - Рандомизированное СВД

http://cims.nyu.edu/~tygert/software.html

http://cims.nyu.edu/~tygert/blanczos.pdf

оборота пслис
источник
5
Благодарю. Я знаю обе бумаги. Я не большой поклонник Виттена [не Виттена] и др., Так как я думаю, что есть более важные статьи о редких разложениях. Что касается рандомизированного SVD, мне особенно нравится обзорная статья «Поиск структуры со случайностью: стохастические алгоритмы построения приближенных матричных разложений» ( arxiv.org/abs/0909.4061 ), также соавтором которой является Мартинссон.
gappy
Я согласен. я просто выкладывал там 2 газеты, которые никто не упомянул.
pslice
2

В этом году на NIPS была краткая статья о распределенном очень крупномасштабном SVD, который работает за один проход по матрице потокового ввода .

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

писк
источник
Что такое NIPS?
остановка
Добавлена ​​ссылка @onestop. NIPS = Нейронные системы обработки информации. Это сообщество (а не система :)). Но Писк говорит о конференции NIPS 2010.
Робин Жирар