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

Question

给定的n-m矩阵A,它被保证N> M =秩(A),并给予一个正由-1柱V,什么是检查[A V]的秩为严格的最快方式大于A？

对于我的应用,A是稀疏的,n大约是2 ^ 12,m是1:n-1中的任何位置.比较等级(完整([A v]))在我的机器上花费大约一秒钟,我需要做数万次,所以我很乐意发现更快捷的方式.

Answer 1

如果你能负担得起零空间的一个计算,就没有必要重复求解.只需调用一次null就足够了.给定一个新的矢量V,如果与V和零空间基础的点积不为零,则V将增加矩阵的秩.例如,假设我们有矩阵M,当然其等级为2.

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

如果我们将它附加到M,新的列向量[1; 1; 1; 1]会增加等级吗？

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

是的,因为它在nullM中的至少一个基础向量上具有非零投影.

这个载体怎么样:

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

在这种情况下,两个数字基本上都是零,因此所讨论的向量不会增加M的等级.

关键是,一旦生成零空间基础,只需要简单的矩阵向量乘法.如果你的矩阵过大(和矩阵几乎满级),为空的呼叫会在这里失败,那么你将需要做更多的工作.然而,只要矩阵没有太多列,n = 4096就不会过大.

如果null太大则一种替代方法是调用svds,以找到基本上为零的奇异向量.这些将形成我们需要的零空间基础.

Answer 2

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

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