This lesson shows you how to view the fast Fourier transform algorithm as a factorization of the discrete Fourier transform matrix into a product of matrices. The matrices in the product representation are very sparse which is why the fast Fourier transform algorithm is computationally efficient. As you see here, matrix factorization is a very useful and insightful tool in signal processing.
Learn signal processing online
