6
$\begingroup$

\begin{equation} \arg\min_{X} \frac{1}{2}\|X-Y\|_{F}^2 + \tau\|X\|_{*} \end{equation} where $\tau\geq 0,Y\in \mathbb{C}^{n\times n}$ and $\|\cdot\|_{*}$ is the nuclear norm. What's the solution of this convex optimization?

In some literature, they show the solution of this optimization problem in real condition (where $Y\in \mathbb{R}^{n\times n}$) is $\mathcal{D}_{\tau}(Y)$, where $\mathcal{D}_{\tau}$ is the soft-thresholding operator. But I wonder what the solution is in complex condition (where $Y\in \mathbb{C}^{n\times n}$)? Is it exactly the same? which is $\mathcal{D}_{\tau}(Y)$.

$\endgroup$
11
  • $\begingroup$ Add some context by showing anything you have tried. $\endgroup$
    – StubbornAtom
    Nov 11, 2016 at 13:39
  • $\begingroup$ I would guess that if $Y$ is diagonal with non-negative entries, then the solution $X$ should be diagonal with non-negative entries too. $\DeclareMathOperator{\diag}{diag}$ With that, it suffices to solve this problem: suppose that $Y$ is diagonal with $Y = \diag(y_1,\dots,y_n)$ and $y_i \geq 0$. Similarly, take $X = \diag(x_1,\dots,x_n)$ with $x_i \geq 0$. The problem now becomes $$ \arg \min_{x_1,\dots,x_n} \frac 12 \sum_{i}((x_i - y_i)^2 + 2\tau x_i) $$ From there, extend the result using SVD. $\endgroup$
    – Ben Grossmann
    Nov 11, 2016 at 13:39
  • $\begingroup$ @Chenfl the solution in the "complex condition" is exactly the same $\endgroup$
    – Ben Grossmann
    Nov 11, 2016 at 14:12
  • $\begingroup$ Show me a reference for real matrices, and I'll explain how every step in the proof still works over complex matrices. $\endgroup$
    – Ben Grossmann
    Nov 11, 2016 at 14:33
  • $\begingroup$ It would be much easier for me to answer your concerns, however, if you explained specifically why you expect something to change for the problem over complex matrices. $\endgroup$
    – Ben Grossmann
    Nov 11, 2016 at 14:36

1 Answer 1

Reset to default
5
$\begingroup$

Basically, for any Schatten Norm the algorithm is pretty simple.

If we use Capital Letter $ A $ for Matrix and Small Letter for Vector than:

$$ {\operatorname*{Prox}}_{\lambda \left\| \cdot \right\|_{p}} \left( A \right) = \arg \min_{X} \frac{1}{2} \left\| X - A \right\|_{F}^{2} + \lambda \left\| X \right\|_{p} $$

Where $ \left\| X \right\|_{p} $ is the $ p $ Schatten Norm of $ X $.

Defining $ \boldsymbol{\sigma} \left( X \right) $ as a vector of the Singular Values of $ X $ (See the Singular Values Decomposition).

Then the Proximal Operator Calculation is as following:

  1. Apply the SVD on $ A $: $ A \rightarrow U \operatorname*{diag} \left( \boldsymbol{\sigma} \left( A \right) \right) {V}^{T} $.
  2. Extract the vector of Singular Values $ \boldsymbol{\sigma} \left( A \right) $.
  3. Calculate the Proximal Operator of the extracted vector using Vector Norm $ p $: $ \hat{\boldsymbol{\sigma}} \left( A \right) = {\operatorname*{Prox}}_{\lambda \left\| \cdot \right\|_{p}} \left( \boldsymbol{\sigma} \left( A \right) \right) = \arg \min_{x} \frac{1}{2} \left\| x - \boldsymbol{\sigma} \left( A \right) \right\|_{2}^{2} + \lambda \left\| x \right\|_{p} $.
  4. Return the Proximal of the Matrix Norm: $ \hat{A} = {\operatorname*{Prox}}_{\lambda \left\| \cdot \right\|_{p}} \left( A \right) = U \operatorname*{diag} \left( \hat{\boldsymbol{\sigma}} \left( A \right) \right) {V}^{T} $.

The mapping of Matrix Norm into Schatten Norm:

  • Frobenius Norm - Given by $ p = 2 $ in Schatten Norm.
  • Nuclear Norm - Given by $ p = 1 $ in Schatten Norm.
  • Spectral Norm (The $ {L}_{2} $ Induced Norm of a Matrix) - Given by $ p = \infty $ in Schatten Norm.

So in your case use the Schatten Norm where $ p = 1 $.
The Proximal Operator for Vector Norm for $ {L}_{1} $ Norm is the Soft Thresholding Operator.

$\endgroup$
3
  • $\begingroup$ Thank you for this answer. Does it make any sense to define $l_0$ Schatten norm, whose proximal mapping involves hard thresholding of singular values (instead of soft thresholding)? $\endgroup$
    – User32563
    Mar 21, 2020 at 14:59
  • $\begingroup$ I guess it has the same sense as applying it to a vector. Namely you are trying to vanish the effect of some directions (As opposed to weaken them with the $ {L}_{1} $). $\endgroup$
    – Royi
    Mar 21, 2020 at 15:13
  • $\begingroup$ hello @Chenfl , was wondering if you guys got the solution for the objective function mentioned in the question ? If yes, kindly spare some time to educate me on the solution. I am working on exact same optimization problem (same constraints and regularization) $\endgroup$
    – Upendra01
    Aug 5, 2020 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .