{'fraction_non_alphanumeric': 0.04040404040404041, 'fraction_numerical': 0.006060606060606061, 'mean_word_length': 5.519736842105263, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Signal Approximation via the Gopher Fast Fourier Transform

We consider the problem of quickly estimating the best κ‐term Fourier representation for a given frequency‐sparse band‐limited signal (i.e., function) f: [0,2π]→¢. In essence, this requires the identification of κ of the largest magnitude frequencies of f∈¢N, and the estimation their Fourier coefficients. Randomized sublinear‐time Monte Carlo algorithms, which have a small probability of failing to output accurate answers for each input signal, have been developed for solving this problem [1, 2]. These methods were implemented as the Ann Arbor Fast Fourier Transform (AAFFT) and empirically evaluated in [3]. In this paper we present and evaluate the first implementation, called the Gopher Fast Fourier Transform (GFFT), of the more recently developed sparse Fourier transform techniques from [4]. Our experiments indicate that different variants of GFFT generally outperform AAFFT with respect to runtime and sample usage.