The Moreau-Yosida Regularization is given by

\begin{equation} f_\mu(x) = \inf_y \left( f(y) + \frac{1}{2\mu} \| x - y \|^2 \right). \end{equation}

We know that $L(x, y) = f(y) + \frac{1}{2\mu} \| x - x \|^2$ is jointly convex in $x$ and $y$.

Source: https://statweb.stanford.edu/~candes/math301/Lectures/Moreau-Yosida.pdf

Why is the epigraph of $f_\mu(x)$ a projection of a convex set?

  • $\begingroup$ Who claims it is a projection? I would rather call it the intersection of (infinitely many) convex sets. $\endgroup$ – LinAlg Feb 12 at 20:25
  • $\begingroup$ The course note states that "$f_u(x)$'s epigraph is the projection of a convex set" on the first page. $\endgroup$ – MathematicaIsAwesome Feb 12 at 22:10
  • 1
    $\begingroup$ I do not see how you get $\{(x,t) : \inf_y L(x,y) \leq t\}$ from a projection of $\{(x,y,t) : L(x,y) \leq t\}$. Ask the author. $\endgroup$ – LinAlg Feb 13 at 0:12

To the best of my knowledge, this is a common mistake. It might be, of course, a projection of some convex set onto the $(x, t)$ coordinates, but it is not "the" convex set you might first think of.

Like any other 'infimal convolution', the epigraph of the Moreau-Yosida regularization is a sum of epigraphs. To be precise, it is the Minkowski sum of the epigraph of $f$ and the epigraph of $\frac{1}{2\mu}\|x\|_2^2$: $$ \operatorname{epi}(f_\mu) = \operatorname{epi}(f)+\operatorname{epi}(\tfrac{1}{2\mu}\|\cdot\|_2^2) \equiv \{ (x+y, t+s) : (x, t) \in \operatorname{epi}(f),~(y, s) \in \operatorname{epi}(\tfrac{1}{2\mu}\|\cdot\|_2^2) \} $$ See the excellent paper on Epigraphical Analysis by Attouch and Wets for more details. The sum of convex sets is convex, and that is one reason why $f_\mu$ is convex.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.