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: 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.
A: 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.
A: 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

A: 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.
A: 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$.

A: 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.
A: 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. 
A: There is an interesting a priori argument why there is no formula that derives the SVD from LU (other than of course something trivial):


*

*Galois tells us that there is no closed formula for the zeros of polynomials of degree 5 and up



*therefore there is no closed formula for the eigenvalues of matrices (5 & up)

*since there is a closed formula for the elements of the LU factor, there is no way to transform it to anything eigenvalue related.


