检查矩阵是否防雷

Question

检查矩阵在Matlab中是否对称正定的最快(运行时间)方法是什么?我对大量大小(维度)从10000到100000不等的稀疏矩阵运行了这个测试。

编辑:

Cholesky对我来说太贵了。我首先需要一个脏检查如果它给出了一个矩阵可能是spd的指示那么我可能只检查那些矩阵更可靠地使用CHOL

Answer 1

如前所述，您可以使用chol函数来检查矩阵是否为PD。

CHOL函数提供了一个可选的第二个输出参数"p"如果矩阵是正定的，它等于零。的胆固醇函数将返回一个错误，如果它只提供了一个输出参数，并给出一个非正矩阵明确的。注意:CHOL期望它的输入矩阵是对称且唯一的看矩阵的上三角部分。

对于对称性，可以使用以下函数:

issym = @(m) isequal(tril(x), triu(x)');

Answer 2

我认为这是一个非常重要的问题。如果矩阵不是正定的，Cholesky算法就会失败，所以最好是自己实现，这样做的好处是当算法因为输入不是正定而失败时，人们可以控制该怎么做。我使用c#而不是Matlab来进行数学编程，我的Cholesky实现只有几行，所以并不困难。如果你使用别人的算法，那么取决于它是如何实现的，如果你输入一个非对称矩阵，你可能会得到误导的结果，因为一些实现假设矩阵是对称的。我能想到的唯一快速预测试是检查矩阵跟踪，如果矩阵是SPD，这将是正的。

Answer 3

我想你可以看看你的矩阵的特征值，看看它们是否都是不同的实值。

因此，您可以考虑这样调用eig函数:

[V,D] = eig(A)

希望对大家有所帮助

Answer 4

对于上述跟踪测试:假设矩阵A为

A =
    1.0000    1.6000
    1.6000    1.0000

然后

trace(A) is 2 

但是A的特征值是eig(A)

ans =
   -0.6000
    2.6000

因此特征值并不都是正的。因此这个矩阵还不是SPD，它的迹线> 0。基于这个反例，我怀疑痕量测试不是决定性的。

Answer 5

您可以通过使用用于估计特征值的Gershgorin定理从考虑中消除一些矩阵来缩小域。

结果是，如果你对每一行元素的绝对值求和(对角线上的元素除外)，k，你得到一个半径，r_k。对应的特征值必须位于对角线上的值a_kk的半径内。所以，如果a_kk> r_k对于所有k，你的矩阵是PD。如果a_kk <= r_k对于某些k，您的矩阵可能仍然是PD，因为这意味着一个或多个Gershgorin磁盘跨越虚轴(或零)，而实际特征值可能在任意一侧。

假设issymmetric(A)成功，如:

r = sum(abs(A),2)-diag(A);
if length(find(r>diag(A))) == 0,
    % No circles cross the origin: A is PD
else
    % A might still be PD: do some other test
end

对矩阵M=sprandsym(n,n,d)+c*speye(n,n)进行快速肮脏测试，其中一些是PD，其中一些不是(玩弄n, d和c)，似乎表明它识别了许多，但不是全部SPD矩阵(如预期的那样)，但与eig()(及其底层Cholesky)相比，非常便宜对于"大"n。对于特定的矩阵，它可能有效，也可能无效。嗯，我想。

显然，我还没有算出所有的细节，但我相信你已经明白了。