计算一个非常大的矩阵的逆矩阵

Question

我正在尝试在C++中计算一个非常大的矩阵（21500x21500）的逆。到目前为止，我已经尝试了Eigen和Armadillo库，但两者都在初始化阶段失败，显示没有足够的内存。有没有办法克服这种情况？

提前致谢！

P.S 我应该更正矩阵的大小为21500x21500。正如UmNyobe所建议的那样，这不是一个方阵。实际上，它是观察矩阵X，并且我正在尝试计算（XTX）-1

我有8GB内存（64位系统），但我不认为我正在利用所有的内存空间。任务管理器显示，在发生错误时的内存使用量为1GB。也许在Windows7中有一条OS命令，当其内存使用量超过1GB时，关闭应用程序。

顺便说一句，我的最初目的是在这个观测矩阵上运行回归。

还有一件事：观测矩阵X中大多数行的每列都是零。有没有办法利用这一点，限制求逆运算中的内存使用？

- Osman Darin

---

为什么你的尺寸不相等？ - UmNyobe

该矩阵大约包含1GB或2GB的数据，具体取决于您使用的是4字节还是8字节矩阵条目。你使用的机器是32位的吗？ - Steve Townsend

Steve，我本来想发关于内存的帖子，但既然你先提到了，你应该更详细地写一下。 - UmNyobe

你是指伪逆吗？为什么要计算逆矩阵？如果是用于线性回归，我建议使用其他技术。 - Robert Cooper

您可能想了解科学计算测试站点，在那里您可能会找到更多的专家来处理这些问题。 - dmckee --- ex-moderator kitten

Answer 1

假设矩阵是正方形的，您可能正在寻找的是一个原地矩阵求逆算法。

您应该查看这个链接。

- Eitan T

Answer 2

您无法对非方阵进行求逆运算。 http://en.wikipedia.org/wiki/Invertible_matrix

- MrWuf

---

即使它是正方形的，在32位硬件上，内存仍然很重要。 - Steve Townsend

我已经更正了规格，它是一个21000x21000维度的方阵。 - Osman Darin

我认为他想要一个Moore-Penrose伪逆，你可以在非方阵上进行计算。 - Robert Cooper

Answer 3

假设有一个大小为 (11300 x 11300) 的整数矩阵（32位），您需要：

4*(11300^2)/(1024^3) = 0.4757 GB

如果您正在使用双精度，请将此数字翻倍。

如果库正在使用需要相同数量的额外内存的 Strassen 算法，则将上一个数字翻倍。

因此，使用 Strassen 或高斯方法反转此大小的基于双精度的矩阵将耗费 1.9 GB 内存。

- UmNyobe

---

因此，他需要提供他正在使用的计算机的详细信息。例如，在32位计算机上无法反转21500x21500。 - UmNyobe

感谢您的输入。根据我的机器规格，我有8GB内存（在64位系统中）。但是就我所能跟踪的内存使用情况来看，当使用的内存达到1GB时，Windows会关闭应用程序。至少，这是任务管理器显示的数量。而且这实际上发生在取逆之前。该应用程序在矩阵初始化阶段就会出现错误。 - Osman Darin

Answer 4

我希望提出另一个解决方案，它只适用于您不对矩阵的逆本身感兴趣，而是对逆与向量的乘积感兴趣。例如，假设您想找到逆矩阵和向量v的乘积，即w := (X^T X)^{-1} v。在这种情况下，您实际上正在寻找以下问题的解决方案：

Find w such that (X^T X) w = v

使用迭代算法，可以在不求逆矩阵的情况下，找到方程中给定的X和v所对应的w。我想到的一种可能是使用共轭梯度法。该算法可以用大约10行代码实现，并且仅需要能够计算给定向量y的乘积(X^T X) y。在我们的情况下，这甚至可以在两个步骤中完成，即先计算z := X y，然后再计算X^T z，这将节省空间，因为您无需存储乘积X^T X。

- Mehrwolf

Answer 5

尽管您正在一个64位机器上编译程序，但也应确保您使用了正确的64位库。否则，该程序可能会以32位编译，您仍然会遇到相同的内存问题。

至于求逆的计算，OpenCV的逆函数可能会有所帮助。请确保使用DECOMP_SVD逆，因为我发现它对于接近奇异矩阵更有效。

- Omid Sakhi