fft-from-scratch

This is a Python implementation of Fast Fourier Transform (FFT) in 1d and 2d from scratch and some of its applications in:

• Photo restoration (paper texture pattern removal)
• convolution (direct fft and overlap add fft method, including a comparison with the direct matrix multiplication method and ground truth using scipy.signal.convolve. It also includes a speed and accuracy comparison with torch.nn.Conv2d)
• large integer multiplication.

Photo restoration

The honeycomb pattern on old photos is due to the "silk finish" paper texture, which was used a lot back in the day. We can remove them in frequency domain using fft.

view on larger screen, small screen will show aliasing effect. We can use a low pass filter later.

Convolution

achieves O(nlogn) complexity, whereas a direct matrix multiplication approach is O(n^2). It is more efficient when n is large.

large integer multiplication

inspired from the multiplication of polynomials in chap.30 of Introduction to algorithms book.