4
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ If $A=X^TX$, you have a way with the thin QR decomposition: math.stackexchange.com/questions/4092558/… $\endgroup$ Commented Dec 2, 2022 at 12:21
  • $\begingroup$ @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$ $\endgroup$ Commented Dec 2, 2022 at 12:24
  • 1
    $\begingroup$ Not a problem, with $Y=X^T$, $YY^T=X^TX$ $\endgroup$ Commented Dec 2, 2022 at 12:29
  • $\begingroup$ @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$?. $\endgroup$ Commented Dec 2, 2022 at 12:38

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$ Commented Dec 2, 2022 at 13:08
  • 1
    $\begingroup$ @Vinzent Looks good. $\endgroup$ Commented Dec 2, 2022 at 13:09
  • $\begingroup$ Can you think of any advantages/disadvantages to you approach vs. mine, or vise-versa?. Perhaps one is less computation intensive than the other? $\endgroup$ Commented Dec 2, 2022 at 13:14
  • $\begingroup$ @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. $\endgroup$ Commented Dec 2, 2022 at 13:20
  • $\begingroup$ Thx, yes that is what I am doing now :). $\endgroup$ Commented Dec 2, 2022 at 13:23
2
$\begingroup$

(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<n$) 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$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .