2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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.][1] Unfortuantely this book only explains the application of the QR decomposition on squared matrices and not the generalized case, see [this link][2]. [1]: numerical.recipes [2]: scicomp.stackexchange.com/questions/1969/… $\endgroup$ – Jan Hackenberg Aug 5 '16 at 14:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ OP writes "positive semidefinite", though. $\endgroup$ – Federico Poloni Aug 7 '16 at 13:46
  • $\begingroup$ @FedericoPoloni edited the answer to discuss the positive semidefinite case. $\endgroup$ – Brian Borchers Aug 7 '16 at 14:16

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.