best rank r approximation for non-Frobenius norm

Question

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.

Answer 1

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.