Как вычислить SVD огромной разреженной матрицы?

26

Каков наилучший способ вычисления разложения по сингулярным числам (SVD) очень большой положительной матрицы (65M x 3,4M), где данные чрезвычайно редки?

Менее 0,1% матрицы не равно нулю. Мне нужен способ, который:

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

Было бы здорово иметь библиотеку Haskell, Python, C # и т. Д., Которая реализует это. Я не использую mathlab или R, но при необходимости я могу пойти с R.

Соня
источник
3
Сколько у тебя памяти? 0,1% от 65M * 3,4M по-прежнему 221e9 ненулевые значения. Если вы используете 4 байта на значение, это все равно больше 55 ГБ, при условии отсутствия затрат, так что разреженность по-прежнему не решает проблему ... Вам нужно загрузить весь набор в память сразу?
Побит
Я должен был быть более точным. Не более 250-500 МБ с 32-разрядным целым числом. Возможно намного меньше, но размерность - проблема, насколько я понимаю. У меня есть машина на 16 ГБ.
Соня
Как насчет этого? quora.com/…
побитовый
Эта веб-страница содержит ссылку на библиотеку Python, в которой реализован «быстрый, инкрементный алгоритм SVD с большой матрицей с малой памятью»: en.wikipedia.org/wiki/Latent_semantic_analysis
побитовый
Смотрите также stats.stackexchange.com/questions/2806 .
говорит амеба, восстанови Монику

Ответы:

21

Если он помещается в память, создайте разреженную матрицу в R, используя пакет Matrix , и попробуйте irlba для SVD. Вы можете указать, сколько сингулярных векторов вы хотите получить в результате, что является еще одним способом ограничения вычислений.

Это довольно большая матрица, но у меня были очень хорошие результаты с этим методом в прошлом. irlbaдовольно современное. Он использует неявно перезапущенный алгоритм би-диагонализации Ланцоша .

Он может прожевать набор призовых данных netflix (480 189 строк по 17 770 столбцам, 100 480 807 ненулевых записей) за миллисекунды. Ваш набор данных в ~ 200 000 раз больше, чем набор данных Netflix, поэтому это займет значительно больше времени. Было бы разумно ожидать, что он может выполнить вычисления в течение нескольких дней.

Zach
источник
матрица данных помещается в память, будет ли irlba эффективно справляться с разложением памяти?
Соня
@Sonia: irlba очень эффективно использует память: она вычисляет приблизительное решение, вы можете ограничить число сингулярных векторов и была разработана для работы с разреженными матрицами. Насколько я знаю, это так же быстро, как вы собираетесь получить для вычисления частичных SVD.
Зак
@ Соня: Удачи!
Зак
Дайте ему попытку из памяти ... Я вычислю форму треугольного блока перед запуском.
Соня
@ Соня, у тебя оно хранится как разреженное Matrix? Попробуйте ограничить число значений, которые вы вычисляете ... может быть, просто посмотрите на топ-10?
Зак