The Sparse Fourier Transform. Haitham Hassanieh

let P be the set of all pairs (i, v) for which the command ŵi ← v was executed. Claims 4.1 and 4.2 and Lemma 4.2 together guarantee that for each i ∈ S the probability that P does not contain the pair (i, (x̂ − ẑ)_i) is at most 4|S|/B + α. We complement this observation with the following claim.

      Claim 4.3 For any j ∈ J we have j ∈ hσ,b(S). Therefore, |J| = |P| ≤ |S|.

      Proof Consider any j ∉ hσ,b(S). From Equation (A.1) in the proof of Lemma 4.2 it follows that |ûj| ≤ δnL < 1/2.

      Lemma 4.3 Consider an execution of NOISELESSSPARSEFFTINNER, and let S = supp(x̂ − ẑ).If |S| ≤ k′, then

      Proof Let e denote the number of coordinates i ∈ S for which either E_coll(i) or E_off (i) holds. Each such coordinate might not appear in P with the correct value, leading to an incorrect value of ŵi. In fact, it might result in an arbitrary pair (i′, v′) being added to P, which in turn could lead to an incorrect value of . By Claim 4.3 these are the only ways that ŵ can be assigned an incorrect value. Thus, we have

      Since E[e] ≤ (4|S|/B + α)|S| ≤ (4β + α)|S|, the lemma follows.

      Analysis of NOISELESSSPARSEFFT

      Consider the tth iteration of the procedure, and define St = supp(x̂ − ẑ) where ẑ denotes the value of the variable at the beginning of loop. Note that |S₀| = |supp(x̂)| ≤ k.

      We also define an indicator variable It which is equal to 0 iff |St|/|S_t−1| ≤ 1/8. If It = 1 we say the tth iteration was not successful. Let γ = 8 · 8(β + α). From Lemma 4.3 it follows that . From Claim 4.3 it follows that even if the tth iteration is not successful, then |St|/|S_t−1| ≤ 2.

      For any t ≤ 1, define an event E(t) that occurs iff . Observe that if none of the events E(1) … E(t) holds then |St| ≤ k/2^t.

      Lemma 4.4 Let E = E(1) ∪ … ∪ E (λ) for λ = 1 + log k. Assume that (4γ)^1\2 < 1/4. Then Pr[E] ≤ 1/3.

      Proof Let t′ = [t/2]. We have

      Therefore,

      Theorem 4.1 Suppose x̂ is k-sparse with entries from {−L, …, L} for some known L = n^O(1). Then the algorithm NOISELESSSPARSEFFT runs in expected O(k log n) time and returns the correct vector x̂ with probability at least 2/3.

      Proof The correctness follows from Lemma 4.4. The running time is dominated by O(log k) executions of HASHTOBINS.

      Assuming a correct run, in every round t we have

      Therefore,

      so the expected running time of each execution of HASHTOBINS is . Setting α = Θ(2^−t/2) and β = Θ(1), the expected running time in round t is . Therefore the total expected running time is O(k log n). ■

4.3 Algorithm for the General Case

      For the general case, we only achieve Equation (4.1) for . In general, for any parameter δ > 0 we can add to the right hand side of Equation (4.1) and run in time O(k log(n/k) log(n/δ)).

      Pseudocode for the general algorithm SFT 4.0 is shown in Algorithms 4.2 and 4.3.

       4.3.1 Intuition

      Let S denote the “heavy” O(k/∊) coordinates of x̂. The overarching algorithm SPARSEFFT (SFT 4.0) works by first “locating” a set L containing most of S, then “estimating” x̂L to get ẑ. It then repeats on . We will show that each heavy coordinate has a large constant probability of both being in L and being estimated well. As a result, is probably nearly k/4-sparse, so we can run the next iteration with k → k/4. The later iterations then run faster and achieve a higher success probability, so the total running time is dominated by the time in the first iteration and the total error probability is bounded by a constant.

      Algorithm 4.2 SFT 4.0: General Sparse Fourier Transform for k = o(n), part 1 of 2

      In the rest of this intuition, we will discuss the first iteration of SPARSEFFT with simplified constants. In this iteration, hashes are to B = O(k/∈) bins and, with 3/4 probability, we get ẑ so is nearly k/4-sparse. The actual algorithm will involve a parameter α in each iteration, roughly guaranteeing that with 1 − probability, we get ẑ so is nearly k-sparse; the formal guarantee will be given by Lemma 4.11. For this intuition we only consider the first iteration where α is a constant.

       Location

      As in the noiseless case, to locate the “heavy” coordinates we consider the “bins” computed by HASHTOBINS with Pσ,a,b. This roughly corresponds to first permuting the coordinates according to the (almost) pairwise independent permutation Pσ,a,b, partitioning the coordinates into B = O(k/∊) “bins” of n/B consecutive indices, and observing the sum of values in each bin. We get that each heavy coordinate i has a large constant probability