# How to decompose a matrix into the outer product of two vectors?

I have a matrix $M$ and I would like to find two vectors $u$ and $v$, that minimize

$$\sum_{i,j} (M_{i,j}-u_iv_j)^2$$

How can I do this (numerically)?

Actually this is very simplified compared to my actual problem. For instance, I dont really have a full matrix, but only values for some range of $(i,j)$. However, I think once I know how to solve it in the general case, it should be straightforward to skip certain entries.

First, note that $\Sigma_{ij} (M_{ij}-u_iv_j)^2 = \|M-uv^T\|_F^2$, where $\|\cdot\|_F$ denotes the Frobenius norm of a matrix. If you're doing a Google search that may be helpful.

In the unconstrained case, there is an analytic solution given by the singular value decomposition. That is: let $M=U\Sigma V^T$ be the SVD of $M$, with the singular values arranged in nonincreasing order along the diagonal of $\Sigma$. Then the triple $(\sigma_1,u_1,v_1)$ formed from the first singular value, the first column of $U$, the first column of $V$, respectively, can be used to compute your $u$ and $v$. For instance, $u=\sigma_1 u_1$, $v=v_1$ would work, but really any $u=\alpha\sigma_1 u_1$, $v=\alpha^{-1} v_1$ for $\alpha\neq 0$ will work as well.

In the constrained case, unfortunately, you have a nonconvex optimization problem on your hands. Presumably you have a problem like this: \begin{array}{ll} \text{minimize} & \|M-uv^T\|_F^2 \\ \text{subject to} & L_{ij} \leq M_{ij} \leq U_{ij} \quad \forall i,j \end{array} where $L$ and $U$ are lower and upper bound matrices (possibly with infinite entries where you have missing information). This is an extreme (e.g., rank-1) version of a low-rank approximation problem.

There is a variety of literature about this, but again, it's nonconvex, which means that it's not easy to solve in practice. A common technique is to alternate between minimizing over $u$ (holding $v$ fixed) and minimizing over $v$ (holding $u$ fixed). There is no guarantee this gives you the best solution though.

EDIT: A simpler way to look at the problem where you know only a portion of the elements of $M$ is that you're minimizing only over the indices that you know: that is, $$\text{minimize} ~ \sum_{(i,j)\in\mathcal{I}} (M_{ij}-u_iv_j)^2$$ for some index set $\mathcal{I}$. After all, for the elements you don't know, you might as well just set $M_{ij}=u_iv_j$ after you've determined the $u$ and $v$ you prefer, so they will contribute 0 to the final Frobenius objective. Alas, that doesn't make the problem any easier; it's still nonconvex.

• thanks for the explanation. Actually I was working with SVD recently and I could have known that this is the way to go... I dont fully understand the second part of what you wrote. What do you mean with $L$ and $U$ as constraints? I mean when I have $M$ given, then they are just $L=M$ and $U=M$, isnt it? Maybe I will understand after reading the links you provided.... – idclev 463035818 Jan 13 '16 at 15:45
• You said that you didn't know $M$ completely, just some of the values. So for the $(i,j)$ entries that you know, you have $L_{ij}=U_{ij}=M_{ij}$. For those you don't know at all, you have $L_{ij}=-\infty$, $U_{ij}=+\infty$ (in other words, you just drop that constraint). If you have some sensible bounds fore these missing values of $M$, you could use them. Regardless, without full information about $M$, you have a nonconvex optimization problem, and that's the difficult one. – Michael Grant Jan 13 '16 at 15:47
• Added one more paragraph. – Michael Grant Jan 13 '16 at 15:50
• I think I understood. I am just a bit confused that you call the case where I dont know all entries (i.e. the one with less contraints) the "constrained case" – idclev 463035818 Jan 13 '16 at 15:51
• Well, I renamed it to "nonconvex" to avoid that confusion. Suffice it to say this: one of the more natural ways to express the model where some of the values of $M$ are missing is as a constrained problem. But it's not that important to get that right now: the real problem is that the missing value case is hard. – Michael Grant Jan 13 '16 at 15:52