最快的方法检查向量是否增加矩阵秩

Question

给定一个$n\times m$的矩阵A，保证 $n>m=rank(A)$，以及一个$n\times 1$的列向量$v$，如何快速检查$[A\ v]$的秩是否大于$A$的秩？

对于我的应用程序，$A$是稀疏的，$n$约为$2^{12}$，$m$在$1:n-1$之间。在我的机器上比较$rank(full([A\ v]))$需要大约一秒钟的时间，并且我需要进行成千上万次的运算，因此我希望发现更快的方法。

- Ian Hincks

---

你说你需要做这个10k次。每次运行有什么变化？例如，A是否总是相同的，而你检查多个向量v？还是每次运行A和v都不同？ - Florian Brucker

@FlorianBrucker 我开始时有一个相对较少列的A，然后我有一个循环运行了约20K次，每次以某种特定方式生成一个新v，并检查它是否与A的列空间线性独立，如果是，则将其附加到A中。 - Ian Hincks

最快的解决方案可能是使用零空间作为创建新向量v的约束条件。 - Jonas

@Jonas - 是的，如果目标是选择完全位于零空间中的新向量，则逻辑解决方案是仅选择由零空间基向量的线性组合构成的向量。 - user85109

Answer 1

如果你有能力做一次零空间的计算，那就不需要重复解。只需要一次null的调用即可。给定一个新向量V，如果它和零空间基的点积非零，那么V会增加矩阵的秩。例如，假设我们有一个矩阵M，它的秩当然是2。

M = [1 1;2 2;3 1;4 2];
nullM = null(M')';

如果我们将一个新的列向量[1;1;1;1]附加到矩阵M上，它是否会增加矩阵的秩？

nullM*[1;1;1;1]
ans =
       -0.0321573705742971
        -0.602164651199413

是的，因为它在nullM的至少一个基向量上具有非零投影。

那这个向量呢：

nullM*[0;0;1;1]
ans =
      1.11022302462516e-16
      2.22044604925031e-16

在这种情况下，两个数字基本上都是零，因此所讨论的向量不会增加M的排名。

关键是，一旦生成了零空间基础，只需要进行简单的矩阵向量乘法即可。如果您的矩阵太大（且矩阵几乎具有完整的秩），则null调用将在此处失败，那么您将需要做更多的工作。但是，只要矩阵的列数不太多，n = 4096并不算过大。

如果null太多，则另一种选择是调用svds，以查找基本上为零的奇异向量。这些将形成我们所需的零空间基础。

- user85109

---

谢谢！那就是我尝试过的，只不过我的线性代数功夫没有你强。 - Jonas

Answer 2

我会使用sprank来处理稀疏矩阵。你可以查看这个方法，它可能比其他任何方法都更快。

编辑：正如@IanHincks正确指出的那样，这不是排名。我仍然保留这个答案，以防将来有人需要。

- Andrey Rubshtein

---

它肯定更快，但它不返回排名，只返回排名的上限（文档称其为结构排名）。 - Ian Hincks

Answer 3

也许你可以尝试解决系统A * x = v，如果它有一个解，这意味着秩不会增加。

x=(B\A)';
norm(A*x-B) %% if this is small then the rank does not increase

- Oli

---

好的建议，但是根据我的测试情况，这似乎比调用rank([full(A) v])更耗时——大约需要4秒而不是1秒。 - Ian Hincks