The Sparse Fourier Transform. Haitham Hassanieh

the mass from non-heavy coordinates lies in the same bin. For such a “well-hashed” coordinate i, we would like to find its location τ = πσ,b(i) = σ(i − b) among the ∈n/k < n/k consecutive values that hash to the same bin. Let

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

      so . In the noiseless case, we showed that the difference in phase in the bin using Pσ,0,b and using Pσ,1,b is plus a negligible O(δ) term. With noise this may not be true; however, we can say for any β ∈ [n] that the difference in phase between using Pσ,a,b and Pσ,α+βb, as a distribution over uniformly random α ∈ [n], is with (for example) E[ν²] = 1/100 (all operations on phases modulo 2π). We can only hope to get a constant number of bits from such a “measurement.” So our task is to find τ within a region Q of size n/k using O(log(n/k)) “measurements” of this form.

      One method for doing so would be to simply do measurements with random β ∈ [n]. Then each measurement lies within π/4 of with at least probability. On the other hand, for j ≠ τ and as a distribution over β, is roughly uniformly distributed around the circle. As a result, each measurement is probably more than π/4 away from . Hence, O(log(n/k)) repetitions suffice to distinguish among the n/k possibilities for τ. However, while the number of measurements is small, it is not clear how to decode in polylog rather than Ω.(n/k) time.

      To solve this, we instead do a t-ary search on the location for t = Θ(log n). At each of O(log_t(n/k)) levels, we split our current candidate region Q into t consecutive subregions Q1, …, Qt, each of size w. Now, rather than choosing β ∈ [n], we choose . By the upper bound on β, for each q ∈ [t] the values { | j ∈ Qq} all lie within of each other on the circle. On the other hand, if |j − τ| > 16w, then will still be roughly uniformly distributed about the circle. As a result, we can check a single candidate element eq from each subregion: if eq is in the same subregion as τ, each measurement usually agrees in phase; but if eq is more than 16 subregions away, each measurement usually disagrees in phase. Hence with O(log t) measurements, we can locate τ to within O(1) consecutive subregions with failure probability 1/t^Θ(1). The decoding time is O(t log t).

      This primitive LOCATEINNER lets us narrow down the candidate region for τ to a subregion that is a t′ = Ω(t) factor smaller. By repeating LOCATEINNER times, LOCATESIGNAL can find τ precisely. The number of measurements is then O(log t log_t(n/k)) = O(log(n/k)) and the decoding time is O(t log t log_t(n/k)) = O(log(n/k) log n). Furthermore, the “measurements” (which are actually calls to HASHTOBINS) are non-adaptive, so we can perform them in parallel for all O(k/∈) bins, with O(log(n/δ)) average time per measurement. This gives O(k log(n/k) · log(n/δ)) total time for LOCATESIGNAL.

      This lets us locate every heavy and “well-hashed” coordinate with 1/t^Θ(1) = o(1) failure probability, so every heavy coordinate is located with arbitrarily high constant probability.

       Estimation

      By contrast, estimation is fairly simple. As in Algorithm 4.1, we can estimate as , where û is the output of HASHTOBINS. Unlike in Algorithm 4.1, we now have noise that may cause a single such estimate to be poor even if i is “well-hashed.” However, we can show that for a random permutation Pσ,a,b the estimate is “good” with constant probability. ESTIMATEVALUES takes the median of Rest = O(log ) such samples, getting a good estimate with 1 − ∊/64 probability. Given a candidate set L of size k/∈, with 7/8 probability at most k/8 of the coordinates are badly estimated. On the other hand, with 7/8 probability, at least 7k/8 of the heavy coordinates are both located and well estimated. This suffices to show that, with 3/4 probability, the largest k elements J of our estimate ŵ contains good estimates of 3k/4 large coordinates, so is close to k/4-sparse.

       4.3.2 Analysis

       Formal Definitions

      As in the noiseless case, we define πσ,b(i) = σ(i − b) mod n, hσ,b(i) = round πσ,b(i)B/n), and oσ,b(i) = πσ,b(i) − hσ,b(i)n/B. We say hσ,b(i) is the “bin” that frequency i is mapped into, and oσ,b(i) is the “offset.” We define

      Define

      In each iteration of SPARSEFFT, define x̂′ = x̂ − ẑ, and let

      Then and . We will show that each i ∈ S is found by LOCATESIGNAL with probability , when .

      For any i ∈ S define three 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 ;

      • “Large offset” event E_off(i): holds iff