3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ So the matrices $V$ and $VD$ aren't going to be either lower-, or upper- triangular matrices, so its not 100% clear to me what you mean. Cholesky and SVD are both two ways to take a matrix and decompose it in a way that might be useful, and will be used in different circumstances. For example, SVD is commonly used in principal component analysis while Cholesky is often used for solving numerical systems. You're right that the Cholesky decomposition has upper-triangular and lower-triangular versions, but there is only one version of SVD. Maybe a little more about what you're trying to do? $\endgroup$ – measure_theory Oct 7 '16 at 13:28
  • $\begingroup$ @measure_theory See this post: stats.stackexchange.com/questions/238938/… for exactly where the problem occurs. It seems to matter if one decomposes like $X = AA^{T}$ or $X = A^{T}A$. $\endgroup$ – baf84b4c Oct 7 '16 at 14:01
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The question is asking for the $L'L$ case and you are describing the $LL'$ case. Have a look at the two posts mentioned at the end of the question. $\endgroup$ – baf84b4c Oct 7 '16 at 14:04
  • $\begingroup$ @baf84b4c If $AA'=\Sigma$, choose $B = A'$, then $B'B=\Sigma$. That's not a meaningfully different case. $\endgroup$ – Matthew Gunn Oct 7 '16 at 14:07
  • $\begingroup$ But it does seem to matter: $Y = L'L$ and $X = LL'$ yield two different symmetric matrices $X$ and $Y$. If one wants to reverse this process and recover $L$ by a matrix square root operation, e.g. Cholesky, then it does matter which way the initial matrix was constructed, e.g. $X$ or $Y$. So I'm interested in recovering $L$ from $Y$, just that in my case I can't use Cholesky and must use SVD. I might not get the exact same $L$ as in Cholesky, but I should get something that satisfied the same constraints. Maybe it'S not possible to do via SVD because it can't distinguish the two cases? $\endgroup$ – baf84b4c Oct 7 '16 at 14:15
  • 1
    $\begingroup$ @baf84b4c There are two types of Cholesky decompositions, upper triangular and lower triangular. Either may be used. There is only ONE type of singular value decomposition. And the singular value decomposition does NOT give you the Cholesky decomposition. $\endgroup$ – Matthew Gunn Oct 7 '16 at 14:19
  • 1
    $\begingroup$ I'm just simulating the covariance matrices not estimating them. And yes, they are very sparse (block structured). All I'm doing are dot products, apart from the SVD which also only takes on the order of minutes for that size. Memory is only a concern if I want to compute the Kronecker product, which I don't. $\endgroup$ – baf84b4c Oct 7 '16 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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