Abstract: The nonuniform FFT arises in a variety of applications, from medical imaging to radio astronomy to the numerical solution of partial differential equations. In a typical problem, one is given an irregular sampling of N data points in the frequency domain with the goal of reconstructing the corresponding function at N points in the physical domain. When the sampling is uniform, the fast Fourier transform (FFT) allows this calculation to be carried out in O(N\log N) operations. Unfortunately, when the data is nonuniform, the FFT does notapply. In the last few years, a number of algorithms have been developed which overcome this limitation and are often referred to as nonuniform FFTs. In this talk, we describe the basic algorithm and its application to magnetic resonance imaging.
This talk will be accessible to graduate students.