LITMIR.BIZ

      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

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