4
$\begingroup$

I would like to calculate the proximal operator of spectral norm for any general matrix, $X \in \mathbb R^{m\times n}$, i.e.,

$$X^* = \arg \min_X \|X\|_2 + \frac{1}{2\tau} \|X-Y\|_F^2$$

I understand that the proximal operator for nuclear norm $\|X\|_*$ is computed using the Singular Value Thresholding (SVT) algorithm, which is similar to the $\ell_1$-norm on a vector of singular values. Thus can we assume that proximal operator for spectral norm can also be similarly computed by taking the $\ell_{\infty}$-norm on a singular value vector ?

$\endgroup$
  • $\begingroup$ It may be a language issue, but it is not the case that "singular value thresholding... is similar to the $\ell_1$-norm on a vector of singular values." The correct thing to say is that the proximal operator of the spectral norm is similar to the proximal operator of the $\ell_1$-norm. And if you express it that way, then yes, the proximal operator of the spectral norm is similar to the proximal operator of the $\ell_\infty$ norm. $\endgroup$ – Michael Grant Apr 12 '15 at 22:52
  • $\begingroup$ Ok. You are right. Thanks. $\endgroup$ – Sohil Shah Apr 13 '15 at 2:38
  • $\begingroup$ Are you looking for a "simple and efficient" algorithm, or any generic optimization algorithm will suffice? $\endgroup$ – Alex Shtof Apr 13 '15 at 9:19
  • $\begingroup$ Any generic solution is sufficient. $\endgroup$ – Sohil Shah Apr 13 '15 at 15:15
  • $\begingroup$ See this paper, section 6.7. $\endgroup$ – Pantelis Sopasakis Nov 6 '16 at 22:10
2
$\begingroup$

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

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

$$ {\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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.