The Sparse Fourier Transform. Haitham Hassanieh

time. Location loops thus take time and estimation loops take time. Figure 3.1 illustrates the inner loop.

      For estimation loops, we get the following guarantee.

      Lemma 3.1 Let S be the support of the largest k coefficients of x̂, and x̂_−S contain the rest. Then for any ∊ ≤ 1,

      Proof The proof can be found in Appendix A.1. ■

      Furthermore, since is a good estimate for |x̂i|—the division is mainly useful for fixing the phase. Therefore in location loops, we get the following guarantee:

      Algorithm 3.1 SFT 1.0: Non-iterative Sparse Fourier Transform for

      Figure 3.1 Example inner loop of the algorithm on sparse input. This run has parameters n = 256, k = 4, G being the (0.11, 0.06, 2 × 10⁻⁹, 133) flat window function in Figure 2.1, and selecting the top 4 of B = 16 samples. In part (a), the algorithm begins with time domain access to P_{σ, τ, b}x given by (P_{σ, τ, b}x)i = x_σ(i−τ)ω^σbi, which permutes the spectrum of x by permuting the samples in the time domain. In part (b), the algorithm computes the time domain signal y = G · P_{σ, τ, b}x. The spectrum of y (pictured) is large around the large coordinates of P_{σ, τ, b}x. The algorithm then computes ẑ, which is the rate B subsampling of ŷ as pictured in part (c). During estimation loops, the algorithm estimates x̂i based on the value of the nearest coordinate in ẑ, namely . During location loops (part (d)), the algorithm chooses J, the top dk (here, 4) coordinates of ẑ, and selects the elements of [n] that are closest to those coordinates (the shaded region of the picture). It outputs the set I of preimages of those elements. In this example, the two coordinates on the left landed too close in the permutation and form a “hash collision.” As a result, the algorithm misses the second from the left coordinate in its output. Our guarantee is that each large coordinate has a low probability of being missed if we select the top O(k) samples.

      Lemma 3.2 Define to be the error tolerated in Lemma 3.1. Then for any i ∈ [n] with |x̂i| ≥ 4E

      Proof The proof can be found in Appendix A.2 ■

3.2.2 Non-Iterative Sparse Fourier Transform

      Our SFT 1.0 algorithm shown in Algorithm 3.1 is parameterized by ∊ and δ. It runs L = O(log n) iterations of the inner loop, with parameters and d = O(1/∊) as well as δ.⁷

      Lemma 3.3 The algorithm runs in time .

      Proof To analyze this algorithm, note that

      or |I′| ≤ 2dkn/B. Therefore, the running time of both the location and estimation inner loops is . Computing I′ and computing the medians both take linear time, namely O(Ldkn/B). Thus, the total running time is . Plugging in and d = O(1/∊), this running time is . We require B = Ω(k/∊), however; for k > ∊n/log(n/δ), this would cause the run time to be larger. But in this case, the predicted run time is Ω(n log n) already, so the standard FFT is faster and we can fall back on it. ■

      Theorem 3.1 Running the algorithm with parameters ∊, δ < 1 gives x̂′ satisfying

      with probability 1 − 1/n and running time .

      Proof Define

      Lemma 3.2 says that in each location iteration r, for any i with |x̂i| ≥ 4E,

      Thus, E[si] ≥ 3L/4, and each iteration is an independent trial, so by a Chernoff bound the chance that si < L/2 is at most 1/2^Ω(L) < 1/n³. Therefore by a union bound, with probability at least 1 − 1/n², i ∈ I′ for all i with |x̂i| ≥ 4E.

      Next, Lemma 3.1 says that for each estimation iteration r and index i,

      Therefore, with probability in at least 2L/3 of the iterations.

      Since real is the median of the real , there must exist two r with but one real above real and one below. Hence, one of these r has , and similarly for the imaginary axis. Then

      By a union bound over I′, with probability at least 1 − 1/n² we have