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!

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


You must log in to answer this question.