# 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

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.