4
$\begingroup$

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) $

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Grant May 2 '15 at 14:40
  • 1
    $\begingroup$ @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. $\endgroup$ – passerby51 May 7 '15 at 17:25
  • $\begingroup$ I was wondering how the answer would change if we had $||X||_1$ where it's induced norm ? $\endgroup$ – user2806363 Jan 2 '17 at 16:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Sohil Shah May 4 '15 at 2:47
  • 1
    $\begingroup$ 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. $\endgroup$ – passerby51 May 7 '15 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.