Properties of Convolution

Visual explanation of Convolution

• Definition
  - $(f *g)(t)=\displaystyle\int_{-\infty }^{\infty }{f(\tau)g(t-\tau)d \tau}$
• 
  1. Express each function in terms of a dummy variable $τ$.
  2. Reflect one of the functions: $g(τ)$$→$ $g(−τ).$
  3. Add a time-offset t, which allows $g(−τ)$ to slide along the $τ$-axis. If t is a positive value, then $g(t−τ)$ is equal to $g(−τ)$ that slides or is shifted along the $τ$ axis toward the right (toward +∞) by the amount of t. If t is a negative value, then $g(t−τ)$ is equal to $g(−τ)$ that slides or is shifted toward the left (toward $-∞$) by the amount of $|t|$.
  4. Start t at $−∞$ and slide it all the way to $+∞$. Wherever the two functions intersect, find the integral of their product. In other words, at time t, compute the area under the function $f(τ)$ weighted by the weighting function $g(t−τ)$.

The resulting waveform (not shown here) is the convolution of functions $f$ and $g$.

If $f(t)$ is a unit impulse, the result of this process is simply $g(t)$.

• In this example, the red-colored "pulse", $g(τ)$ is an even function $( g(−τ)=g(τ) )$ so convolution is equivalent to correlation. A snapshot of this "movie" shows functions $g(t−τ)$ and $f(τ)$ (in blue) for some value of parameter $t$ which is arbitrarily defined as the distance along the $τ$ axis from the point $τ=0$ to the center of the red pulse. The amount of yellow is the area of the product $f(τ)⋅g(t−τ)$ computed by the convolution/correlation integral. The movie is created by continuously changing $t$ and recomputing the integral. The result (shown in black) is a function of $t$ but is plotted on the same axis as $τ$ for convenience and comparison.
• In this depiction, $f(τ)$could represent the response of an RC circuit to a narrow pulse that occurs at $τ=0$. In other words, if $g(τ)=δ(τ)$, the result of convolution is just $f(t)$ But when $g(τ)$is the wider pulse (in red), the response is a "smeared" version of $f(t)$. It begins at $t=−0.5$, because we defined $t$ as the distance from the $τ=0$ axis to the center of the wide pulse (instead of the leading edge).

Convolution of CNN

• Let's briefly review why it is called convolution. In mathematics, the convolution between two functions says $f,g: \mathbb{R} ^{d}\to \mathbb{R}$ is defined as
  - $(f *g)(\boldsymbol{x})=\displaystyle\int_{}^{}{f(\boldsymbol{z})g(\boldsymbol{x}-\boldsymbol{z})d \boldsymbol{z}}$
• That is, we measure the overlap between $f$ and $g$ when one function is "flipped" and shifted by $\boldsymbol{x}$
• Whenever we have discrete objects, the integral turns into a sum
• For instance
  - for vectors from the set of square summable infinite dimensional vectors with index running over $\mathbb{Z}$ , we obtain the following definition
  - $(f *g)(i)=\displaystyle\sum_{a}^{}{f(a)g(i-a)}$
• For two-dimensional tensors
  - we have a corresponding sum with indices $(a,b)$ for $f$ and $(i-a,j-b)$ for $g$ , respectively :
  - $(f *g)(i,j)=\displaystyle\sum_{a}^{}{\displaystyle\sum_{b}^{}{f(a,b)g(i-a,j-b)}}$
• This looks similar to $[\boldsymbol{H}]_{i,j}=u+\displaystyle\sum_{a=-\Delta}^{\Delta}{\displaystyle\sum_{b=-\Delta}^{\Delta}{[\boldsymbol{V}]_{a,b}[\boldsymbol{X}]_{i+a,j+b}}}$ , with one major difference. Rather than using $(i+a,j+b)$ we are using the difference instead

Convolution Thorem (of Fourier Transform)

• Condition
  - Consider two function $g(x),h(x)$ with Fourier transform $G,H$. and let $\mathcal{F}$ denotes the Fourier Transform
  - $G(f)=\mathcal{F}(g)=\displaystyle\int_{\infty }^{\infty }{g(t)e^{-2\pi i ft}dt}$
  - $H(f)=\mathcal{F}(h)=\displaystyle\int_{\infty }^{\infty }{h(t)e^{-2\pi i ft}dt}$
  
• The convolution of $g$ and $h$ is defined by
  - $(g *h)(t)=\displaystyle\int_{-\infty }^{\infty }{g(\tau)h(t-\tau)d \tau}$
• Statement
  - $\mathcal{F}(g*h)=G(f)H(f)$
• Proof
  - $\mathcal{F}(g*h)=\displaystyle\int_{-\infty }^{\infty }[{\displaystyle\int_{-\infty }^{\infty }{g(\tau)h(t-\tau)d \tau}}]e^{-2 \pi i ft}dt=\displaystyle\int_{-\infty }^{\infty }{[\displaystyle\int_{-\infty }^{\infty }{h(t- \tau)e^{-2\pi i ft}dt}]g(\tau)d \tau}$
  - (by Fubini's Theorem )
  - let $t'=t-\tau$ . then $t=t'+\tau$ , $dt=dt'$ : as we see $\tau$ as a constant
  - $=\displaystyle\int_{-\infty }^{\infty }{[\displaystyle\int_{-\infty }^{\infty }{h(t')e^{-2\pi i f(t'+\tau)}}dt']g(\tau)d \tau}$
  - $=H(f) \displaystyle\int_{-\infty }^{\infty }{g(\tau)e^{-2 \pi i f \tau}d \tau}=H(f)G(f)$

Convolution Thorem (of Laplace Transform)

• Condition
  - Consider two function $g(x),h(x)$ with Laplace transform $G,H$. and let $\mathcal{L}$ denotes the Laplace Transform
  - $G(s)=\mathcal{L}(g)=\displaystyle\int_{\infty }^{\infty }{g(t)e^{-st}dt}$
  - $H(s)=\mathcal{L}(h)=\displaystyle\int_{\infty }^{\infty }{h(t)e^{-st}dt}$
  
• The convolution of $g$ and $h$ is defined by
  - $(g *h)(t)=\displaystyle\int_{-\infty }^{\infty }{g(\tau)h(t-\tau)d \tau}$
• Statement
  - $\mathcal{L}(g*h)=G(s)H(s)$
• Proof
  - $\mathcal{L}(g*h)=\displaystyle\int_{-\infty }^{\infty }{[\displaystyle\int_{-\infty }^{\infty }{g(\tau)h(t-\tau)d \tau}]}e^{-st}dt=\displaystyle\int_{-\infty }^{\infty }{[\displaystyle\int_{-\infty }^{\infty }{h(t-\tau)e^{-st}dt}]g(\tau)d \tau}$
  - (by Fubini's Theorem )
  - let $t'=t-\tau$ . then $t=t'+\tau$ , $dt=dt'$ : as we see $\tau$ as a constant
  - $=\displaystyle\int_{-\infty }^{\infty }{[\displaystyle\int_{-\infty }^{\infty }{h(t')e^{-s(t'+\tau)}}dt']g(\tau)d \tau}$
  - $=H(s) \displaystyle\int_{-\infty }^{\infty }{g(\tau)e^{-s\tau}d \tau}=H(s)G(s)$