# 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 – HYL 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... – J. M. Jul 23 '11 at 14:48
If you can handle squareroots of negative numbers ($\to$ complex numbers) there's no problem with non-positive definite matrices. – Gottfried Helms Apr 25 at 7:28

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

Several people in this thread asked why you would ever want to do Cholesky on a non-positive-definite matrix. I thought I'd mention a case would motivate this question.

Cholesky decomposition is used to generate Gaussian random variants given a covariance matrix using $x_i = \sum_j L_{ij} z_j$ where each $z_j ~ Normal(0,1)$ and $L$ is the Cholesky decomposition of the covariance matrix.

A problem arises when the covariance matrix is de-generate, when the random variation described by the covariance in contained in a lower dimensional space. One or more of the Eigenvalues is zero, the matrix is not positive-definite, calls to Cholesky decomposition routines fail. When you are near this case, things also tend to be extremely sensitive to numeric round-off (i.e., the covariance is ill-conditioned).

There shouldn't be any inherent problem with generating points on this "flat" Gaussian, but the textbook algorithm based on Cholesky breaks.

Eigen decomposition can be used as an alternative for this problem, if you have a robust implementation. Some Eigen decomposition algorithms don't do well in this case either, but there are Eigen algorithms that are robust.

-

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

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... – J. M. 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. – Evan Teitelman 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

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.

-

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.

-

Cholesky $A=LL^*$:

• Pros: A little bit faster than SVD (but still O(n$^3$)), and very easy to implement
• Cons: it can only deal with definite/semi-definite cases, so it works only on square matrix. For semi-definite case, to handle the zero diagonal entry, if $L\{i,i\}=0$, then $L\{j,i\}=0$.

SVD $A=U\Sigma V*$

• Pros: it can deal with all kinds of matrix (not necessary to be square matrix).
• Cons: A little bit slower than Cholesky (but still O(mn$^2$)). it requires two steps to decompose, needs QR decomposition and thus not as easy to implement as Cholesky
-