计算矩阵的秩

Question

我需要计算4096x4096稀疏矩阵的秩，我使用C/C++代码。我发现一些库(如Armadillo)可以做到这一点，但它们太慢了(几乎需要5分钟)。

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

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

有人知道一个用于秩计算的快速库吗？

Answer 1

Eigen库支持稀疏矩阵，请试用一下。

Answer 2

计算代数秩是O(n^3)，其中n是矩阵的大小，因此它固有地很慢。你需要..。如果您的矩阵条件不好(对于n= 4096，典型的矩阵条件非常差)，这将是缓慢和不准确的。

现在，排名是多少？它是图像的尺寸。当n很大时，很难计算，而且输入的任何小的数值不准确都会破坏它。对于n= 4096，除非您碰巧有特别好的条件矩阵，否则这将阻止您使用旋转算法执行任何有用的操作。

最好的方法实际上是固定一个截止值，计算奇异值s_1 > ... > s_n，并将最低的整数r作为排序，使得sum(s_i^2，i> r) <ε^2* sum(s_i^2)。

因此你需要一个稀疏的SVD例程，例如。来自there。

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

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

Answer 3

尝试以下代码(文档在此处)。这是一个使用特征库计算矩阵A的秩的示例：

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