performance - 优化非常大的稀疏矩阵的秩计算

Question

我有一个稀疏矩阵，例如

A =

   (1,1)        1
   (3,1)        1
   (1,2)        1
   (2,2)        1
   (1,3)        1
   (3,3)        1
   (4,3)        1
   (4,4)        1

A 的完整矩阵如下所示:

full(A) =

     1     1     1     0
     0     1     0     0
     1     0     1     0
     0     0     1     1

我想快速找到矩阵 A 的秩(因为我的矩阵可以扩展到 10000 x 20000)。我尝试通过两种方式来做到这一点，但它给出了不同的结果

1. 转换为完整矩阵并使用以下方法求秩

   rank(full(A)) = 3
   

2. 使用 sprank 求排名

   sprank(A) = 4
   

真正的答案必须是 3，这意味着使用第一种方式。但是，求秩需要很长时间，尤其是大矩阵。我知道第二种方法给出 4 的原因，因为 sprank 只告诉你矩阵中有多少行/列有非零元素，而 rank 报告矩阵的实际秩，它表示有多少矩阵的行是线性独立的。 sprank(A) 为 4 但 rank(A) 仅为 3，因为您可以将第三行写为其他行的线性组合，特别是 A( 2,:) - A(1,:)。

我的问题是如何找到一个耗时最少的稀疏矩阵的秩

更新:我尝试使用某种方式。然而，它报告了更大的时间消耗

%% Create random matrix
 G = sparse(randi(2,1000,1000))-1;
 A=sparse(G) %% Because my input matrix is sparse matrix
 %% Measure performance
>> tic; rank(full(A)); toc
Elapsed time is 0.710750 seconds.
>> tic; svds(A); toc
Elapsed time is 1.130674 seconds.
>> tic; eigs(A); toc
Warning: Only 3 of the 6 requested eigenvalues converged. 
> In eigs>processEUPDinfo at 1472
  In eigs at 365
Elapsed time is 4.894653 seconds.

Answer 1

我不知道哪种算法最适合您，但我同意在 math.stackexchange.com 上提问可能更合适。当我尝试使用您提供的随机矩阵时 G = sparse(randi(2,1000,1000))-1; 我注意到它的秩<1000 的可能性很小，无论算法如何你使用，它的性能很可能非常依赖于数据。例如，在秩为 [198,325,503,1026,2000] 的 2000 个样本方阵上使用 eigs(G) 会产生以下性能(以秒为单位):[0.64,0.90,1.38, 1.57,4.00]表明eigs函数的性能与矩阵的秩密切相关。

我还搜索了现有工具并尝试了 spnrank我认为它不是那么依赖于数据(对于高排名它比 eigs 提供更好的性能，如果排名小则更差)。

最后，您可能希望根据您最有可能使用的矩阵类型来调整您的技术解决方案。