746-747 / 2239
Convolution theorem
The convolution theorem states that the Fourier of a convolution is the point wise product
of Fourier transforms.
Pointwise multiplication
denotes Fourier transform operator
or
Applying the inverse Fourier transform,
Standard (discrete) Fourier convolution for N points has a complexity of: 2 N
2
e.g . For a 256 x 256 matrix, calculation time is proportional to 2 x 65 536