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

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices*From*: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>*Date*: Wed, 24 Feb 2010 06:39:21 -0500*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:in-reply-to:references :date:message-id:subject:from:to:content-type :content-transfer-encoding; bh=MSVMWprxe00PMS7GNRVaxKXTizGWGf6XH3RWoD7abxk=; b=QTik5ZR+CMO9QTDAp28LizClxhWmo0G0knlVbUsdSe9e5R/sL83T2kkPi80YbvSPM5 txRR91D5ybCAHbvNUeyUcM3jE8HIJGJ0tHld90tvk6tDZv6RQfvNE/Pz8BWT47+A0Qwc nbcp0BbK5/y0+vpqaDPj0/6AgfWha3kfnRAzw=*Domainkey-signature*: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type:content-transfer-encoding; b=SnYuq/b+2mcRBg6KddjqeP3P982ScaROgIqREtsGFgHmrEisQu7Koih5P9LinGUj8/ Yv2nSSClP0qTVXEZUg6AmyUCNWuwSQsVZUFpZCVaPYs9lYrF5XalodnMCPPyp99XR3x+ JzcV/owC0+gZgkJLQ8Qn6qkFRi/kFjb84lhAs=

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 >> >> >> >

**References**:**[eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Ben Goodrich

**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Benoit Jacob

**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Ben Goodrich

**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Benoit Jacob

**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Ben Goodrich

**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Gael Guennebaud

**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Jitse Niesen

**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices***From:*Benoit Jacob

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices** - Next by Date:
**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices** - Previous by thread:
**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices** - Next by thread:
**Re: [eigen] [patch] LDLt decomposition with rank-deficient matrices**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |