Эротические рассказы

The Sparse Fourier Transform. Haitham HassaniehЧитать онлайн книгу.

The Sparse Fourier Transform - Haitham Hassanieh


Скачать книгу
I′ have image and |x̂i| ≤ 4E with probability 1 − 1/n2, with total probability 1 − 2/n2 we have

image

      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 image. Thus,

image

      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 i with i mod MT. We expect that image rather than the previous dkn/B. This means that our heuristic will improve the runtime of the inner loops from O(B log(n/δ) + dkn/B) to image, at the cost of O(M log M) preprocessing.

      Algorithm 3.2 SFT 2.0: Non-iterative Sparse Fourier Transform with heuristic for image

image

      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((k2n log(n/δ)/)1/3 log n) as long as k2n log(n/δ).

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

      Heuristically, one would expect each of the Ir to be a image 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 image. Then in each location loop, rather than spending O(dkn/B) time to list our output, we spend image 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 | iT} (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 image. 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 image time. Optimizing over B, we take

image

      time. Then, optimizing over M, this becomes

image

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

      Note that this is an image 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 logc n) runtime, our preliminary analysis indicates that the resulting algorithm would be slower. Intuitively, observe that for n = 222 and k = 211, the values of image and k log2 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 Bck/ 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

      Image,

      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


Скачать книгу
Яндекс.Метрика