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)?

  • 1
    $\begingroup$ 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. $\endgroup$ – Algebraic Pavel May 13 '14 at 12:38
  • $\begingroup$ @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! $\endgroup$ – R B May 13 '14 at 15:04
  • 2
    $\begingroup$ 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. $\endgroup$ – Algebraic Pavel May 13 '14 at 15:30
  • $\begingroup$ 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. $\endgroup$ – Næreen Feb 15 '16 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.