# Proximal Operator of Spectral Norm (Schatten Norm) of a Matrix

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 ?

• 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. – Michael Grant Apr 12 '15 at 22:52
• Ok. You are right. Thanks. – Sohil Shah Apr 13 '15 at 2:38
• Are you looking for a "simple and efficient" algorithm, or any generic optimization algorithm will suffice? – Alex Shtof Apr 13 '15 at 9:19
• Any generic solution is sufficient. – Sohil Shah Apr 13 '15 at 15:15
• See this paper, section 6.7. – Pantelis Sopasakis Nov 6 '16 at 22:10

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.