Rectangular Cholesky Decomposition

Question

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?

Answer 1

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.