Convolution and FFT Flashcards

1
Q

How can we do 1d circular concolution using matricies

A

We create the circulant matrix where the rows are shifted versions of x.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Prove that the product of circulant matricies is circulant

A

Let * denote convolution

C(xy)z = xyz = xC(y)z = C(x)C(y)z

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a shift matrix?

A

The identity matrix with elements shifted.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the connection between shift and circulant matricies?

A

A is circulant iff. it comutes with the shift matrix:

AS = SA

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Is convolution shift invariant?

A

No its shift equivariant

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Prove that Convolution is shift equivariant

A

(Sx) * y = y * (Sx) = C(y)Sx = SC(y)x = S(x*y)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

When are two matricies jointly diagonaziable? (Diagonaizable by the same eigenvectors)

A

Iff they commute

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Prove that the eigenvalues for a Shift matrix are the roots of unity

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the eigenvectors of the Shift matrix?

A

phi_i = [1, exp(2pii/n), exp(2pi2i)/n…., exp(2pi(n-1)i)/(n)]

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are the orthonormal, unit lenght, eigenvectors from the shift matrix called?

A

The fourier basis

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the FFT?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How do we perform convolution in the foruier domain?

A

F(y) = V^Ty, F(x) = V^Tx
x * y = V(x @ y)
Where @ denotes the elemntwise multiplication (Hadamard product)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How can vi think about the edge cases in a circular 2d convolution?

A

Wrap the 2d image as a torus.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How can we shift a 2d, NxN, matrix?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define shift invariance using shift matricies

A

f(x) = f(Sx) where S is the shift matrix

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Define shift equivariance using shift matricies

A

Sf(x) = f(Sx) where S is the shift matrix

17
Q

How can we make convolution networks approximatly shift invariant?

A

Convolution followed by MaxPooling