Is 2D FFT separable?

Question

Suppose I have a 2D matrix (or image). Can I loop on the columns - compute the FFT of each column and then loop on the rows (of the result matrix) and compute the FFT of that? Would that be equivalent to compute the FFT of the original image?

I tried to prove it, but I'm not sure if my proof is flawed or not. Suppose X is the FFT of x:

$$X[k,l] = \sum_n\sum_m x[n,m]e^{-j2\pi kn/N}e^{-j2\pi ln/N} =\sum_n\left\{\sum_m x[n,m]e^{-j2\pi ln/N}\right\}e^{-j2\pi kn/N} =\sum_n X[n,l]e^{-j2\pi kn/N} = 1DimFFT_k(1DimFFT_l(x)) $$

Can you please tell me if I'm correct, or did I get something wrong?

Thanks in advance,

Gil

Answer 1

Yes you can do that, it is common practice to do so and there can be many speed ups in doing so.