# How to perform Low rank (Cholesky-like) factorization, and what is it called?

Assuming that a symmetric positive-semi-definite square real matrix $$A$$ with shape $$n*n$$ and rank $$m$$ can be decomposed as $$L L^T$$ where $$L$$ is "tall and thin" with shape $$n*m$$, ($$m). How do I find $$L$$ when I know $$m$$, and what is the name of such a decomposition?.

I am looking for a way to do this in Python, using one or more numpy/scipy functions, but I can only find the standard Cholesky decomposition.

• If $A=X^TX$, you have a way with the thin QR decomposition: math.stackexchange.com/questions/4092558/… Commented Dec 2, 2022 at 12:21
• @Jean-ClaudeArbaut thx a lot, I am just now trying to wrap my head around the explanation in the question you linked to.. But I do need $A = XX^T$ and not $A = X^TX$ Commented Dec 2, 2022 at 12:24
• Not a problem, with $Y=X^T$, $YY^T=X^TX$ Commented Dec 2, 2022 at 12:29
• @Jean-ClaudeArbaut yes obviously duh, thx for pointing that out.. I am still trying to understand how to reverse the steps in the question you linked to, to go the other way, but that question is about going from a matrix with shape $m*n$ to a matrix with shape $n*n$ with $n<m$, I think I can see how to reverse that, but is the same solution applicable when instead starting from a matrix with shape $m*m$ and finding one with shape $m*n$?. Commented Dec 2, 2022 at 12:38

Let $$A=X^TX$$, with $$X$$ of shape $$m\times n$$.

If $$m>n$$, the thin $$QR$$ decomposition of $$X$$ produces $$X=QR$$ with $$Q$$ of dimension $$m\times n$$ and $$R$$ of dimension $$n\times n$$. Then with $$L=R^T$$ we have

$$LL^T=R^TR=R^T(Q^TQ)R=(QR)^T(QR)=X^TX=A$$

If $$m\le n$$, the usual $$QR$$ decomposition of $$X$$ yields $$Q$$ of dimension $$m\times m$$ and $$R$$ of dimension $$m\times n$$, and the same relation holds.

• Thx again, now it is clear to me. I posted my own answer too at the same time as you, is my answer not also a solution? or is it flawed in some way? Commented Dec 2, 2022 at 13:08
• @Vinzent Looks good. Commented Dec 2, 2022 at 13:09
• Can you think of any advantages/disadvantages to you approach vs. mine, or vise-versa?. Perhaps one is less computation intensive than the other? Commented Dec 2, 2022 at 13:14
• @Vincent Roughly the same complexity, see cstheory.stackexchange.com/questions/2611/… (for $n\times n$ matrices). I suggest you do some tests on your matrices so see how it goes with the libraries you are using. Commented Dec 2, 2022 at 13:20
• Thx, yes that is what I am doing now :). Commented Dec 2, 2022 at 13:23

(Trying to answer my own question).

Eigen-decomposition of $$A$$:

$$A_{n*n} = Q_{n*n} \Lambda_{n*n} Q^T_{n*n}$$

Since $$A_{n*n}$$ has rank $$m$$ ($$m) it has $$n-m$$ eigen-values that are zero, so removing those eigen-values leads to:

$$A_{n*n} = \hat{Q}_{n*m} \hat{\Lambda}_{m*m} \hat{Q}^T_{n*m}$$

Splitting the eigen-values:

$$A_{n*n} = \hat{Q}_{n*m} \hat{\Lambda}^{1/2}_{m*m} \hat{\Lambda}^{1/2}_{m*m} \hat{Q}^T_{n*m}$$

And defining:

$$L = \hat{Q}_{n*m} \hat{\Lambda}^{1/2}_{m*m}$$

Results in:

$$A = L L^T$$