# Relation between Cholesky and SVD

When we have a symmetric matrix $A = LL^*$, we can obtain L using Cholesky decomposition of $A$ ($L^*$ is $L$ transposed).

Can anyone tell me how we can get this same $L$ using SVD or Eigen decomposition?

Thank you.

-
$A$ should also be positive and definite to do Cholesky decomposition –  Hsueh-Yung Lin Jun 17 '11 at 19:47
By the way, what if A is not positive definite? –  Gatsu Jun 17 '11 at 19:58
It's not terribly straightforward to obtain it. Why would you want to do that anyway? And yes, if it ain't SPD, then you've no Cholesky... –  Ｊ. Ｍ. Jul 23 '11 at 14:48

I am not sure why anyone would want to obtain a Cholesky decomposition from a SVD or an eigen-decomposition, but anyway, let's say $A$ is positive definite:

• As $A$ is positive definite, if $A=U\Sigma V^\ast$ is a SVD of $A$, we must have $U=V$ (exercise). Perform a QR decomposition for $\sqrt{\Sigma}U^\ast$, i.e. write $\sqrt{\Sigma}U^\ast=QR$ for some unitary matrix $Q$ and some upper triangular matrix $R$. Then $A=R^\ast R$ is a Cholesky decomposition of $A$.
• If $A=PDP^{-1}$ is an eigendecomposition of $A$, perform a QR decomposition or Gram-Schmidt orthogonalization for each group of columns of $P$ that correspond to the same eigenvalue. Hence we can obtain a set of orthonormal eigenvectors of $A$, i.e. we get some unitary matrix $U$ such that $A=UDU^\ast$. So we can apply the previous method to obtain a Cholesky decomposition $A=R^\ast R$.
-
I guess if you already computed it somewhere, it makes a lot of sense. –  nicolas Jul 1 '12 at 9:37
doesn't your first point stand as well if we assume A only semi positive definite ? –  nicolas Jul 1 '12 at 9:39

or you use the LU decomposition.

Anyhow, you don't normally calculate the cholesky decomposition from the eigendecomposition or svd - you use gaussian elimination. See something like Matrix Computations.

-
Ok, maybe let me ask in another way. Which other method can be used to find L in this case? I don't see very well how to manage with the LU decomposition...It means that U is equal to L*? –  Gatsu Jun 17 '11 at 20:48
In fact I was having some problem to compute correctly the Cholesky decomposition on Matlab, that's why I was seeking for another way. But now it's ok, I got it! Thanks to all –  Gatsu Jun 17 '11 at 21:08

Provided you can apply SVD (A is Positive Definite), it gives $$A = \sum \lambda_i v_i v_i^T$$ where $v_i$ is a unit eigenvector. This is because A is symmetric.

If you take $x_i = \sqrt{\lambda_i}v_i$, ($\lambda_i >0$ as A is PD). Then take $X = [x_i]$, i.e. each column of $X$ is one of the $x_i$. Then $$A = \sum x_i x_i^T = X X^T$$

(To prove that $\sum x_i x_i^T = X X^T$, use the block multiplication property, with each $x_i$ treated as a block)

In practice, it's probably faster to use Gaussian Elimination.

-

There is an interesting relationship between the eigen-decomposition of a symmetric matrix and its Cholesky factor: Say $A = L L'$ with $L$ the Cholesky factor, and $A = E D E'$ the eigen-decompostion. Then the eigen-decompostion of $L$ is $L= E D^{\frac{1}{2}} F$, with $F$ some orthogonal matrix, i.e. the Cholesky factor is a rotated form of the matrix of eigenvectors scaled by the diagonal matrix of sqaure-root eigen-values. So you can get $L$ from $E D^{\frac{1}{2}}$ through a series of orthogonal rotations aimed at making the elements above the diagonal zero.

-
Well sure, you can perform an LQ decomposition on $\mathbf E\mathbf D^\frac12$, but I don't consider it terribly interesting... –  Ｊ. Ｍ. Sep 30 '11 at 8:14
Please use TeX formatting for math. For some basic information about writing math at this site see the FAQ. –  paraxor Feb 19 '13 at 14:01
this is very interesting, can you please provide a link to a proof? –  Troy McClure Feb 22 '13 at 11:32
@TroyMcClure: as far as I remember, I found this in Harville's book on matrix algebra –  prettygully Apr 19 '13 at 5:07

If you have the SVD of a positive semi-definite matrix you can easily rewrite this to $L L^*$. However, this isn't the $L$ the cholesky composition would have computed.

\begin{align} A &= U\Sigma V^* && \textrm{SVD def.}\\ U &= V &&\textrm{since A is symmetric} \\ A &= \left(U \sqrt{\Sigma}\right) \left(U \sqrt{\Sigma}\right)^* && \textrm{note that\sqrt{\Sigma}is easily computed as it's diagonal} \\ A &= L L^* && \textrm{with...}\\ L &= U \sqrt{\Sigma} \end{align}

Though this isn't the same $L$ as cholesky computes (since it's not triangular), it does satisty $A = L L^*$ which may be enough to be useful to some.

-