What is a proximal operator and how would one derive it in general for a function?
In particular, if I had a function: $ f(x) = x^TQx + b^Tx + c $ How would I get the proximal operator for this if Q was a m dimensional square symmetric positive semidefinite matrix?
Best Answer
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) $$