Mathematics, Computation and Geometry of Data

Volume 1 (2021)

Number 1

Multiscale high-dimensional sparse Fourier algorithms for noisy data

Pages: 35 – 58

DOI: https://dx.doi.org/10.4310/MCGD.2021.v1.n1.a2

Authors

Bosu Choi (Oden Institute for Computational Engineering and Sciences, University of Texas, Austin, Tx., U.S.A.)

Andrew Christlieb (Department of Computational Mathematics, Science & Engineering, Michigan State University, East Lansing, Mich., U.S.A.)

Yang Wang (Department of Mathematics, Hong Kong University of Science and Technology, Hong Kong)

Abstract

We develop an efficient and robust high-dimensional sparse Fourier algorithm for noisy samples. Earlier in the paper “High-dimensional sublinear sparse Fourier algorithms” (2016) [3], an efficient sparse Fourier algorithm with $\Theta (ds \operatorname{log} s)$ average-case runtime and $\Theta (ds)$ sampling complexity under certain assumptions was developed for signals that are $s$‑sparse and bandlimited in the $d$‑dimensional Fourier domain, i.e. there are at most s energetic frequencies and they are in $[- N/2 , N/2)^d \cap \mathbb{Z}^d$. However, in practice the measurements of signals often contain noise, and in some cases may only be nearly sparse in the sense that they are well approximated by the best $s$ Fourier modes. In this paper, we propose a multiscale sparse Fourier algorithm for noisy samples that proves to be both robust against noise and efficient.

Keywords

higher dimensional sparse FFT, fast Fourier algorithms, Fourier analysis, multiscale algorithms

2010 Mathematics Subject Classification

Primary 65T50. Secondary 68W25.

Received 17 July 2019

Published 15 July 2022