The Sparse Fourier Transform. Haitham Hassanieh

∉ I′ have and |x̂i| ≤ 4E with probability 1 − 1/n², with total probability 1 − 2/n² we have

      Rescaling ∊ and δ gives our theorem. ■

       3.2.3 Extension

      In this section, we present an extension of the SFT 1.0 algorithm which adds a heuristic to improve the runtime. We refer to this new algorithm as SFT 2.0 and it is shown in Algorithm 3.2. The idea of the heuristic is to apply the aliasing filter to restrict the locations of the large coefficients. The algorithm is parameterized by M that divides n. It performs the aliasing filter as a preprocessing step to SFT 1.0 and uses its output to restrict the frequency locations in the set Ir outputted by the location loops, as shown in Algorithm 3.2.

      Observe that . Thus,

      This means that the filter is very efficient, in that it has no leakage at all. Also, it is simple to compute. Unfortunately, it cannot be “randomized” using P_{σ, τ, b}: after permuting by σ and b, any two colliding elements j and j′ (i.e., such that j = j′ mod M) continue to collide. Nevertheless, if x̂j is large, then j mod M is likely to lie in T—at least heuristically on random input.

      SFT 2.0 assumes that all “large” coefficients j have j mod M in T. That is, we restrict our sets Ir to contain only coordinates i with i mod M ∈ T. We expect that rather than the previous dkn/B. This means that our heuristic will improve the runtime of the inner loops from O(B log(n/δ) + dkn/B) to , at the cost of O(M log M) preprocessing.

      Algorithm 3.2 SFT 2.0: Non-iterative Sparse Fourier Transform with heuristic for

      Note that on worst case input, SFT 2.0 may give incorrect output with high probability. For example, if xi = 1 when i is a multiple of n/M and 0 otherwise, then y = 0 with probability 1 − M/n and the algorithm will output 0 over supp(x). However, in practice the algorithm works for “sufficiently random” x.

      Claim 3.1 As a heuristic approximation, SFT 2.0 runs in O((k²n log(n/δ)/∊)^1/3 log n) as long as k ≤ ∊²n log(n/δ).

      Justification. First we will show that the heuristic improves the inner loop running time to , then we will optimize the parameters M and B.

      Heuristically, one would expect each of the Ir to be a factor smaller than if we did not require the elements to lie in T modulo M. Hence, we expect each of the Ir and I′ to have size . Then in each location loop, rather than spending O(dkn/B) time to list our output, we spend time—plus the time required to figure out where to start listing coordinates from each of the dk chosen elements J of ẑ. We do this by sorting J and {σi | i ∈ T} (mod M), then scanning through the elements. It takes O(M + dk) time to sort O(dk) elements in [M], so the total runtime of each location loop is . The estimation loops are even faster, since they benefit from |I′| being smaller but avoid the M + dk penalty.

      The full algorithm does O(M log M) preprocessing and runs the inner loop L = O(log n) times with d = O(1/∊). Therefore, given parameters B and M, the algorithm takes time. Optimizing over B, we take

      time. Then, optimizing over M, this becomes

      time. If k < ∊²n log(n/δ), the first term dominates.

      Note that this is an factor smaller than the running time of SFT 1.0.

      1. This fact was implicit in Cormode and Muthukrishnan [2006]. For an explicit statement and proof see Gilbert and Indyk [2010, remarks after Theorem 2].

      2. Throughout this book, we will use the terms “Binning” and “Bucketization” interchangeably.

      3. One can randomize the positions of the frequencies by sampling the signal in time domain appropriately as we showed in Section 2.2.2.

      4. The Dirichlet kernel is the discrete version of the sinc function.

      5. A more efficient filter can be obtained by replacing the Gaussian function with a Dolph-Chebyshev function. (See Figure 2.1 for an illustration.)

      6. Although it is plausible that one could combine our filters with the binary search technique of Gilbert et al. [2005a] and achieve an algorithm with a O(k log^c n) runtime, our preliminary analysis indicates that the resulting algorithm would be slower. Intuitively, observe that for n = 2²² and k = 2¹¹, the values of and k log₂ n = 45056 are quite close to each other.

      7. Note that B is chosen in order to minimize the running time. For the purpose of correctness, it suffices that B ≥ ck/∊ for some constant c.

       4

       Optimizing Runtime Complexity

       4.1 Introduction

      The algorithm presented in Chapter 3 was the first algorithm to outperform FFT in practice for reasonably sparse signals. However, it has a runtime of

      ,

      which is polynomial in n and only outperforms FFT for k smaller than Θ(n/ log n).

       4.1.1 Results

      In this chapter, we address this limitation by presenting