Decomposition of a matrix into two non-square matrices

Assume we're trying to find $A\in [-1,1]^{n\times d}, B\in [-1,1]^{m\times d}$, from an observed matrix $C\in [-d,d]^{n\times m}$, where $C=AB^T$.

The goal is to return $\widehat A, \widehat B$ such that $\widehat A \widehat B\approx C$.

If we had $n=m$, then this is a simple SVD decomposition (and deletion of the $n-d$ smallest singular values, if there's noise).

How can we address the case where the dimensions aren't the same?

Is it possble to efficiently find $\widehat A, \widehat B$ such that $\widehat A \widehat B= C$ (assuming such $A,B$ exist)?

If not, can we find $$minarg_{\widehat A, \widehat B}||C-\widehat A \widehat B||_F$$?

this seems doable by writing all $mn$ constraints and running least squares, but I'm wondering if it has a nice close form.

Are $\widehat A, \widehat B$ unique (up to rotation/scaling/permutation)?

• Why can't you use SVD in the case when $m\neq n$? it is well defined for any combination of dimensions. Just take the first $d$ singular values and set the others to zero. – Algebraic Pavel May 13 '14 at 12:38
• @PavelJiranek - I didn't write the domain correctly. The entries in A and B should be in $[-1,1]$. Do you see how to use the SVD for this task? Thanks! – R B May 13 '14 at 15:04
• Now this is something completely different, which, by the way, most likely invalidates your comment about the SVD. Also, I guess it could be much easier for you to start with minimizing the Frobenius norm instead of the spectral one. – Algebraic Pavel May 13 '14 at 15:30
• I suggest you to read this article by Joel Tropp, or this short tutorial, he explain several randomized scheme to obtain such a matrix decomposition. – Næreen Feb 15 '16 at 21:25