檢查向量是否增加矩陣秩的最快方法

給定一個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

回答