Crossposted on Operations Research Stack Exchange
The problem.
Let $X,A \in\mathbb{R}^{n\times m}$ and let $W\in\mathbb{R}^{nm\times nm}$ be a positive definite matrix. I want to know if there is a closed-form solution to this problem $$ \min_{X} \frac{1}{2}\text{vec}(X-A)^\top W\text{vec}(X-A) + \|X\|_*, $$ where $\|X\|_*$ denotes the nuclear norm of $X$, and $\text{vec}(X)$ denotes the vectorization operation of the matrix $X$.
A solution in the unweighted case.
For $W = I$ (the identity matrix), the problem is known as Singular Value Thresholding (SVT), and corresponds to: $$ \min_{X} \frac{1}{2}\|X-A\|_F^2 + \|X\|_*, $$ where $\|X\|_F$ is the Frobenius norm of $X$, and a solution is found in this paper (thm. 2.1), and is nicely expressed as
$$X = U\max(0,S-I)V^\top,$$
where $A = USV^\top$ is the SVD of the matrix $A$. In the weighted case I am not sure whether is possible to express the solution in closed form. This problem is also known as Weighted Singular Value Thresholding (WSVT) and a closed-form solution has not been found yet.
Related work.
Paper 1 studies the problem of the Weighted Low-Rank Approximation (WLRA) problem which is more difficult than the one proposed in this question (the problem in the question is a convex relaxation of the one in the paper). They have a closed-form solution in the case $W$ can be expressed as $W = W_1 \otimes W_2$. This was my initial problem, however ...
Paper 2 proves that the WLRA problem is NP-hard in general and that is the reason why I moved from WLRA to WSVT (actually my initial problem includes also other constraints, but that is another story).
Paper 3 studies the WSVT problem, but they come up with a numerical solution (no analytical solution). Is there really no way one can solve the problem in closed form as for the unweighted SVT problem?
Paper 4 studies a related problem (the same as this related question), where the nuclear norm is weighted by a vector $w$. In this case, we have an analytical solution. However, I tried to recast my problem in this form with no success.
Why bother with a closed form solution?
I really need an analytical solution because the original problem is much more complex (includes other convex constraints and another outer optimization over another set of variables). To solve such optimization problem, I believe a closed-form solution for the simpler problem considered in this question would help considerably.
