# Bounded domain matrix factorization

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

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

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