Solved – How to do SVD instead of Cholesky for $L^{T}L$

cholesky decompositionsvd

The Cholesky decomposition can be used to obtain $A$ from $X = AA^{T}$ (lower triangular version) but also $B$ from $Y = B^{T}B$ (upper triangular version). The SVD can be used to do something similar to the lower triangular Cholesky decompositionas as described here; e.g. obtaining $\mathbb{V}\mathbb{D}$ from $\mathbb{C} = \mathbb{V}\mathbb{D}^{2}\mathbb{V}'$. But how can it be adapted to something similar to the upper triangular Cholesky decomposition?

Best Answer

Theory:

Let $\mathbf{z}$ be a random vector with mean zero and $\mathrm{Var}\left(\mathbf{z} \right) = I$. Let $\Sigma$ be the desired covariance matrix.

For any matrix $A$ such that $AA' = \Sigma$

$$\mathrm{Var}\left( A\mathbf{z} \right) = A\mathrm{Var}(\mathbf{z})A' = \Sigma $$

There are numerous ways to obtain such an A. Some commonly used approaches are:

  • Cholesky decomposition
  • Singular value decomposition (useful in case of rank deficient $\Sigma$).

Obtaining $A$ such that $AA'=\Sigma$ using Lower Triangular Cholesky

If $\Sigma$ is positive definite you can compute the Cholesky decomposition.

L = chol(Sigma,'lower')

Then $LL' = \Sigma$ and we can choose $A = L$.

Obtaining $A$ such that $AA'=\Sigma$ using Upper Triangular Cholesky

R = chol(Sigma,'upper') Then $R'R = \Sigma$ and we can choose $A = R'$.

Obtaining $A$ such that $AA'=\Sigma$ using Singular Value Decomposition

[U, S, V] = svd(Sigma)

A singular value decomposition on a matrix $\Sigma$ will yield matrices $U$, $S$, $V$ Such that $USV'=\Sigma$ and $S$ is diagonal. Furthermore, if $\Sigma$ is symmetric, we have $U = V$. Choose: $$ A = U \sqrt{S}$$ Then $AA' = U\sqrt{S}\sqrt{S}U'= USU' = USV' = \Sigma$

Let $n$ be the number of random vectors we wish to generate, let $k$ be the dimension of the vector, and let randn be a function which generates an $n$ by $k$ matrix representing $n\cdot k$ iid draws of variance 1 random variables.

A = U*sqrt(S)
X = randn(n, k) * A'

And X will be an $n$ by $k$ matrix with cov(X) $\approx \Sigma$ where cov computes the sample covariance matrix taking each row as an observation.

What if I have $B$ such that $B'B=\Sigma$?

This is not a meaningfully different case. Let $A = B'$ then $AA'=\Sigma$.

Related Question