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

给定一个n×m的矩阵A，并保证n> m = rank（A），并给出一个n×1的列v，检查[A v]的排名是否严格大于A的最快方法？检查向量是否增加矩阵秩的最快方法

对于我的应用程序，A是稀疏的，n约为2^12，m是1：n-1中的任意位置。在我的机器上比较rank（full（[A v]））需要一秒左右的时间，我需要做几万次，所以我会很高兴地发现一个更快的方法。

2012-02-01 Ian Hincks

你说你需要做10K次。从运行到运行有哪些变化？例如。是'A'总是一样的，你检查了很多向量'v'？或者每个跑步都有不同的“A”和“V”？ – 2012-02-01 15:17:22

@FlorianBrucker我从A开始的列数相对较少，然后我有一个循环运行〜20K次，每次都以某种特定的方式生成一个新的v，检查它是否线性独立于A的列空间，以及如果是，则将其附加到A. – 2012-02-01 16:32:10

最快的解决方案可能是使用空间空间作为创建新向量'v'的约束条件。 – Jonas 2012-02-01 17:27:33

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

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

2012-02-01 15:16:10 Oli

好的建议，但它似乎比调用rank（[full（A）v]）我的测试用例要多一点时间 - 大约4秒，而不是1秒。 – 2012-02-01 16:28:23

如果您可以负担得起对空间进行一次计算，则无需重复求解。只需调用一次null即可。给定一个新的向量V，如果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来查找基本为零的奇异向量。这些将构成我们需要的零空间基础。

2012-02-01 16:12:24

谢谢！这是我所尝试的，除了我的林阿格不如你的那么强。 – Jonas 2012-02-01 16:33:22

谢谢，这是反复解决的很好建议。 – 2012-02-01 16:54:30

我会使用sprank稀疏矩阵。检查一下，它可能比任何其他方法更快。

编辑：正如@IanHincks指出的那样，它不是排名。我在这里留下答案，以防将来有人需要它。

2012-02-01 16:30:04

它肯定快得多，但它不返回排名，只有排名上的界限（文档称它为结构排名）。 – 2012-02-01 16:37:40

回答