A SVD-Based Algorithm for Dense Nonuniform Fast Fourier Transform

This work introduces a fast algorithm based on Singular Value Decomposition to compute the Nonuniform Fourier Transform. This approach is compared to proven techniques like the ones based on interpolation and least square approximation. Nonuniform Fourier exponentials are approximated through a set of optimum spaces obtained by modulating a single space. For a fixed precision, the space dimension is smaller with respect to the previous approaches, resulting in a computational cost reduction. Furthermore, the proposed formulation involves only real-complex multiplications rather than complex-complex ones. As a counterpart, the amount of projections to be computed is higher with respect to proven approaches. So, the proposed algorithm results to be optimum for dense nonuniformly sampled frequencies.