[Math] Proximal Operator of Spectral Norm (Schatten Norm) of a Matrix

convex optimizationconvex-analysislinear algebraproximal-operatorsspectral-norm

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 ?

Best Answer

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.
Related Question