9.19. Infimal Convolution#

Note

Some results in this section appear without complete proof at the moment. They have been collected from various sources. The proofs will be added later.

9.19.1. Definition#

Definition 9.82 (Infimal convolution)

Let $V$ be a real vector space. Let $f, g : V \to \overset{―}{R}$ be extended real-valued functions. Their infimal convolution, denoted by $f ◻ g : V \to \overset{―}{R}$ , is defined as

(9.11)#

(f ◻ g) (x) ≜ inf {f (y) + g (z) | y, z \in V, y + z = x} .

The infimal convolution of $f$ with $g$ is called exact at $x$ if the infimum in (9.11) is attained at some $y, z \in V$ such that $y + z = x$ .

The infimal convolution is called exact if it is attained at every $x \in X$ .

Remark 9.17 (Alternative definitions)

It is easy to see that

(f ◻ g) (x) = inf {f (y) + g (z) | y, z \in V, y + z = x, f (y) < \infty, g (z) < \infty} .

Another formulation is

(f ◻ g) (x) = inf {f (y) + g (x - y) | y \in V} .

This definition is reminiscent of the convolution operation in signal processing. The word infimal reminds of the infimum appearing in the definition. This is the motivation for the name infimal convolution.

Infimal convolution is also known as epigraphical addition because performing an infimal convolution of $f$ and $g$ amounts to the adding of the strict epigraphs of $f$ and $g$ . Recall from Definition 2.52 that the strict epigraph of a function $f : V \to \overset{―}{R}$ is given by

epi_{s} f ≜ {(x, t) \in V \oplus R | f (x) < t} .

We show in Property 9.42 that $epi_{s} f ◻ g = epi_{s} f + epi_{s} g$ .

From the definition, it is clear that $f ◻ g$ is the largest of all the functions $h : V \to \overset{―}{R}$ satisfying

h (y + z) \leq f (y) + g (z) \forall y, z \in X .

Example 9.87 (Cost minimization)

Consider a situation where a person sources a certain product from two different manufactures.

The person needs to acquire $x$ total quantity.
The total supply is given by the equation $x = y + z$ where $y$ is the quantity sourced from manufacturer A and $z$ is the quantity sourced from manufacture B.
Suppose the total cost of acquisition from manufacture A is given by a function $f (y)$ . It may not be linear as the manufacturer may have different levels of discounts as $y$ increases.
Similarly, the cost of acquisition from manufacture B is given by the function $g (z)$ .
Then the total cost is given by $f (y) + g (z)$ subject to the condition that $y + z = x$ .
Then the cost minimization problem is given by

$h (x) = inf {f (y) + g (z) | x = y + z} = (f ◻ g) (x) .$
We will also be interested in the set of solutions to the infimal problem; i.e.,

${(y, z) | f (y) + g (z) = (f ◻ g) (x)} .$

9.19.2. Basic Properties#

9.19.2.1. Domain#

Property 9.40 (Domain of infimal convolution)

Let $f, g : V \to \overset{―}{R}$ be given extended valued functions. Then

dom f ◻ g = dom f + dom g .

Proof. Let $z \in dom f + dom g$ .

Then there exist $x \in dom f$ and $y \in dom g$ such that $z = x + y$ .
Then $f (x) < \infty$ and $g (y) < \infty$ .
By definition of infimal convolution

$(f ◻ g) (z) \leq f (x) + g (y) < \infty .$
Hence $z \in dom f ◻ g$ .
Hence $dom f + dom g \subseteq dom f ◻ g$ .

For the converse, let $z \in dom f ◻ g$ .

Then $(f ◻ g) (z) < \infty$ .
First consider the case where $(f ◻ g) (z) = t \in R$ .
Then for any $ϵ > 0$ , there exist $x, y$ with $x + y = z$ such that

$t \leq f (x) + g (y) \leq t + ϵ .$
Since $f (x) + g (y)$ is finite, hence $f (x) < \infty$ and $g (y) < \infty$ .
Hence $x < dom f$ and $y \in dom g$ .
Thus $z = x + y \in dom f + dom g$ .
Now consider the case where $(f ◻ g) (z) = - \infty$ .
Then for every $M \in R$ , there exist $x, y$ with $x + y = z$ such that

$f (x) + g (y) \leq M .$
Thus $f (x) < \infty$ and $g (y) < \infty$ for such pairs of $x, y$ .
Consequently $z = x + y \in dom f + dom g$ .
Combining the two cases $dom f ◻ g \subseteq dom f + dom g$ .

Finally

We have already shown that $dom f + dom g \subseteq dom f ◻ g$ .
Thus $dom f + dom g = dom f ◻ g$ .

9.19.2.2. Epigraph#

Property 9.41 (Connection with epigraph)

(f ◻ g) (x) = inf {r \in R | (x, r) \in epi f + epi g} .

Proof. Let $t = (f ◻ g) (x)$ . Define $S = {r \in R | (x, r) \in epi f + epi g}$ . We need to show that $t$ is the greatest lower bound of the set $S$ .

Let $(x, r) \in epi f + epi g$ .
Then there exists $(y, r_{1}) \in epi f$ and $(z, r_{2}) \in epi g$ so that $x = y + z$ and $r = r_{1} + r_{2}$ .
Thus $f (y) + g (z) \leq r_{1} + r_{2} = r$ (by epigraphs).
By infimal convolution definition $t \leq f (y) + g (z) \leq r$ .
Thus we have shown that $t \leq r$ if $(x, r) \in epi f + epi g$ .
Thus $t$ is a lower bound of the set $S$ .
Now choose any $ϵ > 0$ .
Then there exists $y \in dom f$ and $z \in dom g$ with $x = y + z$ such that

$f (y) + g (z) \leq t + ϵ .$
Note that $(y, f (y)) \in epi f$ and $(z, g (z)) \in epi g$ .
Hence $(y + z, f (y) + f (z)) \in epi f + epi g$ .
Consequently $(y + z, t + ϵ) \in epi f + epi g$ .
Replacing $x = y + z$ , we have $(x, t + ϵ) \in epi f + epi g$ .
Thus, for every $ϵ > 0$ , $t + ϵ \in S$ .
Hence $t$ must be the greatest lower bound of the set $S$ .
In other words, $t = inf S$ as desired.

Property 9.42 (Strict epigraph of infimal convolution)

Let $f, g : V \to \overset{―}{R}$ be given extended valued functions. Then

epi_{s} f ◻ g = epi_{s} f + epi_{s} g .

Proof. We show the set inclusion from both sides.

Let $(x, r) \in epi_{s} f ◻ g$ .
Then $(f ◻ g) (x) < r$ .
Then there exist $y \in dom f$ and $z \in dom g$ with $x = y + z$ such that

$f (y) + g (z) < r .$

This is directly from the definition of infimal convolution.
Consequently, we can split $r$ as $r = r_{1} + r_{2}$ such that $f (y) < r_{1}$ and $g (z) < r_{2}$ .
1. Let $s = f (y)$ , $t = g (z)$ .
2. Let $d = r - (s + t) > 0$ .
3. Let $e = \frac{d}{2} > 0$ .
4. Let $r_{1} = s + e$ and $r_{2} = t + e$ .
5. Then $r_{1} + r_{2} = s + t + 2 e = s + t + d = r$ .
6. Also $f (y) = s < r_{1}$ and $g (z) = t < r_{2}$ .
Then $(y, r_{1}) \in epi_{s} f$ and $(z, r_{2}) \in epi_{s} g$ by definition of strict epigraphs.
Hence $(y + z, r_{1} + r_{2}) = (x, r) \in epi_{s} f + epi_{s} g$ .
Thus $epi_{s} f ◻ g \subseteq epi_{s} f + epi_{s} g$

For the converse

Let $(x, r) \in epi_{s} f + epi_{s} g$ .
Then there is $(y, r_{1}) \in epi_{s} f$ and $(z, r_{2}) \in epi_{s} g$ so that

$x = y + z and r = r_{1} + r_{2} .$
Thus $f (y) < r_{1}$ and $g (z) < r_{2}$ .
Thus $f (y) + g (z) < r_{1} + r_{2} = r$ .
Hence $(f ◻ g) (x) \leq f (y) + g (z) < r$ .
Hence $(x, r) \in epi_{s} f ◻ g$ .
Hence $epi_{s} f + epi_{s} g \subseteq epi_{s} f ◻ g$ .

Property 9.43 (Epigraph of infimal convolution)

Let $f, g : V \to \overset{―}{R}$ be given functions. Then

epi f + epi g \subseteq epi f ◻ g .

The equality holds if and only if the infimal convolution is exact at each $x \in V$ where $(f ◻ g) (x) \in R$ .

Proof. We first show the inclusion.

Let $(x, r) \in epi f + epi g$ .
Then there is $(y, r_{1}) \in epi f$ and $(z, r_{2}) \in epi g$ so that

$x = y + z and r = r_{1} + r_{2} .$
Thus $f (y) \leq r_{1}$ and $g (z) \leq r_{2}$ .
Thus $f (y) + g (z) \leq r_{1} + r_{2} = r$ .
Hence $(f ◻ g) (x) \leq f (y) + g (z) \leq r$ .
Hence $(x, r) \in epi f ◻ g$ .
Hence $epi f + epi g \subseteq epi f ◻ g$ .

Next we show that the reverse inclusion holds if infimal convolution is exact at each $x \in V$ where $(f ◻ g) (x) \in R$ .

Let $(x, r) \in epi f ◻ g$ .
Then $(f ◻ g) (x) \leq r$ .
Consider first the case where $(f ◻ g) (x) = - \infty$ .
Then for any $M \in R$ , there exist $y \in dom f$ and $z \in dom g$ with $x = y + z$ such that $f (y) + f (z) < M$ .
In particular, there exist $y, z$ so that $f (y) + f (z) < r$ .
Hence $(x, r) \in epi f + epi g$ .
Now if $(f ◻ g) (x) \in R$ then the infimal convolution is exact.
Since the infimal convolution is exact, hence there exist $y \in dom f$ and $z \in dom g$ with $x = y + z$ such that

$f (y) + g (z) = (f ◻ g) (x) \leq r .$

This is directly from the definition of infimal convolution.
Consequently, we can split $r$ as $r = r_{1} + r_{2}$ such that $f (y) \leq r_{1}$ and $g (z) \leq r_{2}$ .
Then $(y, r_{1}) \in epi f$ and $(z, r_{2}) \in epi g$ by definition of epigraphs.
Hence $(y + z, r_{1} + r_{2}) = (x, r) \in epi f + epi g$ .
Thus $epi_{s} f ◻ g \subseteq epi f + epi g$ .

Finally, to show that this condition is necessary, assume that there exists a point $x \in V$ where $(f ◻ g) (x) \in R$ and the infimal convolution is not exact.

Let $t = (f ◻ g) (x)$ .
Then $(x, t) \in epi f ◻ g$ .
Since the infimal convolution is not exact, hence for any $y \in dom f$ and $z \in dom g$ with $x = y + z$

$t < f (y) + g (z) .$
For contradiction, assume that $(x, t) \in epi f + epi g$ .
Then there exist $(y, t_{1}) \in epi f$ and $(z, t_{2}) \in epi g$ so that $x = y + z$ and $t = t_{1} + t_{2}$ .
Thus $f (y) \leq t_{1}$ and $g (z) \leq t_{2}$ .
Thus $f (y) + g (z) \leq t_{1} + t_{2} = t$ .
We have arrived at a contradiction.
Hence $(x, t) \notin epi f + epi g$ .

9.19.2.3. Convexity#

Theorem 9.274 (Infimal convolution of convex functions)

Let $f : V \to (- \infty, \infty]$ be a proper convex function and $g : V \to R$ be a real valued convex function. Then $f ◻ g$ is convex.

Proof. Define $h (x, y) = f (y) + g (x - y)$ .

Since $f$ and $g$ are convex, hence $h$ is convex.
We can easily show that for any $x \in V$ , there exists $y \in V$ such that $h (x, y) < \infty$ .
1. Pick any $x \in V$ .
2. Choose any $y \in dom f$ .
3. Then $f (y) < \infty$ .
4. Since $g$ is real valued, hence $g (x - y) < \infty$ .
5. Thus $h (x, y) = f (y) + g (x - y) < \infty$ .
Then due to Theorem 9.118

$(f ◻ g) (x) = inf_{y \in V} h (x, y) = inf_{y \in V} [f (y) + g (x - y)]$

is convex as a partial minimization of the function $h (x, b y)$ w.r.t. $y$ .

It is still possible that $f ◻ g$ is not a proper function and may be equal to $- \infty$ at some $x$ .

Example 9.88 (Set distance function as infimal convolution)

Let $C \subseteq V$ be a nonempty convex set.

The indicator function $I_{C}$ is a proper convex function.
The norm function $‖ \cdot ‖$ is a real valued convex function.
By Theorem 9.274, $I_{C} ◻ ‖ \cdot ‖$ is convex.
But then

$(I_{C} ◻ ‖ \cdot ‖) (x) = inf_{y \in V} (I_{C} (y) + ‖ x - y ‖) = inf_{y \in C} ‖ x - y ‖ = d_{C} (x) .$
Thus $d_{C}$ (the distance function to a convex set) is convex.

9.19.3. Conjugates#

Theorem 9.275 (Conjugate of infimal convolution of proper functions)

For two proper functions $h_{1}, h_{2} : V \to (- \infty, \infty]$ , it holds that:

(h_{1} ◻ h_{2})^{*} = h_{1}^{*} + h_{2}^{*} .

Proof. Pick $y \in V^{*}$ . Then

\begin{aligned} (h_{1} ◻ h_{2})^{*} (y) & = sup_{x \in V} {⟨ x, y ⟩ - (h_{1} ◻ h_{2}) (x)} \\ = sup_{x \in V} {⟨ x, y ⟩ - inf_{u \in V} (h_{1} (u) + h_{2} (x - u))} \\ = sup_{x \in V} sup_{u \in V} {⟨ x, y ⟩ - h_{1} (u) - h_{2} (x - u)} \\ = sup_{u \in V} sup_{x \in V} {⟨ x - u, y ⟩ + ⟨ u, y ⟩ - h_{1} (u) - h_{2} (x - u)} \\ = sup_{u \in V} {sup_{x \in V} {⟨ x - u, y ⟩ - h_{2} (x - u)} + ⟨ u, y ⟩ - h_{1} (u)} \\ = sup_{u \in V} {h_{2}^{*} (y) + ⟨ u, y ⟩ - h_{1} (u)} \\ = h_{2}^{*} (y) + sup_{u \in V} {⟨ u, y ⟩ - h_{1} (u)} \\ = h_{2}^{*} (y) + h_{1}^{*} (y) \\ = (h_{1}^{*} + h_{2}^{*}) (y) . \end{aligned}

Theorem 9.276 (Conjugate of sum of convex functions)

Let $h_{1} : V \to (- \infty, \infty]$ be a proper convex function and $h_{2} : V \to R$ be a real valued convex function. Then

(h_{1} + h_{2})^{*} = h_{1}^{*} ◻ h_{2}^{*} .

Proof. The proof is more complicated and requires the application of Fenchel’s duality theorem (Theorem 10.85).

Pick any $y \in V^{*}$ .
Elaborating the conjugate function

$\begin{aligned} (h_{1} + h_{2})^{*} (y) & = sup_{x \in V} {⟨ x, y ⟩ - (h_{1} + h_{2}) (x)} \\ = sup_{x \in V} {⟨ x, y ⟩ - h_{1} (x) - h_{2} (x)} \\ = - inf_{x \in V} {h_{1} (x) + h_{2} (x) - ⟨ x, y ⟩} \\ = - inf_{x \in V} {h_{1} (x) + g (x)} \end{aligned}$

where $g (x) = h_{2} (x) - ⟨ x, y ⟩$ .
We note that since $h_{2}$ is a real valued convex function, hence $g$ is also a real valued convex function.
We note that

$(ri dom h_{1}) \cap (ri dom g) = (ri dom h_{1}) \cap V = ri dom h_{1} \neq \emptyset .$
Applying the Fenchel’s duality theorem (Theorem 10.85),

$inf_{x \in V} {h_{1} (x) + g (x)} = sup_{z \in V} {- h_{1}^{*} (z) - g^{*} (- z)} .$
Further

$\begin{aligned} g^{*} (- z) & = sup_{x \in V} {⟨ x, - z ⟩ - g (x)} \\ = sup_{x \in V} {⟨ x, - z ⟩ - h_{2} (x) + ⟨ x, y ⟩} \\ = sup_{x \in V} {⟨ x, y - z ⟩ - h_{2} (x)} \\ = h_{2}^{*} (y - z) . \end{aligned}$
Consequently

$\begin{aligned} (h_{1} + h_{2})^{*} (y) & = - inf_{x \in V} {h_{1} (x) + g (x)} \\ = - sup_{z \in V} {- h_{1}^{*} (z) - g^{*} (- z)} \\ = inf_{z \in V} {h_{1}^{*} (z) + g^{*} (- z)} \\ = inf_{z \in V} {h_{1}^{*} (z) + h_{2}^{*} (y - z)} \\ = (h_{1}^{*} ◻ h_{2}^{*}) (y) . \end{aligned}$

This completes the proof.

Corollary 9.28 (Function sum as conjugate of infimal convolution of conjugates)

Let $h_{1} : V \to (- \infty, \infty]$ be a proper closed convex function and $h_{2} : V \to R$ be a real valued convex function. Then

h_{1} + h_{2} = (h_{1}^{*} ◻ h_{2}^{*})^{*} .

Proof. We proceed as follows.

Since $h_{1}$ is proper and $h_{2}$ is real valued, hence $h_{1} + h_{2}$ is proper.
Since both $h_{1}$ and $h_{2}$ are closed functions, hence $h_{1} + h_{2}$ is closed.
Since both $h_{1}$ and $h_{2}$ are convex functions, hence $h_{1} + h_{2}$ is convex.
Thus $h_{1} + h_{2}$ is a proper, closed convex function.
By Theorem 9.242,

$(h_{1} + h_{2})^{* *} = h_{1} + h_{2} .$
By Theorem 9.276,

$(h_{1} + h_{2})^{*} = h_{1}^{*} ◻ h_{2}^{*} .$
Hence

$h_{1} + h_{2} = (h_{1} + h_{2})^{* *} = [(h_{1} + h_{2})^{*}]^{*} = [h_{1}^{*} ◻ h_{2}^{*}]^{*} .$

Theorem 9.277 (Representation of the infimal convolution by conjugates)

Let $h_{1} : V \to (- \infty, \infty]$ be a proper convex function and $h_{2} : V \to R$ be a real valued convex function. Suppose $h_{1} ◻ h_{2}$ is a real valued function. Then

h_{1} ◻ h_{2} = (h_{1}^{*} + h_{2}^{*})^{*} .

Proof. We proceed as follows.

By Theorem 9.275

$(h_{1} ◻ h_{2})^{*} = h_{1}^{*} + h_{2}^{*} .$
Since $h_{1}$ is proper and convex and $h_{2}$ is real valued and convex, hence by Theorem 9.274, $h_{1} ◻ h_{2}$ is convex.
By hypothesis $h_{1} ◻ h_{2}$ is also real valued.
Thus $h_{1} ◻ h_{2}$ is proper and closed.
Since $h_{1} ◻ h_{2}$ is proper, closed and convex; hence by Theorem 9.242

$(h_{1} ◻ h_{2})^{* *} = h_{1} ◻ h_{2} .$
Hence

$h_{1} ◻ h_{2} = [(h_{1} ◻ h_{2})^{*}]^{*} = [h_{1}^{*} + h_{2}^{*}]^{*} .$

9.19.4. Convexity#

An interesting application of constructing a convex function from a convex set in $V \oplus R$ is the fact that addition of epigraphs leads to another convex function. This is also known as infimal convolution.

Theorem 9.278 (Infimal convolution)

Let $f_{1}, \dots, f_{m} : V \to (- \infty, \infty]$ be proper convex functions. Let $f : V \to (- \infty, \infty]$ be defined as

f (x) = inf {f_{1} (x_{1}) + \dots + f_{m} (x_{m}) | x_{i} \in V, x_{1} + \dots + x_{m} = x} .

Then, $f$ is a proper convex function.

Proof. Let $F_{i} = epi f_{i}$ and $F = F_{1} + \dots + F_{m}$ .

Since $f_{i}$ is convex, hence $F_{i} = epi f_{i}$ are convex sets for $i = 1, \dots, m$ .
Sum of convex sets is convex. Hence, $F$ is a convex set.
By definition of $F$ , $(x, t) \in F$ if and only if there exists $x_{i} \in V$ and $t_{i} \in R$ with $(x_{i}, t_{i}) \in F_{i}$ such that $x = x_{1} + \dots + x_{m}$ and $t = t_{1} + \dots + t_{m}$ .
It follows that $f_{i} (x_{i}) \leq t_{i}$ for $i = 1, \dots, m$ .
Consequently, $f_{1} (x_{1}) + \dots + f_{m} (x_{m}) \leq t_{1} + \dots + t_{m}$ .
By Theorem 9.111, a function $g : V \to (- \infty, \infty]$ defined as

$g (x) ≜ inf {t \in R | (x, t) \in F}$

is a proper convex function.
Let $T = {t \in R | (x, t) \in F}$ . Then $g (x) = inf T$ .
We note that

$T = {t | (x_{i}, t_{i}) \in F_{i}, t = t_{1} + \dots + t_{m}, x = x_{1} + \dots + x_{m}} .$
We claim that $g = f$ .

To show that $g = f$ , we need to do the following.

Show that $dom f = dom g$ .
Then, show that for every $x \in dom f$ , $f (x) = g (x)$ .

Assume that $x \notin dom g$ .

Then, there is no $t \in R$ such that $(x, t) \in F$ .
Thus, there is no $(x_{i}, t_{i}) \in F_{i}$ for $i = 1, \dots, m$ such that $x = x_{1} + \dots + x_{m}$ .
Thus, for every $x_{i} \in V$ such that $x = x_{1} + \dots + x_{m}$ there is at least one $i$ such that there is no $t_{i} \in R$ such that $(x_{i}, t_{i}) \in F_{i}$ .
Thus, for every $x_{i} \in V$ such that $x = x_{1} + \dots + x_{m}$ there is at least one $i$ such that $f_{i} (x_{i}) = \infty$ .
Thus, for every $x_{i} \in V$ such that $x = x_{1} + \dots + x_{m}$ , $f_{1} (x_{1}) + \dots + f_{m} (x_{m}) = \infty$ .
Thus, $f (x) = \infty$ .
Thus, $x \notin dom f$ .

Assume that $x \notin dom f$ .

Then, $f (x) = \infty$ .
Thus, for every $x_{i} \in V$ such that $x = x_{1} + \dots + x_{m}$ , $f_{1} (x_{1}) + \dots + f_{m} (x_{m}) = \infty$ .
Thus, for every $x_{i} \in V$ such that $x = x_{1} + \dots + x_{m}$ , there exists at least one $i$ such that $f_{i} (x_{i}) = \infty$ .
Thus, for every $x_{i} \in V$ such that $x = x_{1} + \dots + x_{m}$ , there exists at least one $i$ such that $x_{i} \notin dom f_{i}$ .
Thus, for every $x_{i} \in V$ such that $x = x_{1} + \dots + x_{m}$ , there exists at least one $i$ such that there is no $t_{i} \in R$ with $(x_{i}, t_{i}) \in F_{i}$ .
Thus, there is no $(x_{i}, t_{i}) \in F_{i}$ for $i = 1, \dots, m$ such that $x = x_{1} + \dots + x_{m}$ .
Thus, there is no $t \in R$ such that $(x, t) \in F$ .
Thus, $x \notin dom g$ .

Thus, $x \notin dom f ⟺ x \notin dom g$ . Thus, $dom f = dom g$ .

Let us now consider some $x \in dom f = dom g$ . Then, both $f (x)$ and $g (x)$ are finite. Our goal is to show that $f (x) = g (x)$ .

We first show that $f (x) \leq g (x)$ .

For every $x_{i} \in V$ with $x = x_{1} + \dots + x_{m}$ , and $f_{i} (x_{i})$ finite, we have:

$f (x) \leq f_{1} (x_{1}) + \dots + f_{m} (x_{m}) .$
Thus, for every $(x_{i}, t_{i}) \in F_{i}$ with $x = x_{1} + \dots + x_{m}$ , we have

$f (x) \leq f_{1} (x_{1}) + \dots + f_{m} (x_{m}) \leq t_{1} + \dots + t_{m} .$
Thus, for every $(x, t) \in F$ with $(x_{i}, t_{i}) \in F_{i}$ , $x = x_{1} + \dots + x_{m}$ , $t = t_{1} + \dots + t_{m}$ , we have

$f (x) \leq t .$
Taking the infimum on the R.H.S. over the set $T$ , we get

$f (x) = f (x) \leq g (x) = z .$

Now, for contradiction, assume that $f (x) < g (x)$ .

For every $t \in R$ such that $(x, t) \in F$ , we have $g (x) \leq t$ .
Thus, for every $(x_{i}, t_{i}) \in F_{i}$ with $x = x_{1} + \dots + x_{m}$ , we have

$g (x) \leq t_{1} + \dots + t_{m} .$
Then, for every $(x_{i}, t_{i}) \in F_{i}$ with $x = x_{1} + \dots + x_{m}$ , we have

$f (x) < t_{1} + \dots + t_{m} .$
Thus, there exists $r > 0$ such that for every $(x_{i}, t_{i}) \in F_{i}$ with $x = x_{1} + \dots + x_{m}$ , we have

$f (x) + r \leq t_{1} + \dots + t_{m} .$

TO BE COMPLETED.

Topics in Signal Processing

Infimal Convolution

Contents

9.19. Infimal Convolution#

9.19.1. Definition#

9.19.2. Basic Properties#

9.19.2.1. Domain#

9.19.2.2. Epigraph#

9.19.2.3. Convexity#

9.19.3. Conjugates#

9.19.4. Convexity#