# Rectangular Cholesky Decomposition

Assume we have a positive semidefinite matrix $A$ with $A\in\mathbb{R^{n\times n}}$. Clearly a cholesky decomposition $A=B^TB$ exist with $B\in\mathbb{R^{n\times n}}$. For my research it would be interesting to know, if we can construct a rectangular decompostion so that $A=B^TB$ with $B\in\mathbb{R^{m\times n}}$ and $n\neq m$ where $m$ is arbitrary. However, I have the feeling that such a decompostion only exists, if $m>n$. Has anybody heared of such a decomposition?

• Maybe useful: There exisists a technique called QR decomposition, which can treat more general matrices, which only have to be rectangular and not quadratic. Source : [Press et al., Numerical Recipies, 3rd edition, page 100 - 103.] Unfortuantely this book only explains the application of the QR decomposition on squared matrices and not the generalized case, see [this link]. : numerical.recipes : scicomp.stackexchange.com/questions/1969/… – Jan Hackenberg Aug 5 '16 at 14:03

If $A$ is positive definite, then $\mbox{rank}(A)=n$, and any factorization of the form $A=B^{T}B$ must involve a $B^{T}$ matrix with $m \geq n$ columns.

It's relatively easy to construct such a factorization from the Cholesky factorization of $A$ (e.g. by adding 0 columns), but what do you want to do with such a $B$?

If $A$ is merely positive semidefinite, then $\mbox{rank}(A)=r<n$, and there is no Cholesky factorization, although you can construct a factorization $A=B^{T}B$ where $B^{T}$ has $r$ columns.

One way to do this uses the eigenvalue decomposition of $A$ as follows:

First, find the eigenvalue-eigenvector decomposition of $A$,

$A=U \Lambda U^{T}$

where $U$ is $n$ by $n$ and orthogonal and $\Lambda$ is $n$ by $n$ and diagonal with nonnegative elements on the diagonal. Assume that the eigenvalues in $\Lambda$ are sorted in descending order so that the 0 eigenvalues come last.

By taking the square roots of the eigenvalues, we can write $A$ as

$A=U \sqrt{\Lambda} \sqrt{\Lambda} U^{T}$

Let

$C=\sqrt{\Lambda} U^{T}$

then

$A=C^{T}C$

Let $r$ be the number of nonzero eigenvalues in $\Lambda$. Since the remaining $n-r$ eigenvalues are 0, the last $n-r$ rows of $C$ are 0. Let $B$ consist of the first $r$ rows of $C$. Then

$A=B^{T}B$

where $B$ is of size $r$ by $n$ and $B^{T}$ is of size $n$ by $r$.

Another common way to write this is as

$A=\sum_{i=1}^{r} \lambda_{i} u_{i}u_{i}^{T}$

where $u_{i}$ is the $i$th column of $U$.

There is no factorization $A=B^{T}B$ in which $B^{T}$ has fewer than $r$ columns. There are many factors with more than $r$ columns, such as the $C^{T}$ given above.

• OP writes "positive semidefinite", though. – Federico Poloni Aug 7 '16 at 13:46
• @FedericoPoloni edited the answer to discuss the positive semidefinite case. – Brian Borchers Aug 7 '16 at 14:16
• This can also be done using the Eckart–Young–Mirsky theorem. – jvdillon Mar 3 at 18:54