The Sparse Fourier Transform. Haitham Hassanieh
Читать онлайн книгу.
∉ I′ 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
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 M ∈ T. We expect that
Algorithm 3.2 SFT 2.0: Non-iterative Sparse Fourier Transform with heuristic for
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 k ≤ ∊2n log(n/δ).
Justification. First we will show that the heuristic improves the inner loop running time to
Heuristically, one would expect each of the Ir to be a
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. Then, optimizing over M, this becomes
time. If k < ∊2n log(n/δ), the first term dominates.
Note that this is an
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
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