3
$\begingroup$

Given a symmetric PSD matrix $A \in \mathbb R^{n \times n}$, we can Cholesky-decompose it into $LL^T$, where $L \in \mathbb R^{n \times n}$ is lower triangular. However, we can also consider decompositions of the form $A \simeq X X^T$, where $X \in \mathbb R^{n \times m}$ and $m \neq n$.

I assume that by some rank argument, this is only possible to be solved exactly of $m \geq n$. However, what if I am interested in the following optimisation problem in $X \in \mathbb R^{n \times m}$

$$\text{minimise} \quad \| A - XX^T \|_2$$

where $m \ll n$? Is this some standard problem that has been studied? Can I use some kind of solver to solve this style of problem? I'm not well versed in SDP / cone programming, can this problem be phrased in terms of those style of problems?

$\endgroup$
  • $\begingroup$ Indeed they did, thanks for making it flow better! $\endgroup$ – Siddharth Bhat Jun 1 at 15:03
  • 1
    $\begingroup$ You could use the SVD to find the closest rank $m$ approximant to $A$, and then (if you wanted) do Cholesky to that. $\endgroup$ – kimchi lover Jun 1 at 15:03
2
$\begingroup$

The Eckart-Young-Mirsky theorem tells us that the best rank $r$ approximation to a possibly non-symmetric matrix $A$ in the 2-norm (also in the Frobenius norm) is given by the first $k$ singular values and singular vectors of the SVD of $A=U\Sigma V^{T}$ as

$A=\sum_{i=1}^{k} \sigma_{i} U_{i}V_{i}^{T}$.

When $A$ is symmetric and positive semidefinite, this simplifies to

$A=\sum_{i=1}^{k} \sigma_{i}U_{i}U_{i}^{T}$

and this can be written as

$A=XX^{T}$

where

$X=\left[ \begin{array}{cccc} \sqrt{\sigma_{1}}U_{1} & \sqrt{\sigma_{2}}U_{2} & \ldots & \sqrt{\sigma_{k}}U_{k} \end{array} \right] $

There's no need for SDP to solve this problem.

$\endgroup$
  • 1
    $\begingroup$ Eckart- I've fixed the typo. $\endgroup$ – Brian Borchers Jun 2 at 6:07
  • $\begingroup$ Thank for you a reference to a rigorous theorem :) $\endgroup$ – Siddharth Bhat Jun 2 at 12:07
  • $\begingroup$ If I wanted to study more about low-rank approximations and theorems of this kind, where would I learn them from? $\endgroup$ – Siddharth Bhat Jun 2 at 12:07
  • $\begingroup$ This theorem is an old result from the 1930's. You can find it in lots of textbooks on linear algebra and matrix theory. However, it's application is somewhat limited. You're probably more interested in recent work on low-rank and non-negative matrix and tensor factorizations. $\endgroup$ – Brian Borchers Jun 2 at 15:03

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.