A Nonuniform Fast Fourier Transform Based on Low Rank Approximation
Ver/ Abrir
Identificadores
URI: http://hdl.handle.net/10902/13767DOI: 10.1137/17M1134822
ISSN: 1064-8275
ISSN: 1095-7197
Registro completo
Mostrar el registro completo DCFecha
2018Derechos
© Society for Industrial and Applied Mathematics
Publicado en
SIAM Journal on Scientific Computing Volume 40, Issue 1, pp. A1-C155
Editorial
Society for Industrial and Applied Mathematics
Resumen/Abstract
By viewing the nonuniform discrete Fourier transform (NUDFT) as a perturbed version of a uniform discrete Fourier transform, we propose a fast and quasi-optimal algorithm for computing the NUDFT based on the fast Fourier transform (FFT). Our key observation is that an NUDFT and DFT matrix divided entry by entry is often well approximated by a low rank matrix, allowing us to express a NUDFT matrix as a sum of diagonally scaled DFT matrices. Our algorithm is simple to implement, automatically adapts to any working precision, and is competitive with state-of-the-art algorithms. In the fully uniform case, our algorithm is essentially the FFT. We also describe quasi-optimal algorithms for the inverse NUDFT and two-dimensional NUDFTs.
Colecciones a las que pertenece
- D20 Artículos [412]
- D20 Proyectos de Investigación [277]