Legendre Transformation

Legendre transformation, its geometry intuition, and applications in machine learning.

• Legendre conjugate
• Geometry explaination
• Properties
• Applications

Legendre conjugate

For a strictly convex function $f:\mathrm{\Omega }\subset {\mathbb{R}}^n\mapsto \mathbb{R}$ with ${\mathrm{\nabla }}^{2}f\succ 0$, its Legendre conjugate is defined as

$$f^{\ast }(\mathbf{y})=\underset{\mathbf{x}\in \mathrm{\Omega }}{max}⟨\mathbf{y},\mathbf{x}⟩-f(\mathbf{x}),\mathbf{y}\in {\mathbb{R}}^n.$$

As $\mathbf{x}\mapsto \underset{\mathbf{x}\in \mathrm{\Omega }}{max}⟨\mathbf{y},\mathbf{x}⟩-f(\mathbf{x})$ is a strictly concave function of $\mathbf{x}$ (linear function + concave function) it has unique point ${\mathbf{x}}^{\ast }$ that attains the maximum value

$$⟨\mathbf{y},{\mathbf{x}}^{\ast }⟩-f({\mathbf{x}}^{\mathbf{\ast }})\mathrm{with}\mathrm{\nabla }f({\mathbf{x}}^{\ast })=\mathbf{y}.$$

Hence, we can explain $f^{\ast }(\mathbf{y})$ like this, which point $\mathbf{x}\in \mathrm{\Omega }$ has a gradient $\mathrm{\nabla }f(\mathbf{x})$ equals to the given $\mathbf{y}$.

Geometry explaination

Let us approach Legendre conjugate from the geometry perspective to gain more intuition.

Recall that the epigraph for a convex function $f$ is

$$\mathcal{O}=\{(\mathbf{x},z)\mid \mathbf{x}\in \mathrm{\Omega },z\ge f(\mathbf{x})\}.$$

How can we describe its boundary $\partial \mathcal{O}$ ?

Of course, given a $\mathbf{x}\in \mathrm{\Omega }$ we have $(\mathbf{x},z=f(\mathbf{x}))\in \partial \mathcal{O}$, representing $\partial \mathcal{O}$ from $\mathbf{x}$-coordinate.

Let us consider the tangent hyperplane passing a fixed point $({\mathbf{x}}_0,f({\mathbf{x}}_0))\in \mathrm{\Omega }$:

$$z=⟨\mathrm{\nabla }f({\mathbf{x}}_0),\mathbf{x}-{\mathbf{x}}_0⟩+f({\mathbf{x}}_0).$$

The key point here is that there is only one point of $\partial \mathcal{O}$ that admits a tangent hyperplane with slope $\mathrm{\nabla }f({\mathbf{x}}_0),$ since $\mathrm{\nabla }f(\mathbf{x})$ is a monotonous increasing function w.r.t $\mathbf{x}$ (${\mathrm{\nabla }}^{2}f\succ 0$). Therefore, we may also represent the boundary $\partial \mathcal{O}$ with the parameter $\mathbf{y}=\mathrm{\nabla }f(\mathbf{x})$, representing $\partial \mathcal{O}$ from $\mathbf{y}$-coordinate. In summary, we can identify a point $(\mathbf{x},z)\in \partial \mathcal{O}$, either by its $\mathbf{x}$-coordinate or its $\mathbf{y}$-coordinate ($\mathbf{y}=\mathrm{\nabla }f(\mathbf{x})$). Namely, we have exhibited a dual coordinate system.

How can we write the boundary $\mathcal{O}$ in terms of $\mathbf{y}$-coordinate? Note that any hyperplane with a given slope $\mathrm{\nabla }f({\mathbf{x}}_{\mathbf{0}})$ passing through $\partial \mathcal{O}$ has a unique point on $z$-axis. These lines admit one equation:

$$z=⟨\mathrm{\nabla }f({\mathbf{x}}_{\mathbf{0}}),\mathbf{p}-\mathbf{x}⟩+f(\mathbf{x}),$$

where $(\mathbf{x},f(\mathbf{x}))$ is the intersection point between the hyperplane and $\partial \mathcal{O}$ (there may be multiple intersection points, and any of them is valid). Among these parallel lines, $z=⟨\mathrm{\nabla }f({\mathbf{x}}_{\mathbf{0}}),\mathbf{p}-{\mathbf{x}}_0⟩+f({\mathbf{x}}_0)$ is the unique one that attains the minimized $z$-intersection value

$$-⟨\mathrm{\nabla }f({\mathbf{x}}_0),{\mathbf{x}}_0⟩+f({\mathbf{x}}_0).$$

Remark: This is because $f$ is a convex function and $f(\mathbf{x})\ge ⟨\mathrm{\nabla }f({\mathbf{x}}_{\mathbf{0}}),\mathbf{x}-{\mathbf{x}}_0⟩+f({\mathbf{x}}_0)$, which concludes

$$-⟨\mathrm{\nabla }f({\mathbf{x}}_{\mathbf{0}}),\mathbf{x}⟩+f(\mathbf{x})\ge -⟨\mathrm{\nabla }f({\mathbf{x}}_{\mathbf{0}}),{\mathbf{x}}_0⟩+f({\mathbf{x}}_0).$$

We can also imagine this visually. The hyperplane $z=⟨\mathrm{\nabla }f({\mathbf{x}}_0),\mathbf{x}-{\mathbf{x}}_0⟩+f({\mathbf{x}}_0)$ only has one intersection with $\partial \mathcal{O}$ wheras other lines $z=⟨\mathrm{\nabla }f({\mathbf{x}}_0),\mathbf{p}-\mathbf{x}⟩+f(\mathbf{x})$ with $\mathbf{x}\ne {\mathbf{x}}_0$ all have mutiple intersections with $\partial \mathcal{O}$; we can move any of the later lines to get the former by decreasing the $z$-axis intersection.

The tangent hyperlane equation $z=⟨\mathrm{\nabla }f({\mathbf{x}}_0),\mathbf{x}-{\mathbf{x}}_0⟩+f({\mathbf{x}}_0)$ can also be writen as

$$⟨\left[\begin{array}{c}\mathrm{\nabla }f({\mathbf{x}}_0)\\ -1\end{array}\right],\left[\begin{array}{c}\mathbf{x}\\ z\end{array}\right]-\left[\begin{array}{c}{\mathbf{x}}_0\\ f({\mathbf{x}}_0)\end{array}\right]⟩=0$$

This form reveals that $[\mathbf{x},z{]}^{\mathrm{\top }}\in {\mathbb{R}}^{n+1}$ is any point in the hyperplane and $[f({\mathbf{x}}_0),-1{]}^{\mathrm{\top }}\in {\mathbb{R}}^{n+1}$ is the normal vector perpendicular to the hyperplane at point $[{\mathbf{x}}_0,f({\mathbf{x}}_0){]}^{\mathrm{\top }}$.

So we can represent $({\mathbf{x}}_0,z=f({\mathbf{x}}_0))\in \partial \mathcal{O}$ with $\mathbf{y}:=\mathrm{\nabla }f({\mathbf{x}}_{\mathbf{0}})$ as

$${\mathbf{x}}_0={\mathrm{argmin}}_{\mathbf{x}}-⟨\mathbf{y},\mathbf{x}⟩+f(\mathbf{x})={\mathrm{argmax}}_{\mathbf{x}}⟨\mathbf{y},\mathbf{x}⟩-f(\mathbf{x}).$$

In other words, finding a point $\mathbf{x}\in \mathrm{\Omega }$ that has a gradient $\mathrm{\nabla }f(\mathbf{x})$ equals to the given $\mathbf{y}$, which is equivalent to

$$\underset{\mathbf{x}\in \mathrm{\Omega }}{max}⟨\mathbf{y},\mathbf{x}⟩-f(\mathbf{x}),\mathbf{y}\in {\mathbb{R}}^n.$$

Remark: $⟨\mathbf{y},0-\mathbf{x}⟩$ describes the change of $z$ value of the hyperplane $z=⟨\mathbf{y},\mathbf{p}-\mathbf{x}⟩+f(\mathbf{x})$ when $\mathbf{p}$ goes from $\mathbf{x}$ to $0$. Given the slope $\mathbf{y}$, the hyperplane passing the point $(\mathbf{x},f(\mathbf{x}))$ with $\mathrm{\nabla }f(\mathbf{x})=\mathbf{y}$ achieves the minimum value on $z$-axis.

Interpreting Legendre transformation in one sentence:

$$\underset{\mathbf{x}\in \mathrm{\Omega }}{max}⟨\mathbf{y},\mathbf{x}⟩-f(\mathbf{x}),\mathbf{y}\in {\mathbb{R}}^n$$

is a linear function of $\mathbf{y}$ and thus it amounts to

$$\underset{\mathbf{x}\in \mathrm{\Omega }}{min}⟨\mathbf{y},-\mathbf{x}⟩+f(\mathbf{x}),\mathbf{y}\in {\mathbb{R}}^n,$$

which is the minimized $z$-intersection value that hyperplane

$$z=⟨\mathbf{y},\mathbf{p}-\mathbf{x}⟩+f(\mathbf{x}),\mathbf{p}\in {\mathbb{R}}^n$$

could attain.

Properties

• $f^{\ast }(\mathbf{y})=\underset{\mathbf{x}\in \mathrm{\Omega }}{max}⟨\mathbf{y},\mathbf{x}⟩-f(\mathbf{x})$ is a convex function, since it is a linear function of $\mathbf{y}$.
• $f^{\ast \ast }=f$.
• $\mathrm{\nabla }{f}^{\ast }=(\mathrm{\nabla }f{)}^{-1}$ or $(\mathrm{\nabla }{f}^{\ast }{)}^{-1}=\mathrm{\nabla }f$ if $\mathrm{\nabla }f$ is inversible.
• $f(\mathbf{x})+f^{\ast }(\mathbf{y})\ge ⟨\mathbf{y},\mathbf{x}⟩$.

Applications

Smoothed max operator.