A deterministic sparse FFT for functions with structured Fourier sparsity
- PDF / 1,160,953 Bytes
- 43 Pages / 439.642 x 666.49 pts Page_size
- 22 Downloads / 202 Views
A deterministic sparse FFT for functions with structured Fourier sparsity Sina Bittens1
· Ruochuan Zhang2 · Mark A. Iwen3
Received: 21 November 2017 / Accepted: 20 July 2018 / © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract In this paper, a deterministic sparse Fourier transform algorithm is presented which breaks the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting structured frequency support. These functions include, e.g., the often considered set of block frequency sparse functions of the form f (x) =
n B−1 j =1 k=0
N N cωj +k ei(ωj +k)x , {ω1 , . . . , ωn } ⊂ − , ∩Z 2 2
as a simple subclass. Theoretical error bounds in combination with numerical experiments demonstrate that the newly proposed algorithms are both fast and robust to noise. In particular, they outperform standard sparse Fourier transforms in the rapid recovery of block frequency sparse functions of the type above. Keywords Sparse Fourier transform (SFT) · Structured sparsity · Deterministic constructions · Approximation algorithms
Communicated by: Yang Wang Sina Bittens
[email protected] Ruochuan Zhang [email protected] Mark A. Iwen [email protected] 1
Institute for Numerical and Applied Mathematics, University of G¨ottingen, Lotzestr. 16-18, 37083 G¨ottingen, Germany
2
Department of Mathematics, Michigan State University, East Lansing, MI, 48824, USA
3
Department of Mathematics, and Department of Computational Mathematics, Science, and Engineering (CMSE), Michigan State University, East Lansing, MI, 48824, USA
S. Bittens et al.
Mathematics Subject Classification (2010) 05-04 · 42A10 · 42A15 · 42A16 · 42A32 · 65T40 · 65T50 · 68W25 · 94A12
1 Introduction In this paper, we consider the problem of deterministically recovering a periodic function f : [0, 2π ] → C as rapidly as absolutely possible via sampling. In particular, we focus on a specific set of functions f whose dominant Fourier series coefficients are all associated with frequencies contained in a small number, n, of unknown structured support sets S1 , . . . , Sn ⊂ (−N/2, N/2] ∩ Z, where N ∈ N is very large. In such cases, the function f will have the form f (x) ≈
n
cω eiωx ,
(1)
j =1 ω∈Sj
where each unknown Sj has simplifying structure (e.g., has |x − y| < B N for all x, y ∈ Sj ). The classical solution for this problem would be to compute the discrete Fourier transform (DFT) of N equally spaced samples from f on the interval [0, 2π ],
N−1 f 2πj , in order to obtain approximations of cω for all frequencies ω ∈ N j =0
(−N/2, N/2] ∩ Z in O(N log N)-time. Herein, we instead consider faster deterministic sparse Fourier transform (SFT) methods which are guaranteed to recover such f using na number of samples and operations that scale at most polynomially in both j =1 |Sj | and log(N). Such algorithms will always be faster than classical O(N log(N))-time methods whenever the cardinalities of the support sets, |Sj |, are sufficiently small i
Data Loading...
