Proximal Operator Matrix Regression

Question

We have that $W \in \mathbb{R}^{n \times m}$ and we want to find $$\text{prox}(W) = \arg\min_Z\Big[\frac{1}{2} \langle W-Z, W-Z \rangle+\lambda ||Z||_* \Big]$$

Here, $||Z||_*$ represents the trace norm of $Z$.

I tried getting the derivative of the whole thing, and to do that I used that the derivative of trace norm is $UV^T$ (according to Proximal Operator and the Derivative of the Matrix Nuclear Norm). However, after this, I don't really know how to proceed.

Answer 1

The prox of the trace norm (also called the Nuclear Norm) is known in closed form. The formula (and code for numerical implementation) are found here:

http://proximity-operator.net/multivariatefunctions.html

You were on the right track. In general, if your matrix function is really just a symmetric operation involving singular values, you can use SVD to express the prox of the matrix function in terms of the prox of the symmetric function. In this case, your "symmetric function" is just the one-norm being applied to the singular values of your matrix.

For a rigorous statement, check out Section 24.8 of Bauschke/Combettes' book, volume 2.

Answer 2

Since you use the Inner Product of Matrices then the problem can be rewritten as:

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

Which matches Proximal Operator for Schatten Norm.

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.