c++ - 计算矩阵的秩

Question

我需要计算 4096x4096 稀疏矩阵的秩，并且我使用 C/C++ 代码。我找到了一些图书馆（如犰狳），但它们太慢了（几乎 5 分钟）。

我还尝试了两个开源版本的 Matlab（Freemat 和 Octave），但是当我尝试使用脚本进行测试时都崩溃了。

5 分钟不算多，但我必须从一百万个矩阵中获得排名，所以越快越好。

有人知道用于排名计算的快速库吗？

Answer 1

试试下面的代码（文档在这里）。这是一个用 Eigen 库计算矩阵 A 秩的例子：

MatrixXd A(2,2);
A << 1 , 0, 1, 0;
FullPivLU<MatrixXd> luA(A);
int rank = luA.rank();

Answer 2

Eigen库支持稀疏矩阵，试试吧。

Answer 3

计算代数秩是 O(n^3)，其中 n 是矩阵大小，所以它本质上很慢。你需要例如。执行旋转，如果您的矩阵条件不佳（对于 n = 4096，典型的矩阵条件非常恶劣），这将是缓慢且不准确的。

现在，排名是多少？它是图像的维度。当 n 很大时，计算起来非常困难，并且输入的任何小的数值不准确性都会破坏它。对于 n = 4096，除非您碰巧有特别好的条件矩阵，否则这将阻止您使用旋转算法做任何有用的事情。

最好的方法实际上是修复一个截止 epsilon，计算奇异值 s_1 > ... > s_n 并将最小整数 r 作为秩，使得 sum(s_i^2, i > r) < epsilon^2 * sum (s_i^2)。

因此，您需要一个稀疏的 SVD 例程，例如。从那里。

这可能不会更快，但至少它是正确的。

您可以要求加快速度所需的较少奇异值。这是一个棘手的问题，没有关于背景的信息以及您如何获得这些矩阵，我们无能为力。