2
$\begingroup$

Suppose I have an LDL decomposition of a symmetric semipositive definite matrix $A$:

$$A = L D L^T$$

where $D$ is diagonal with $D_{ii} \ge 0$ and $L$ is lower triangular with 1s along the diagonal. eg:

$$A = \begin{pmatrix}1&&&\\7&1&&\\3&21&1&\\3&1&2&1\end{pmatrix} \begin{pmatrix}7&&&\\&2&\\&&3&\\&&&0\end{pmatrix} \begin{pmatrix}1&7&3&3\\&1&21&1\\&&1&2\\&&&1\end{pmatrix}$$

If $D_{ii} > 0, \forall{i}$, then the factorization is unique and it has an inverse, which is also its Moore-Penrose psuedoinverse. The inverse is:

$$A^{-1} = L^{-T} D^{-1} L^{-1}$$

However if at least some of $D_{ii} = 0$, then the decomposition is not unique (some columns in $L$ are undetermined). I'd like to be able to represent the pseudoinverse of $A$ as $L^{-T} D^{+} L^{-1}$, where $D^+_{ii} = 1/D_{ii}$ if $D_{ii} > 0$ and $0$ otherwise.

Is there a way to account for the pseudoinverse in such a way that I can use the LDL decomposition to get it? Presumably this would also make the decomposition unique?

$\endgroup$
1
$\begingroup$

The $LDL^T$ decomposition of an SPSD matrix cannot be unique. If $$ A=LDL^T $$ with $$\tag{1} D=\begin{bmatrix}D_{11}&0\\0&0\end{bmatrix}, \quad L=\begin{bmatrix}L_{11}&0\\L_{21}&L_{22}\end{bmatrix}, $$ where $D_{11}$ is nonsingular (with positive diagonal entries), then it is easy to see that the sub-matrix $L_{22}$ can be in fact chosen arbitrarily. Generally, you would need to consider a pivoted factorisation leading to $$\tag{2} \Pi^TA\Pi=LDL^T $$ with $L$ and $D$ of the form (1) and some permutation matrix $\Pi$, because accepting a zero pivot would make the remainder of the factorisation algorithm undefined.

Assume that you have a factorisation (1) obtained (by luck) without pivoting (or consider $\Pi^TA\Pi$ instead of $A$) and define $A^+=L^{-T}D^+L^{-1}$. It is easy to verify that $$ A^+=\begin{bmatrix}L_{11}^{-T}D_{11}^{-1}L_{11}^{-1}&0\\0&0\end{bmatrix}, $$ so $A^+$ is unique as it does not depend on the "non-unique block" $L_{22}$. So in fact $$ A^{+}=\begin{bmatrix}A_{11}^{-1}&0\\0&0\end{bmatrix}, $$ where $A_{11}$ is the leading principal sub-matrix of $A$ (of the dimension equal to the rank of $A$ consistent with the partitioning of the factors in (1)).

You might want to note that $A^{+}$ defined this way is not the Moore-Penrose pseudo inverse, since it generally $AA^{+}$ and $A^+A$ are not symmetric. On the other hand, the matrix $A^{+}$ as you defined it would form a so-called generalised reflexive inverse, or a (1,2)-generalised inverse (since it satisfies the first two of the four conditions defining the unique Moore-Pseudo inverse).

If you insists to compute the Moore-Penrose pseudo-inverse from the $LDL^T$ factorisation, consider (as before with luck or pivoting) that you have (1) and write $A$ as $$ A=\tilde{L}D_{11}\tilde{L}^{T}, $$ where $\tilde{L}^T=[L_{11}^T,L_{21}^T]$. Since $D_{11}$ and $\tilde{L}$ have full rank we can write $$ A^{\dagger}=(\tilde{L}D_{11}\tilde{L}^T)^{\dagger}=(\tilde{L}^{\dagger})^TD_{11}^{-1}\tilde{L}^{\dagger}, $$ where $$ \tilde{L}^{\dagger}=(\tilde{L}^T\tilde{L})^{-1}\tilde{L}^T =(L_{11}^TL_{11}+L_{21}^TL_{21})^{-1}[L_{11}^T,L_{21}^T]. $$ Hence we obtain quite an awful expression $$ A^{\dagger}=\tilde{L}\tilde{D}_{11}^{-1}\tilde{L}^{T}, \quad \tilde{D}_{11}=\tilde{L}^T\tilde{L}D_{11}\tilde{L}^T\tilde{L}=(L_{11}^TL_{11}+L_{21}^TL_{21})D_{11}(L_{11}^TL_{11}+L_{21}^TL_{21}). $$

$\endgroup$
  • $\begingroup$ Thanks that makes a lot of sense :) $\endgroup$ – Jay Lemmon May 2 '14 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.