Min $+$ convolution is associative

Question

Although the following question was encountered in a Communication Networking textbook, the problem is still one of algebraic and analytic manipulation.

Define the (min,+) convolution of two real valued functions (domain is $\mathbb{R}^+$) f,g as $$f*g= \inf_{0 \leq s \leq t}\{ f(s) + g(t-s)\}$$

Interested readers may compare it with the usual definition of convolution. Anyhow, I needed to prove that this convolution was commutative and associative. I was able to prove the commutative part but associative seems to elude me.

Here is how far I got:

$$f*(g*h) = \inf_{0 \leq s \leq t}\{ f(t-s) + (g*h)(s)\}$$ $$ = \inf_{0 \leq s \leq t}\{ f(t-s) + \inf_{0 \leq u \leq s}\{ g(u) + h(s-u)\}\}$$ $$= \inf_{0 \leq s \leq t}\{ \inf_{0 \leq u \leq s} \{f(t-s) + g(u) + h(s-u)\}\}$$

I couldn't proceed from here. I have also tried expanding $(f*g)*h$ and trying to see if the steps "meet in the middle" but to no avail.

I'd appreciate it if someone could give me some insight on how to proceed with this.

Additional Info

In case of the convolution integral/summation, I used indicator functions to allow me to swap integrals. But here I need to swap two infima, the inner one dependent on the outer one. Is there an indicator function like trick that can be used here?

Answer 1

The infinum swapping is more straightforward than you think. In general, let $S\subseteq \mathbb{R}$ be non-empty, and $S=\bigcup_{\alpha\in I} S_\alpha$ for some arbitrary index set $I$.

We have $S_\alpha \subseteq S$ for all $\alpha$, so $$\inf S \leq \inf S_\alpha\quad \forall\alpha\in I.$$

Further, $$\forall \epsilon>0\quad\exists s\in S\text{ s.t. } \inf S + \epsilon > s,$$ and thence $$\forall \epsilon>0\quad\exists \alpha\in I \text { s.t. } \exists s\in S_\alpha\text{ s.t. } \inf S + \epsilon > s_\alpha \geq \inf S_\alpha.$$

So $$\inf S = \inf\ \{\inf S_\alpha | \alpha\in I\}.$$

Applying this to a function defined on a domain $D\subseteq \mathbb{R}^2$, let $D_u=\{(u,v)\,|\,v\in \mathbb{R},\ (u,v)\in D\}\subseteq D$, and substitute $S=f(D)$ and $S_u=f(D_u)$ above. Then

\begin{align*} \inf f(D) &= \inf_{u}\ (\inf f(D_u) )\\ &= \inf_{u}\ \inf_{v\in D_u} f(u,v) \end{align*}

In particular, it means that \begin{multline} \inf_{0\leq s\leq t} \inf_{0\leq u\leq s} (f(t-s)+g(u)+h(s-u)) =\\ \inf_{0\leq u \leq s\leq t} (f(t-s)+g(u)+h(s-u)). \end{multline}

Answer 2

Got it. We can use the following identity as shown by halfflat: $$\inf_{0\leq s \leq t} \inf_{0\leq u \leq s} f(u,s) = \inf_{0\leq u \leq t} \inf_{u \leq s \leq t} f(u,s).$$ It will be proved at the end. Let us use it first. Also note that convolution is commutative, the proof of which was easy and so I didn't need.

Now $$f*(g*h) = \inf_{0\leq s \leq t} f(t-s) + \inf_{0\leq u \leq s} g(s-u)+h(u) \\ = \inf_{0\leq u \leq t} \inf_{u \leq s \leq t} f(t-s)+g(s-u)+h(u)\\ = \inf_{0\leq u \leq t} \inf_{0 \leq s-u \leq t-u} f(t-u-(s-u))+g(s-u)+h(u)\\ = \inf_{0\leq u \leq t} \inf_{0 \leq v \leq t-u} f(t-u-v)+g(v)+h(u)\\ = \inf_{0\leq u \leq t} (f*g)(t-u) + h(u)=(f*g)*h$$

Proof of Identity: We use indicator functions. $$\inf_{0\leq s \leq t} \inf_{0\leq u \leq s} f(u,s) = \inf_{0\leq s \leq t} \inf_{0\leq u \leq t} f(u,s)1_{u\leq s}+f(s,s)1_{u > s} $$ This is true because $$\inf_{0\leq u \leq s} f(u,s) \leq f(s,s)$$

Now that the infima are no longer dependent, swap them to get $$ \inf_{0\leq u \leq t} \inf_{0\leq s \leq t} f(u,s)1_{u\leq s}+f(s,s)1_{u > s} \\ =\inf_{0\leq u \leq t} \min \left\{\inf_{u \leq s \leq t} f(u,s),\inf_{0\leq s\leq u}f(s,s)\right\}\\ \leq \inf_{0\leq u \leq t} \inf_{u \leq s \leq t} f(u,s) $$

To get the reverse inequality, observe that $$\inf_{0\leq u \leq t} \inf_{u \leq s \leq t} f(u,s)=\inf_{0\leq u \leq t} \inf_{0 \leq s \leq t} f(u,s)1_{s\geq u}+f(u,u)1_{s<u}$$

Now repeat the steps above.