Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices

[Benoit Jacob <jacob.benoit.1@xxxxxxxxx>]

2010/2/24 Benoit Jacob <jacob.benoit.1@xxxxxxxxx>:
> 2010/2/24 Jitse Niesen <jitse@xxxxxxxxxxxxxxxxx>:
>> On Wed, 24 Feb 2010, Gael Guennebaud wrote:
>>
>>> note that the LDLT decomp does pivoting, so it is normal that you don't
>>> get the same diagonal matrix. If you reconstruct the matrix from the decomp
>>> you will see that in this case the decomp is correct.
>>
>> To further clarify, because this also threw me off for a while: I think the
>> important thing here is that the matrix A is singular.
>
> Great observation :)
>
> For a detailed analysis of the stability of LDLt with pivoting for
> singular matrices, see
> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.3360
>
> Formulas are given on page 12, suggesting that it's not very stable, AFAIU.

Sorry, let me correct that. It means that it's actually stable after
we pivot to put the biggest element on the diagonal (A_{11}). Which is
what we do.

Still, this remains:

>
> In particular, LDLt, even with pivoting, is not a rank-revealing
> decomposition, which means that the data "how many zeros in vectorD()"
> should be considered meaningless.

In other words, AFAIU, while reconstructedMatrix() is stable for
singular semidefinite input, vectorD() is not. Which is possible as,
for singular matrices, the decomposition is not unique.

Benoit


>
> Benoit
>
>> The diagonal D is
>> unique (up to reordering) for positive-definite matrices. However, there is
>> no such uniqueness for singular matrices. Simple example
>>
>> A = [ 0  0;  0  1 ]      (these are 2-by-2 matrices in Matlab notation)
>> L = [ 0  0;  sqrt(3)  1 ]
>> D = [ 1/4  0;  0  1/4 ]
>>
>> The matrix A has two LDL^T decompositions, A = A * I * A^T = L * D * L^T,
>> but the diagonal parts are not the same.
>>
>> Cheers,
>> Jitse
>>
>>
>>
>