best rank r approximation for non-Frobenius norm

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.

-
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. –  Federico Poloni Feb 19 '13 at 20:01
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$. –  Timur Feb 19 '13 at 20:18
Hmm, good point! I was too quick and didn't think it through. –  Federico Poloni Feb 19 '13 at 20:55

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.

-
Interesting - can you give a citation for the fact that in the unweighted has each local minimum is also a global minimum? –  user21162 Feb 24 '13 at 20:58
@robinson: please see the cited paper for this claim. –  Suvrit Feb 25 '13 at 0:57
Thanks, Suvrit. Great reference. –  Timur Feb 26 '13 at 21:53