Estamos realizando la búsqueda. Por favor, espere...


A nonuniform fast fourier transform based on low rank approximation

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.

Otras publicaciones de la misma revista o congreso con autores/as de la Universidad de Cantabria

 Fuente: SIAM Journal on Scientific Computing 40(1), A529-A547

Editorial: Society for Industrial and Applied Mathematics

 Año de publicación: 2018

Nº de páginas: 17

Tipo de publicación: Artículo de Revista

 DOI: 10.1137/17M1134822

ISSN: 1064-8275,1095-7197

Proyecto español: MTM2012-34787