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$
  • 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 '14 at 15:49
  • $\begingroup$ Why the downvote? It seems a perfectly reasonable question to me. $\endgroup$ – Federico Poloni May 15 '14 at 12:53
  • $\begingroup$ btw, I did not downvote this question, it is perfectly reasonable, though not research level $\endgroup$ – Suvrit May 15 '14 at 15:12
  • 2
    $\begingroup$ There is no standard off-the-shelf method to efficiently solve this problem, therefore it is research level. $\endgroup$ – Mark L. Stone Oct 8 '15 at 1:10
1
$\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, privacy policy and cookie policy

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