7
$\begingroup$

Suppose I have a convex function $f(x)$ for which I can easily compute the proximal mapping

prox$_f(z) = \arg\min_{x} f(x) + \frac{1}{2}||x-z||^2_2$

is there a simple expression for the proximal mapping of $f(\mathcal{A}(x))$ where $\mathcal{A}(x)$ is linear? That is, can I express

$\arg\min_{x} f(\mathcal{A}(x)) + \frac{1}{2}||x-z||^2_2$

in terms of prox$_f(z)$?

1 Answers 1

6

You might want to check the paper 'Signal recovery by proximal forward-backward splitting' by Combettes and Wajs (*) which reviews the prox and the prox of typical operations on functions (translation, scaling, …).

In that paper, you will find that if $\mathbf A$ is a semi-orthogonal linear transform (i.e.: $\mathbf A\mathbf A^* = \nu \mathbf{Id}$ with $\nu>0$) then there is a closed form of the prox of $f\circ \mathbf A$. I don't think there is one for the general case (I'd be tempted to say that it would be in that paper if it existed!)

The expression is the following:

$$ \mathrm{prox}_{f\circ \mathbf A}(x) = x + \nu^{-1} \mathbf{A}^*\left(\mathrm{prox}_{\nu f}(\mathbf A x) - \mathbf A x\right) \tag{1}$$

Hope this helps a little!

(*) Paper by Combettes & al

EDIT if you're interested in proving the above expression, here are the main steps of a possible proof:

  • Express the definition of the problem in a dual form (Fenchel-Rockafellar) and write the first order optimality conditions
  • Use Moreau's decomposition you should get something like $$ \nu^{-1}\mathbf A \mathbf d - y^* = \mathrm{prox}_{(\nu^{-1}f^\star)^\star}(\nu^{-1}\mathbf A\mathbf d)$$ where $y^*$ is the dual variable, and $^\star$ denotes the convex conjugate.
  • express the convex conjugate of $(\nu^{-1}f^\star)$
  • Shake the whole a little and using the optimality conditions, it should boil down to (1).

Another proof is using the fact that $\partial (f\circ \mathbf A) = \mathbf A^*\circ\partial f\circ \mathbf A$ (equality holds since $\mathbf A$ is surjective and hence the strong relint qualification condition holds, cf. Rockafellar's book). With Moreau decomposition $$x - \mathrm{prox}_{f\circ \mathbf A}(x) \in \mathbf A^*\partial f(\mathbf Ax)\in Im(\mathbf A^*)$$ multiply everything by $\mathbf A$ and it boils down to $$\mathbf A \mathrm{prox}_{f\circ\mathbf A}(x) = \mathrm{prox}_{\nu f}(\mathbf A x)$$ you can then use the decomposition of the prox in its orthogonal projection on $Im(\mathbf A^*)$ and on $ker(\mathbf A)$ and using the last equation you should end up with (1).

  • 1
    There's definitely no known formula for the general case. If there were, it would make it much easier to solve many convex optimization problems. For example, the proximal point method would become a practical method, because many convex objective functions can be expressed in the form $f(Ax)$, where $f$ has an easy prox-operator.2016-09-28
  • 0
    useful comment, thanks! (I guess in the general case that leaves with you with primal-dual method like Chambolle & Pock's)2016-09-28
  • 1
    Here's an example of something we could do if there were a nice formula for the prox-operator of $f(Ax)$ (where $A$ is any matrix). Currently we often minimize $g(x) + h(x)$ (where $g$ and $h$ are proximable) using the Douglas-Rachford method. But $g(x) + h(x) = f(Ax)$, where $A = \begin{bmatrix} I \\ I \end{bmatrix}$ and $f(x,y) = g(x) + h(y)$. Note that $f$ has an easy prox-operator (because $g$ and $h$ do). So, there would be no need for the Douglas-Rachford method -- we could just use the proximal point method.2016-09-28
  • 1
    Yes, in order to minimize $f(Ax)$, we could use the Chambolle-Pock method. Another option is to use the Douglas-Rachford method: we express $f(Ax)$ as $f(y) + I_A(x,y)$, where $I_A$ is the indicator function of the graph of $A$ (in other words, indicator function of $S = \{ (x,y) \mid y = Ax \}$. The prox-operator of $f$ is assumed to be easy, and the prox-operator of $I_A$ can be evaluated by projecting onto the graph of $A$, which requires solving a linear system involving $A$. A similar approach allows us to minimize objective functions of the form $f(x) + g(Ax)$ using Douglas-Rachford.2016-09-28
  • 0
    thanks @littleO, it's just a pity that this isn't a full question by itself so that more people can profit from your insight!2016-09-28