# What is proximal operator of nuclear norm in weighted space? (variable metric)

I am trying to find out proximal operator of nuclear norm in weighted space.

First, proximal operator of nuclear norm is

$$\text{prox}_{\lambda | \cdot |_*}(A) = \arg\min_X \frac{1}{2}\|X-A\|_F^2 + \lambda |X|_* = S_{\lambda}(A),$$ where $$S_{\lambda}$$ is matrix soft-thresholding.

Now, I would like proximal operator for weighted space, that is, (for vector inputs)

$$\text{prox}_{H,f(x)}(u) = \arg\min_x \frac{1}{2}\|x-u\|_H^2 + f(x)$$ for some symmetric positive definite matrix. Here, we assume $$H$$ to be diagonal matrix.

So, Question 1: Would proximal operator for matrix functions be $$\text{prox}_{H,f(x)}(A) = \arg\min_X \frac{1}{2}\|X-A\|_H^2 + f(x),$$ where $$\|X\|_H= \|H^{1/2}X H^{-1/2}\|_2$$?

Preliminaries for second question:

Second question is about dimensions. Say, the original problem I was trying to solve has vector variable $$x \in \mathbb{R}^n$$. However, for nuclear norm, one would need to turn it into matrix via reshape function. The issue is that the variable metric is wrt vector, $$H \in \mathbb{R}^{n, n}$$, where $$H$$ is diagonal. But dimension of $$X \in \mathbb{R}^{\sqrt{n},\sqrt{n}}$$

See: the necessary and sufficient optimality condition for regular case would be $$X-A \in \partial \lambda \|A\|_* = \lambda * \{UV^{\top} + W | U^{\top}W = 0, WV=0, \|W\|_2 \leq 1\}.$$ Here, clearly the dimensions match.

However, for weighted (or variable metric) case, we have $$H(X-A) \in \partial \lambda \|A\|_*,$$where dimensions don't match. One trick I thought was to vectorize it, as, $$H(\text{vec}(X)-\text{vec}(A)) \in \partial \lambda \|A\|_*.$$ (We would use variable metric proximal operator for matrix fuctions stated above, and replace matrix as vector, and change frobenius norm to 2 norm while doing it)

In addition, we have following equality, \begin{align} \|X\|_* &= \min_{X=AB'} \|A\|_F \|B\|_F \\ &= \min_{X=AB'} \frac{1}{2}(\|A\|_F^2+\|B\|_F^2 )\\ &= \min_{X=AB'} \frac{1}{2}(\|\text{vec}(A)\|_2^2 + \|\text{vec}(B)\|_2^2)\\ &= \|\text{vec}(\Sigma^{1/2})\|_2^2, \end{align} where $$X=U\Sigma V^{\top}$$ is SVD of $$X$$, and $$A = U\Sigma^{1/2}, B=V\Sigma^{1/2}$$.

Question 2: Is this "legal"?

My attempt: to have optimality condition for this case, we would have $$H(\text{vec}(X)-\text{vec}(A)) \in \partial \lambda \|A\|_* = \partial \lambda \|\text{vec}(\Sigma^{1/2})\|_2^2 = \lambda 2 \bar{\sigma}^{1/2}$$ where $$\bar{\sigma}$$ is $$\text{vec}(\Sigma)$$

This implies that $$A_{i,j} = X_{i,j}$$ for all $$i \neq j$$, and for all $$i=j$$, we have $$H_{i*\sqrt{n}} * (X_{i,i} - A_{i,i}) \in \lambda \sigma_i^{1/2}.$$

Does this mean $$A_{i,i} = X_{i,i} - 2H_{i*\sqrt{n}}^{-1} \lambda \sigma_i^{1/2}$$? Somehow I feel like I've made some mistake - somehow I feel like "entire space" of $$H$$ should be acting on the operator, not only $$\sqrt{n}$$-th entries.

Any input would be appreciated!

• @RodrigodeAzevedo fixed. thanks for commenting it out
– HHSS
Oct 27, 2021 at 22:11
• Strongly related question: math.stackexchange.com/questions/4295898/… Nov 4, 2021 at 19:30
• I encountered the exact same issue for the dimensions of the subgradient in the above-mentioned related question. Did you find a solution? Nov 4, 2021 at 19:57
• In your last equation, how do you define $H_{i*\sqrt{n}}$? Nov 4, 2021 at 20:02