Tags: #notesonai #mnemonic Topics: [[Maths]], [[Deep Learning]], [[Computer Vision]] ID: 20230109111157 --- # Convolution The convolution of two functions $f$ and $g$ is denoted by $*$ as the integral of the product of the two functions after one is reversed and shifted $ (f \cdot g)(t) \triangleq \int_{-\infty}^{\infty} f(\tau) g(t-\tau) d \tau=\int_{-\infty}^{\infty} f(t-\tau) g(\tau) d \tau $ For images $a_{r c}=x * w=\sum_{i=-a}^{a} \sum_{j=-b}^{b} x_{r-i, c-j} \cdot w_{i j}$ A convolution operation is both linear and shift invariant. Convolution has commutative property. The convolution operation reaches a maximum, only in cases where the filter is mostly similar to a specific section of the input signal. ## Convolution matrices In fully connected layer, the weight matrix is a dense matrix and full matrix multiplication takes place. However, in convolutional layer, the weight matrix shares elements and convolution operation can be seen as block diagonal matrix multiplication. Convolution can therefore be represented as matrices $C(w)$ called circulant matrices. These are multidiagonal matrices with each elements on each diagonal having the same value. ![[circulant-matix.jpg]] [Image Credit](https://towardsdatascience.com/deriving-convolution-from-first-principles-4ff124888028) One special property of circulant matrices is that unlike normal [[Linear Algebra#Basic Matrix Algebra|matrix multiplication]] *circulant matrix multiplications commute*. i.e $\mathrm{C}(\mathrm{w}) \mathrm{C}(\mathrm{u})=\mathrm{C}(\mathrm{u}) \mathrm{C}(\mathrm{w})$ This is because convolution operation is itself commutable. ## The shift operator We apply convolutions by shifting the filters. For $w=[0,1, \ldots, 0]=C(w)$ the right-shift operator - Similar to convolution: shift once' to the right - Transpose for left-shift The shift operator is an orthogonal matrix. The shift operator is also circulant. ![[shiftoperator.jpg]] ## Circulant matrices enable Translation equivariance Circulant matrices enable translation equivariance to convolutions - Change the location of the input - The results will be the same (but shifted) Ex: gaussian filter with right shift ![[translation-eq-ciculant-matrices.jpg]] ## All circulant matrices have the same eigenvectors The eigen values of the circulant matrices are different. But the [[Linear Algebra#Eigenvectors|eigenvectors]] are always the same! The eigenvectors of the "translation transformation/operator". The $k$ -th eigenvector of $n \times n$ circulant $e^{(k)}=\left[\begin{array}{c}\omega_{n}^{0 \cdot k} \\ \omega_{n}^{1 \cdot k} \\ \omega_{n}^{2 \cdot k} \\ \vdots \\ \omega_{n}^{(n-1) \cdot k}\end{array}\right],$ where $\omega_{\mathrm{n}}=\exp \left(\frac{2 \pi \cdot i}{n}\right)$ Collecting all eigenvectors $ \Phi=\left[\begin{array}{lllll} e^{(0)} & e^{(1)} & e^{(2)} & \cdots & \left.e^{(n-1)}\right] \end{array}\right. $ This looks a lot like [[Discrete Fourier Transform]]. Which means convolution is very similar to DFT: ![[Convolution-to-dft.png]] If we can compute (inverse) Fouriers and their inverse fast, then we are game. Fast Fourier Transform (FFT): A faster version of DFT $O(n \log n)$ vs $O\left(n^{2}\right)$. It replaces sliding window convolutions with very fast matrix multiplications. ![[dft-conv.png]] --- ## References 1. Lecture 7.3, UvA Deep Learning course 2020 2. Circulant matrices and convolution intuition https://towardsdatascience.com/deriving-convolution-from-first-principles-4ff124888028