7
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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.... $\endgroup$ – idclev 463035818 Jan 13 '16 at 15:45
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Jan 13 '16 at 15:47
  • $\begingroup$ Added one more paragraph. $\endgroup$ – Michael Grant Jan 13 '16 at 15:50
  • $\begingroup$ 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" $\endgroup$ – idclev 463035818 Jan 13 '16 at 15:51
  • $\begingroup$ 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. $\endgroup$ – Michael Grant Jan 13 '16 at 15:52

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.