ベクトルが行列のランクを増やすかどうかを調べる最速の方法

Question

n> m = rank（A）であり、n行1列vが与えられていることが保証されたn行m列の行列Aが与えられると、 [A v]がAより厳密に大きいランクを持つかどうかを確認する最速の方法は？

私の用途では、Aはまばらで、nは約2^12、mは1：n-1のどこかにあります。 ランク（フル（[A v]）の比較はマシン上で約1秒かかるので、何万回も実行する必要があるので、より早く発見することができれば幸いです。

Answer 1

ランクが上がらないという解決策がある場合は、おそらくシステムA*x=vを解決しようとすることができます。

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

Answer 2

ヌルスペースの1つの計算を行う余裕がある場合は、繰り返し解決する必要はありません。 nullへの呼び出しが1回で十分です。新しいベクトルVが与えられた場合、Vとゼロ空間ベースのドット積が非ゼロであれば、Vは行列のランクを増加させます。我々はMにそれを付加した場合、ランクを上げるたとえば、私たちはもちろん、新たな列ベクトルは[; 1; 1 1 1]ウィル2.

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

のランクを持つ行列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が多すぎる場合の1つの代替方法は、本質的にゼロである特異ベクトルを見つけるためにsvdsを呼び出すことです。これらは私たちが必要とするヌルスペースの基礎を形成します。

Answer 3

スパース行列にはsprankを使用します。それをチェックすると、他のどの方法よりも速いかもしれません。

：@IanHincksが正しく指摘したように、それはランクではありません。私はここに答えを残しています。誰かが将来それを必要とする場合に備えて、私は答えを残しています。