What is Moreau’s Decomposition Theorem?

Let $f: \mathbb{R}^n \mapsto \mathbb{R}$ be a convex function. Moreau’s Decomposition Theorem is the following result:

Theorem (Moreau Decomposition). For all $x \in \mathbb{R}^n$ ,

$x = \textbf{prox}_{f} (x) + \textbf{prox}_{f^*} (x)$ ,

where $\textbf{prox}_{f}$ is the proximal operator for $f$ and $f^*$ is the convex conjugate of $f$ .

Here is the proof: Let $z = \textbf{prox}_{f} (x)$ . Then,

$\begin{aligned} z = \textbf{prox}_{f} (x) \quad &\Leftrightarrow \quad x - z \in \partial f(z) \\ &\Leftrightarrow \quad z \in \partial f^*(x-z) \\ &\Leftrightarrow \quad x - (x-z) \in \partial f^*(x-z) \\ &\Leftrightarrow \quad x - z = \textbf{prox}_{f^*} (x) \\ &\Leftrightarrow \quad x = \textbf{prox}_{f} (x) + \textbf{prox}_{f^*} (x). \end{aligned}$

The second equivalence is a result involving convex conjugates and subdifferentials (see this post for statement and proof) while the 4th equivalence is a property of the proximal operator (see the note at the end of this post).

Extended Moreau Decomposition

The extended version of Moreau’s Decomposition Theorem involves a scaling factor $\lambda > 0$ . It states that for all $x$ ,

$\begin{aligned} x = \textbf{prox}_{\lambda f} (x) + \textbf{prox}_{\lambda^{-1} f^*} (x / \lambda). \end{aligned}$

Proof: Applying Moreau decomposition to the function $\lambda f$ gives

$x = \textbf{prox}_{\lambda f} (x) + \textbf{prox}_{(\lambda f)^*} (x).$

Using the definitions of the proximal operator and the convex conjugate,

$\begin{aligned} \textbf{prox}_{(\lambda f)^*} (x) &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \| x - u \|_2^2 + (\lambda f)^* (u) \right\} \\ &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \| x - u \|_2^2 + \sup_v \left[ u^\top v - \lambda f(v) \right] \right\} \\ &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \|(x/\lambda) - (u / \lambda) \|_2^2 + \frac{1}{\lambda} \sup_v \left[ (u / \lambda)^\top v - f(v) \right] \right\} \\ &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \|(x/\lambda) - (u / \lambda) \|_2^2 + \frac{1}{\lambda} f^*( u / \lambda) \right\} \\ &= \underset{u}{\text{argmin}} \left\{ \frac{1}{2} \| (x / \lambda) - u \|_2^2 + \lambda^{-1}f^* (u) \right\} \\ &= \textbf{prox}_{\lambda^{-1} f^*} (x / \lambda). \end{aligned}$

References:

Gu, Q. (2016). “SYS 6003: Optimization. Lecture 25.”

Statistical Odds & Ends

What is Moreau’s Decomposition Theorem?

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply