Let ${C \subset \mathbb{R}^n}$ be closed, convex, and nonempty. How might one show that the proximal mapping of the indicator function of $C$ is in fact the projection operator on to $C$?
[Math] Proximal Operator of the Indicator Function (Show It Is the Projection Operator)
convex optimizationconvex-analysisproximal-operators
Related Solutions
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).
The proximal operator is the map $\def\prox{\mathop{\rm prox}\nolimits}\prox_f \colon \mathbb R^m \to \mathbb R^m$ given by $$ \prox_f(x) = {\rm argmin}_{y \in \mathbb R^m} f(y) + \frac 12\|x-y\|^2 $$ For the given $f$ and $x,y \in \mathbb R^m$, we have \begin{align*} g_x(y) &:= f(y) + \frac 12\|x-y\|^2\\ &= y^tQy + b^ty + c + \frac 12x^tx + x^ty + \frac 12y^ty\\ &= y^t\left(Q + \frac 12\right)y + (b+x)^ty + c + \frac 12x^tx \end{align*} Now $Q + \frac 12$ is symmetric and positive definite, hence this has a unique minimum. To find it, we compute $g_x$'s critical point, we have for $h \in \mathbb R^m$: \begin{align*} g_x'(y)h &= 2y^t\left(Q + \frac 12\right)h + (b+x)^t h \end{align*} so $g_x'(y) = 0$ iff $$ y = \left(2Q + 1\right)^{-1}(b+x) $$ That is $$ \prox_f(x) = \left(2Q + 1\right)^{-1}(b+x) $$
Best Answer
Proximal operator of the indicator function $\iota_C$ is given by \begin{equation*} prox_{\iota_C}(z)= \begin{aligned} & \underset{x}{\text{argmin}} & & \frac{1}{2}\|x-z\|^2_2 + \iota_C(x) \\ \end{aligned} \end{equation*} which can be re-written as: \begin{equation*} prox_{\iota_C}(z)= \begin{aligned} & \underset{x \in C}{\text{argmin}} & & \frac{1}{2}\|x-z\|^2_2 \\ \end{aligned} \end{equation*} which is nothing but the projection of $z$ onto $C$.