4
$\begingroup$

The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to Eckart-Young theorem, is truncated SVD - just keep $r$ largest singular values. What if I need to construct best rank $r$ approximation in a different matrix norm, for example quadratic $\|M\|^2 = \sum_{i,j}S_{ij}M_{ij}^2$, for some fixed matrix $S$, $S_{ij} > 0$? It would be nice if the resulting procedure is computationally efficient.

$\endgroup$
3
  • $\begingroup$ The norm that you are suggesting is simply a weighted version of the Frobenius norm. So you just have to rescale the entries of the matrix according to the weights and apply Eckart-Young on the resulting problem. $\endgroup$ Feb 19, 2013 at 20:01
  • $\begingroup$ Problem with this is that definition of rank is not invariant with this rescaling - for example, if you do element-wise rescaling of matrix by itself you can get matrix of rank $0$. $\endgroup$
    – Timur
    Feb 19, 2013 at 20:18
  • $\begingroup$ Hmm, good point! I was too quick and didn't think it through. $\endgroup$ Feb 19, 2013 at 20:55

1 Answer 1

4
$\begingroup$

Your problem is what is commonly known as weighted low-rank matrix approximation. This problem has not received as much interest as it deserves. A good starting point on this problem is the "Weighted low-rank approximations" paper by Srebro and Jaakola. They outline an EM (Expectation Maximization) based algorithm to tackle this problem.

The fundamental difference between this weighted version of the problem and the unweighted one is the structure of the critical points of the objective function: $\sum_{ij} s_{ij}(m_{ij} - b_{ij})^2$, where $B$ is the low-rank approximation you are seeking. For the unweighted case, each local minimum of the objective is also global (the other critical points are saddle points); this structure is lost in the weighted case (unless the matrix $S$ happens to have some special structure, like diagonal, or rank one, etc.). This makes a purely SVD based solution impossible.

But since the paper cited above, several authors have looked at versions of this problem, so several new algorithms for approximately solving it may be available, but don't expect a "closed-form" solution like the pure SVD case.

$\endgroup$
2
  • $\begingroup$ Interesting - can you give a citation for the fact that in the unweighted has each local minimum is also a global minimum? $\endgroup$
    – user21162
    Feb 24, 2013 at 20:58
  • $\begingroup$ @robinson: please see the cited paper for this claim. $\endgroup$
    – Suvrit
    Feb 25, 2013 at 0:57

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.