The Sparse Fourier Transform. Haitham Hassanieh

      Note that on worst case input, SFT 2.0 may give incorrect output with high probability. For example, if xi = 1 when i is a multiple of n/M and 0 otherwise, then y = 0 with probability 1 − M/n and the algorithm will output 0 over supp(x). However, in practice the algorithm works for “sufficiently random” x.

      Claim 3.1 As a heuristic approximation, SFT 2.0 runs in O((k²n log(n/δ)/∊)^1/3 log n) as long as k ≤ ∊²n log(n/δ).

      Justification. First we will show that the heuristic improves the inner loop running time to , then we will optimize the parameters M and B.

      Heuristically, one would expect each of the Ir to be a factor smaller than if we did not require the elements to lie in T modulo M. Hence, we expect each of the Ir and I′ to have size . Then in each location loop, rather than spending O(dkn/B) time to list our output, we spend time—plus the time required to figure out where to start listing coordinates from each of the dk chosen elements J of ẑ. We do this by sorting J and {σi | i ∈ T} (mod M), then scanning through the elements. It takes O(M + dk) time to sort O(dk) elements in [M], so the total runtime of each location loop is . The estimation loops are even faster, since they benefit from |I′| being smaller but avoid the M + dk penalty.

      The full algorithm does O(M log M) preprocessing and runs the inner loop L = O(log n) times with d = O(1/∊). Therefore, given parameters B and M, the algorithm takes time. Optimizing over B, we take

      time. Then, optimizing over M, this becomes

      time. If k < ∊²n log(n/δ), the first term dominates.

      Note that this is an factor smaller than the running time of SFT 1.0.

      1. This fact was implicit in Cormode and Muthukrishnan [2006]. For an explicit statement and proof see Gilbert and Indyk [2010, remarks after Theorem 2].

      2. Throughout this book, we will use the terms “Binning” and “Bucketization” interchangeably.

      3. One can randomize the positions of the frequencies by sampling the signal in time domain appropriately as we showed in Section 2.2.2.

      4. The Dirichlet kernel is the discrete version of the sinc function.

      5. A more efficient filter can be obtained by replacing the Gaussian function with a Dolph-Chebyshev function. (See Figure 2.1 for an illustration.)

      6. Although it is plausible that one could combine our filters with the binary search technique of Gilbert et al. [2005a] and achieve an algorithm with a O(k log^c n) runtime, our preliminary analysis indicates that the resulting algorithm would be slower. Intuitively, observe that for n = 2²² and k = 2¹¹, the values of and k log₂ n = 45056 are quite close to each other.

      7. Note that B is chosen in order to minimize the running time. For the purpose of correctness, it suffices that B ≥ ck/∊ for some constant c.

       4

       Optimizing Runtime Complexity

       4.1 Introduction

      The algorithm presented in Chapter 3 was the first algorithm to outperform FFT in practice for reasonably sparse signals. However, it has a runtime of

      ,

      which is polynomial in n and only outperforms FFT for k smaller than Θ(n/ log n).

       4.1.1 Results

      In this chapter, we address this limitation by presenting two new algorithms for the Sparse Fourier Transform. We show

      • an O(k log n)-time algorithm for the exactly k-sparse case, and

      • an O(k log n log(n/k))-time algorithm for the general case.

      The key property of both algorithms is their ability to achieve o(n log n) time, and thus improve over the FFT, for any k = o(n). These algorithms are the first known algorithms that satisfy this property. Moreover, if one assumes that FFT is optimal and hence the DFT cannot be computed in less than O(n log n) time, the algorithm for the exactly k-sparse case is optimal¹ as long as k = n^Ω(1). Under the same assumption, the result for the general case is at most one log log n factor away from the optimal runtime for the case of “large” sparsity .

      For the general case, given a signal x, the algorithm computes a k-sparse approximation of its Fourier transform, x̂ that satisfies the following guarantee:

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