Proximal Operator / Proximal Mapping for Composition of Functions 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)$?
 A: 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 and Wajs.
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).
