Хранение большой, но низкоуровневой матрицы эффективно

Я знаю, что в R есть пакеты для эффективного хранения разреженных матриц. Есть ли способ эффективно хранить матрицу низкого ранга? Например:Хранение большой, но низкоуровневой матрицы эффективно

A <- matrix(rnorm(1e6), nrow=1e5, ncol=1e1) 
B <- A %*% t(A)

Теперь B слишком велик, чтобы сохранить в памяти, но это низкий по рангу. Есть ли способ построить и сохранить B эффективным способом, так что некоторые основные методы чтения (rowSums, colSums и т. Д.) Выполняются «на лету», чтобы торговать за процессор или память?

источник

2013-03-14 Jeroen

Интересный вопрос: какие приложения у него были бы? (Где вообще выглядят матрицы низкого ранга?) –

@DavidRobinson: Эти матрицы используются, например, в качестве приближений больших плотных матриц (слишком больших для вычисления или даже для хранения) в некоторых [алгоритмах оптимизации] (http://en.wikipedia.org/wiki/Limited-memory_BFGS). –

Если вы хотите приблизиться к B, вы можете использовать низкоразмерное приближение, например. использовать SVD и сохранить первые n измерений SVD? Не уверен, что это совсем то, чего вы хотите, но, возможно, стоит рассмотреть. –

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

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

Чтобы проверить, не имеет ли значение строка, проверьте, не является ли ранг матрицы без этой строки. Для вычисления ранга матрицы см. this и that ответ.

источник

2013-03-28 10:10:30 flonk

Это в основном звучит как очень дорогой способ факторинга :-) – Jeroen

Простите, но ужасно плохая идея, которая работает только для простого случая, с реплицированными рядами. На самом деле TRIVIAL создает матрицу ранга 1, которая не имеет реплицированных строк или столбцов. Таким образом, выбираем случайные линейные векторы U и V, тогда U '* V имеет ранг 1. – 2013-09-06 14:23:44

Ваш вопрос уже является ответом: чтобы эффективно хранить такую матрицу низкого ранга, вы создаете структуру данных, содержащую оба фактора. Если требуется умножение матричных векторов, это можно сделать справа налево с использованием матрично-векторных произведений факторов.

Одно из применений этой стратегии и структуры данных можно найти в реализациях методов квази-Ньютона с ограниченной памятью Broyden или BFGS.

источник

2014-02-13 14:29:41 LutzL

Хранение большой, но низкоуровневой матрицы эффективно

ответ

Смежные вопросы