The Sparse Fourier Transform. Haitham Hassanieh

B more carefully to obtain the desired running time. The cost of each iterative step is multiplied by the number of filtering steps needed to compute the location of the coefficients, which is Θ(log(n/B)).If we set B = Θ(k′), this would be Θ(log n) in most iterations, giving a Θ(k log² n) running time. This is too slow when k is close to n. We avoid this by decreasing B more slowly and k′ more quickly. In the r-th iteration, we set B = k/ poly(r). This allows the total number of bins to remain O(k) while keeping log(n/B) small—at most O(log log k) more than log (n/k). Then, by having k′ decrease according to k′ = k/r^Θ(r) rather than k/2^Θ(r), we decrease the number of rounds to O(log k/ log log k). Some careful analysis shows that this counteracts the log log k loss in the log (n/B) term, achieving the desired O(k log n log(n/k)) running time.

       4.2 Algorithm for the Exactly Sparse Case

      In this section, we assume x̂_i ∈ {−L, …, L} for some precision parameter L. To simplify the bounds, we assume L ≤ nc for some constant c > 0; otherwise the log n term in the running time bound is replaced by log L. We also assume that x̂ is exactly k-sparse. We will use the filter G with parameter δ = 1/(4n2L).

      Definition 4.1 We say that is a flat window function with parameters B > 1, δ > 0, and α > 0 if and satisfies

      • = 1 for |i| ≤ (1 − α)n/(2B) and = 0 for |i| ≤ n/(2B),

      • ∈ [0,1] for all i, and

      • .

      The above notion corresponds to the (1/(2B), (1 − α)/(2B), δ, O(B/α log(n/δ))-flat window function. In Appendix D, we give efficient constructions of such window functions, where G can be computed in time and for each i, can be computed in O(log(n/δ)) time. Of course, for i ∉ [(1 − α)n/(2B), n/(2B)], ∈ {0,1} can be computed in O(1) time. The fact that takes ω(1) time to compute for i ∈ [(1 − α)n/(2B), n/(2B)] will add some complexity to our algorithm and analysis. We will need to ensure that we rarely need to compute such values. A practical implementation might find it more convenient to precompute the window functions in a preprocessing stage, rather than compute them on the fly.

      The algorithm NOISELESSSPARSEFFT (SFT 3.0) is described as Algorithm 4.1. The algorithm has three functions:

      • HASHTOBINS. This permutes the spectrum of with Pσ,a,b, then “hashes” to B bins. The guarantee will be described in Lemma 4.1.

      • NOISELESSSPARSEFFTINNER. Given time-domain access to x and a sparse vector ẑ such that is k′-sparse, this function finds “most” of .

      • NOISELESSSPARSEFFT. This iterates NOISELESSSPARSEFFTINNER until it finds x̂ exactly.

      Algorithm 4.1 SFT 3.0: Exact Sparse Fourier Transform for k = o(n)

      We analyze the algorithm “bottom-up,” starting from the lower-level procedures.

      Analysis of NOISELESSSPARSEFFTINNER and HASHTOBINS

      For any execution of NOISELESSSPARSEFFTINNER, define the support S = supp(x̂ − ẑ). Recall that πσ,b(i) = σ(i − b) mod n. Define hσ,b(i) = round(πσ,b(i)B/n) and . Note that therefore |oσ,b(i)| ≤ n/(2B). We will refer to hσ,b(i) as the “bin” that the frequency i is mapped into, and oσ,b(i) as the “offset.” For any i ∈ S define two types of events associated with i and S and defined over the probability space induced by σ and b:

      • “Collision” event E_coll(i): holds iff hσ,b(i) ∈ hσ,b(S\ {i}), and

      • “Large offset” event E_off (i): holds iff |oσ,b(i)| ≥ (1 − α)n/(2B).

      Claim 4.1 For any i ∈ S, the event E_coll(i) holds with probability at most 4|S|/B.

      Proof Consider distinct i, j ∈ S. By Lemma 2.1,

      By a union bound over j ∈ S, Pr[E_coll(i)] ≤ 4 |S| /B.

      Claim 4.2 For any i ∈ S, the event E_off (i) holds with probability at most α.

      Proof Note that oσ,b(i) ≡ πσ,b(i) ≡ σ(i − b) (mod n/B). For any odd σ and any l ∈ [n/B], we have that Pr_b[σ(i − b) ≡ l (mod n/B)]= B/n. Since only αn/B offsets oσ,b(i) cause E_off (i), the claim follows.

      Lemma 4.1 Suppose B divides n. The output û of HASHTOBINS satisfies

      Let The running time of HASHTOBINS is

      Proof The proof can be found in Appendix A.3.

      Lemma 4.2 Consider any i ∈ S such that neither E_coll(i) nor E_off(i) holds. Let j = hσ,b(i). Then

      and j ∈ J.

      Proof