5
$\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$
2
  • 1
    $\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$ Commented Apr 12, 2015 at 22:52
  • 1
    $\begingroup$ See this paper, section 6.7. $\endgroup$ Commented Nov 6, 2016 at 22:10

1 Answer 1

Reset to default
6
$\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 Value 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$
2
  • $\begingroup$ Note that in the case $p=2$ (Frobenius norm), a much simpler closed form of prox exists which doesn’t involve any SVD. $\endgroup$ Commented Sep 25, 2019 at 21:18
  • $\begingroup$ @LorenzoStella, Indeed. In that case it is much easier to solve it as we're dealing with vectors (Vectorize the matrices). $\endgroup$ Commented Sep 26, 2019 at 13:57

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.