The best rank $r$ approximation to a given matrix $M$ in Frobenius norm, according to EckartYoung 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.

$\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 EckartYoung on the resulting problem. $\endgroup$ – Federico Poloni Feb 19 '13 at 20:01

$\begingroup$ Problem with this is that definition of rank is not invariant with this rescaling  for example, if you do elementwise rescaling of matrix by itself you can get matrix of rank $0$. $\endgroup$ – Timur Feb 19 '13 at 20:18

$\begingroup$ Hmm, good point! I was too quick and didn't think it through. $\endgroup$ – Federico Poloni Feb 19 '13 at 20:55
Your problem is what is commonly known as weighted lowrank matrix approximation. This problem has not received as much interest as it deserves. A good starting point on this problem is the "Weighted lowrank 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 lowrank 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 "closedform" solution like the pure SVD case.