高效存储大型低秩矩阵

Question

我知道在R中有一些包可以高效地存储稀疏矩阵。那么是否也有一种高效地存储低秩矩阵的方法呢？例如：

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

现在，B太大而无法存储在内存中，但它的秩很低。有没有一种有效的方式来构建和存储B，以使一些基本的读取方法（例如rowSums，colSums等）能够实时执行，并以牺牲CPU或内存为代价？

- Jeroen Ooms

---

有趣的问题-它会有什么应用？（低秩矩阵通常出现在哪里？） - David Robinson

@DavidRobinson：这些矩阵被用作大型密集矩阵的近似（太大无法计算，甚至无法存储），在一些优化算法中使用（http://en.wikipedia.org/wiki/Limited-memory_BFGS）。 - Vincent Zoonekynd

如果您想近似B，您可以使用低维度逼近，例如使用SVD并保留SVD的前n个维度。不确定这是否完全符合您的要求，但值得考虑。 - Kevin Wright

虽然它没有回答你的问题，但以下内容似乎有些相关：http://mathoverflow.net/questions/92328/low-rank-matrix-factorization - NPE

是的，我同意上面的评论。因式分解后它会变得稀疏。 - Scott

可能会有所帮助：http://www.stanford.edu/class/ee378b/papers/achlioptas-mcsherry-LRMatrixApprox.pdf - user85109

Answer 1

你的问题已经是答案了：要有效地存储这样一个低秩矩阵，你需要创建一个包含两个因子的数据结构。如果需要进行矩阵向量乘法，则可以使用因子的矩阵向量乘积从右到左进行计算。

这种策略和数据结构的一个应用可以在实现有限记忆Broyden或BFGS拟牛顿方法中找到。

- Lutz Lehmann

Answer 2

这里有另一种方法，虽然我不确定对于大矩阵来说效率如何：

如果秩很低，那么这意味着矩阵包含许多无关的行，它们是其他行的线性组合。如果矩阵表示一个线性方程组，可以设计一个算法，逐步删除这些行。

要检查一行是否无关，请检查没有该行的矩阵的秩是否仍然相同。要计算矩阵的秩，请参见this和that答案。

- flonk

---

这基本上听起来像是一种非常昂贵的因式分解方式 :-) - Jeroen Ooms

抱歉，这个想法非常糟糕，只适用于简单情况下的重复行。事实上，生成一个没有重复行或列的秩为1的矩阵是微不足道的。因此，选择随机行向量U和V，然后U'*V的秩为1。 - user85109