Предположим , что у меня плотную матрицу из размера, с SVD разложения
В
R
можно вычислить СВД следующим образом : svd(A)
.
Если в добавлена новая -я строка , можно ли вычислить новую декомпозицию SVD на основе старой (т. Е. Используя , и ), без пересчета СВД с нуля?A U S V
algorithms
svd
linear-algebra
matrix-decomposition
numerics
user1436187
источник
источник
rank 1 updates
. Быстрые онлайн-версии SVD для облегченных рекомендательных систем от Brand - это первая доступная статья. Я не видел что-то для SVD, уже реализованного в R, к сожалению. Обновления Cholesky существуют (updown
изMatrix
) благодаря CHOLMOD. Разреженность вашей матрицы действительно изменит ваше окончательное решение; вы предполагаете плотную или разреженную матрицу?Ответы:
Да, можно обновить декомпозицию SVD после добавления одной новой строки в существующую матрицу.
В общем, эта формулировка проблемы « добавить один к » называется обновлениями первого уровня . Ссылка MathOverflow, предоставленная @amoeba для « эффективных обновлений ранга два при разложении по собственным значениям », является отличным первым шагом, если вы хотите начать глубже изучать вопрос; Первая статья дает четкое решение вашего конкретного вопроса. Просто чтобы уточнить, что означают ранги один и два, чтобы вы не запутались, если ваш новый таков, что:A*
Где и v являются векторами, тогда вы называете это обновлением ранга 1 (или возмущением ). Основа этого обновления продиктована формулой Шермана-Моррисона. , Если возмущение более одного ранга, т.е. A ∗ = A - U V TU v
формула Вудбери входит в игру. Если вы увидите эти формулы, вы заметите, что есть много обратного. Вы не решаете это напрямую. Поскольку вы уже определили большую часть их подсистем (т. Е. Вы уже вычислили некоторую декомпозицию), вы используете их для получения более быстрых и / или более стабильных оценок. (Вот почему люди все еще исследуют эту область.) Я много использовал книгу « Вычислительная статистика » Дж.Э. Гентла; Я думаю, Чепт. 5 Числовая линейная алгебра настроит вас правильно. (Убер-классик: « Матричная алгебра с точки зрения статистика » Харвиля, к сожалению, вообще не затрагивает обновления рангов.)
Что касается статистики / приложений, обновления ранга один являются общими в рекомендательных системах, потому что каждый может иметь тысячи записей клиентов и пересчитывать SVD (или любое заданное разложение по этому вопросу) каждый раз, когда регистрируется новый пользователь или новый продукт. добавлено или удалено довольно расточительно (если не недостижимо). Обычно рекомендующие системные матрицы являются редкими, и это делает алгоритмы еще более эффективными. Первая доступная статья - рукопись М.Брэнда « Быстрые онлайновые версии SVD для облегченных рекомендательных систем ». Переходя к плотным матрицам, я думаю, что просмотр статей из «Распознавания образов» и «Обработка изображений» поможет вам понять, как использовать настоящий алгоритм. Например, документы:
кажется, что все решают одну и ту же проблему в своей сути; новые возможности приходят , и мы должны обновить наше представление соответственно быстро . Обратите внимание, что эти матрицы не являются симметричными или даже квадратными. Другая работа М. Брэнда также может решить эту проблему (см. Статью « Быстрые низкоранговые модификации тонкого разложения по сингулярным числам (2006) » - об этом также упоминается в ссылке МО, приведенной в начале поста.) много замечательных работ по этому вопросу, но большинство из них, как правило, в значительной степени математические (например, статья Бенайча-Джорджеса и Надакудити «Особые значения и векторы возмущений низкого ранга больших прямоугольных случайных матриц» (2012)") и я не думаю, что они помогут найти решение в ближайшее время. Я бы посоветовал вам сосредоточиться на литературе по обработке изображений.
К сожалению, я не встречал никаких реализаций R для процедур обновления ранга один. Ответ на « Обновляемая реализация SVD в Python, C или Fortran? » От Computational Science SE дает ряд реализаций MATLAB и C ++, которые вы можете рассмотреть. Обычно реализации R, Python и т. Д. Являются обертками вокруг реализаций C, C ++ или FORTRAN.
источник