# Proximal Operator of ${L}_{\infty,1}$ Norm (Mixed Norm) of a Matrix

How can I calculate the proximal operator of mixed norm $${L}_{\infty,1}$$ for any general matrix, $$X\in R^{m\times n}$$ i.e.,

$${X}^{\ast} = \arg \min_X {\left\| X \right\|}_{\infty, 1} + \frac{1}{2 \tau} {\left\| X - Y \right\|}_{F}^{2}$$

Where $${\left\| X \right\|}_{\infty, 1} = \max \left( {\left\| {X}_{i,:} \right\|}_{1}, \forall i = 1, \dots, m \right)$$

• Would you believe some crazy folks use CVX to implement custom proximal operators? It works, yes, but it's slow. It's good for testing out the ideas on small models. – Michael Grant May 2 '15 at 14:40
• @MichaelGrant, It is not that crazy :) That is what I have found CVX to be good for, trying out ideas without worrying about implementation details. Also, good for double-checking your implementation with some accurate interior-point methods. Cheers. – passerby51 May 7 '15 at 17:25
• I was wondering how the answer would change if we had $||X||_1$ where it's induced norm ? – user2806363 Jan 2 '17 at 16:03

Here is a partial answer. Let us write $x_i$ and $y_i$ for rows of $X$ and $Y$. Then,
\begin{align} \min_X \| X\|_{\infty,1} + \frac1{2\tau} \| X - Y\|_F^2 &= \min_X \Big[ \max_i \| x_i\|_1 + \sum_j \frac1{2\tau} \| x_j - y_j\|_2^2 \Big] \\ &= \min_X \max_i \Big[ \| x_i\|_1 + \sum_j \frac1{2\tau} \| x_j - y_j\|_2^2 \Big]\\ &\ge \max_i \min_X \Big[ \| x_i\|_1 + \sum_j \frac1{2\tau} \| x_j - y_j\|_2^2 \Big] \\ &= \max_i \Big[ \| S_\tau(y_i)\|_1 + \frac1{2\tau} \| S_\tau(y_i) - y_i\|_2^2 \Big] \end{align} where $S_\tau$ is the soft-thresholding operator (the proximal operator associated with the $\ell_1$ norm), and the inequality is by weak duality. Let $i_*$ be an index that is the maximizer of the last expression. Let $Y^*_{i,:} = y_i$ if $i\neq i_*$ and $Y^*_{i,:} = S_\tau(y_{i_*})$. If $\|y_i\|_1 \le \|S_\tau(y_{i_*})\|_1$ for $i \neq i_*$, then $Y^*$ is the desired solution (if I haven't made mistakes!) What happens otherwise seems to be more complicated.
• I was also thinking of hoping to solve this using auxiliary variable i.e., $\min_{X,\eta} \eta + \frac{1}{2\tau} ||X-Y||_F^2 \quad s.t. ||X_{i,:}||_1 \leq \eta \quad \forall i=1,\dots,m$. Any idea on how to solve for both the variables $\mathbf{X}, \eta$ together ? – Sohil Shah May 4 '15 at 2:47
• That is also a good idea. For fixed $\eta$ your problem reduces to projecting each row on the $\ell_1$ ball of radius $\eta$. This has been studied a lot and there is "almost" a closed form solution (Just search for projection onto $\ell_1$ ball.) This gives you a way to evaluate the objective as a function of $\eta$ for each given $\eta$. From there, the problem is that of optimizing over $\eta$, a scalar variable. This is relatively easy: You are trying to minimize a convex function $\eta \mapsto f(\eta)$ using only 0th order information on $f$. You might try the bisection method. – passerby51 May 7 '15 at 17:20