# Lesson 3 (Circular) Convolution

## 1D Convolution

A circulant matrix $C$ is a square matrix that's completely determined by the first column $c$. Other columns are just shifts of the first columns.

For example, the circulant matrix generated by $c=\begin{bmatrix}1\\2\\0\end{bmatrix}$ is $\qquad C=circ(c)=\begin{bmatrix}1&0&2\\2&1&0\\0&2&1\end{bmatrix}$.


```python
import numpy as np
from scipy.linalg import circulant
```


```python
circulant([1,2,0])
```




    array([[1, 0, 2],
           [2, 1, 0],
           [0, 2, 1]])



Let $c,x\in\mathcal{C}^n$. By definition, the convolution between $c$ and $x$ is 
$$c*x(i)=\sum_{j=0}^{n-1}c(i-j)x(j)=\begin{bmatrix}c_i&c_{i-1}&\cdots&c_{i-(n-1)}\end{bmatrix}\begin{bmatrix}x_0\\x_1\\\vdots\\x_{n-1}\end{bmatrix},$$
which means that
$$c*x=\begin{bmatrix}c_0&c_{0-1}&\cdots&c_{0-(n-1)}\\
c_1&c_{1-1}&\cdots&c_{1-(n-1)}\\
\vdots&\vdots&\ddots&\vdots\\
c_{n-1}&c_{n-1-1}&\cdots&c_{n-1-(n-1)}\end{bmatrix}\begin{bmatrix}x_0\\x_1\\\vdots\\x_{n-1}\end{bmatrix}=circ(c)x.$$

Let $F_n$ be the $n\times n$ unitary discrete Fourier transform, as defined in Lesson 2. One fast way to compute convolution is to use FFT. It can be proven that
\begin{equation}F_n(c)\odot F_n(x)=F_n(c*x),\end{equation}
where $\odot$ is the coordinate-wise vector product, that is $[x\odot y](i)=x(i)y(i)$.

Let $diag(x)$ be the diagonal matrix whose diagonal is $x$, then the above equation can also be written as
$$diag(F_nc)F_nx=F_ncirc(c)x\Longleftrightarrow circ(c)=F_n^*diag(F_nc)F_n\Longleftrightarrow F_n circ(c)F_n^*=diag(F_nc).$$

The code below verifies that both ways of computing convolution give the same output.


```python
x = np.random.randn(3);print(x)
```

    [-0.57732409  0.33621261  2.05435539]



```python
circulant([1,2,0])@x
```




    array([ 3.5313867 , -0.81843557,  2.72678061])




```python
np.fft.ifft(np.fft.fft([1,2,0])*np.fft.fft(x))
```




    array([ 3.5313867 +0.j, -0.81843557+0.j,  2.72678061+0.j])



## to be continued


```python

```

ccb992b75ac977194443e6f4bf8e7aca15ec7b83
ipynb
Jupyter Notebook
nb/L3Convolution.ipynb
xuemeic/Image-Processing
3038ce2fb89af2bd28d9ff034e1884a3a2830d6c
MIT
nb/L3Convolution.ipynb
xuemeic/Image-Processing
3038ce2fb89af2bd28d9ff034e1884a3a2830d6c
MIT
nb/L3Convolution.ipynb
xuemeic/Image-Processing
3038ce2fb89af2bd28d9ff034e1884a3a2830d6c
MIT
Qwen/Qwen-72B
1. YES
2. YES