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?
Best Answer
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}). $$