Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
$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... –  J. M. Jul 23 '11 at 14:48
add comment

5 Answers 5

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$.
share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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. –  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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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