The Sparse Fourier Transform. Haitham Hassanieh

Скачать книгу

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 for all i ∈ I′. Since all i ∉ 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

Скачать книгу