6
$\begingroup$

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 $.

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 $$\text{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.

Assuming such $A,B$ exist, are $\widehat A, \widehat B$ unique (up to rotation/scaling/permutation)?

$\endgroup$
4
  • 1
    $\begingroup$ This problem is hard to solve (it is a difficult nonconvex problem); no closed form solution, and no guaranteed approximation either. $\endgroup$
    – Suvrit
    May 14, 2014 at 15:49
  • $\begingroup$ Why the downvote? It seems a perfectly reasonable question to me. $\endgroup$ May 15, 2014 at 12:53
  • $\begingroup$ btw, I did not downvote this question, it is perfectly reasonable, though not research level $\endgroup$
    – Suvrit
    May 15, 2014 at 15:12
  • 2
    $\begingroup$ There is no standard off-the-shelf method to efficiently solve this problem, therefore it is research level. $\endgroup$ Oct 8, 2015 at 1:10

1 Answer 1

2
$\begingroup$

We are considering the case of free minimum (not reached on the boundary). Assume that $d\leq \inf (m,n)$ ; then $rank(AB^T)\leq d$. Conversely, if $D$ is a $n,m$ matrix of rank $d$, then I think (I have no time to see that) that $D$ may be written in the form $AB^T$. Then your problem is to approximate $C$ with a matrix of rank $d$. You can do that, using the singular values of $C$ and the Eckart–Young theorem.

Let $A=[a_{i,j}],B=[b_{k,l}]$. If you consider the boundary, then (unfortunately for you) you must assume that some $a_{i,j}$ and $b_{k,l}$ are $\pm 1$ and write the Lagrange equations. You must study all the (numerous) cases ! It's because, as noted by suvrit, your problem is not a convex one.

If you are not on the boundary, the Lagrange equations are : find $A,B$ s.t. $CB-AB^TB=A^TC-A^TAB^T=0$ (writing is simple, yet solving is not). If, for instance, you add the constraints $a_{1,1}=1,b_{1,2}=-1$, then the equations are: find $A,B$ and real numbers $\lambda,\mu$ s.t., for every matrices (with correct dimensions) $H,K$, $trace((CB-AB^TB)H)+\lambda h_{1,1}=trace((A^TC-A^TAB^T)K)+\mu k_{1,2}=0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.