Convolution and FFT Flashcards
How can we do 1d circular concolution using matricies
We create the circulant matrix where the rows are shifted versions of x.
Prove that the product of circulant matricies is circulant
Let * denote convolution
C(xy)z = xyz = xC(y)z = C(x)C(y)z
What is a shift matrix?
The identity matrix with elements shifted.
What is the connection between shift and circulant matricies?
A is circulant iff. it comutes with the shift matrix:
AS = SA
Is convolution shift invariant?
No its shift equivariant
Prove that Convolution is shift equivariant
(Sx) * y = y * (Sx) = C(y)Sx = SC(y)x = S(x*y)
When are two matricies jointly diagonaziable? (Diagonaizable by the same eigenvectors)
Iff they commute
Prove that the eigenvalues for a Shift matrix are the roots of unity
Let S be a nxn shift matrix, y be a eigenvalue, v be the corresponding eigenvector and * denote matrix/vector multiplication
S^{k}*v = y^{k}*v so v_{i+k} = y^{k}v_i
S^{n}*v = S*v so v_{i+n} = v_i
v_i = S^{n}v_i = y^{n}v_i
so y^{n} = 1
y = sqrt(i2pi/n)
What are the eigenvectors of the Shift matrix?
phi_i = [1, exp(2pii/n), exp(2pi2i)/n…., exp(2pi(n-1)i)/(n)]
What are the orthonormal, unit lenght, eigenvectors from the shift matrix called?
The fourier basis
What is the FFT?
Instead of taking the Fourier transform of a whole vector, we can do the fourier transform of the even/ odd indicies and combine them afterwards to get the transform.
How do we perform convolution in the foruier domain?
F(y) = V^Ty, F(x) = V^Tx
x * y = V(x @ y)
Where @ denotes the elemntwise multiplication (Hadamard product)
How can vi think about the edge cases in a circular 2d convolution?
Wrap the 2d image as a torus.
How can we shift a 2d, NxN, matrix?
Stack the columns in the 2d matrix to a column vector. Create your shift matrix as usual with respect to vertical shifts. Use this matrix as blocks and create a 2d matrix with NxN of these blocks, that is a 2d shift matrix.
Define shift invariance using shift matricies
f(x) = f(Sx) where S is the shift matrix
