href="#fb3_img_img_61b5e539-8084-5369-ab69-dd696ede105b.png" alt="image"/>
We also define πσ, b(i) = σ(i − b) mod n.
Claim 2.3
Proof
Lemma 2.1 If j ≠ 0, n is a power of two, and σ is a uniformly random odd number in [n], then Pr[σj ∊ [−C, C]] ≤ 4C/n.
Proof If j = m2l for some odd m, then the distribution of σj as σ varies is uniform over m′2l for all odd m′. There are thus 2 · round(C/2l+1) < 4C/2l+1 possible values in [−C, C] out of n/2l+1 such elements in the orbit, for a chance of at most 4C/n. ■
Note that for simplicity we will only analyze our algorithm when n is a power of two. For general n, the analog of Lemma 2.1 would lose an n/φ(n) = O(log log n) factor, where φ is Euler’s totient function. This will correspondingly increase the running time of the algorithm on general n.
Claim 2.3 allows us to change the set of coefficients binned to a bucket by changing the permutation; Lemma 2.1 bounds the probability of non-zero coefficients falling into the same bucket.
2.2.3 Subsampled FFT
Suppose we have a vector x ∈ ℂn and a parameter B dividing n, and would like to compute ŷi = x̂i(n/B) for i ∈ [B].
Claim 2.4 ŷ is the B-dimensional Fourier transform of
Proof
2.2.4 2D Aliasing Filter
The aliasing filter presented in Section 1.1.2. The filter generalizes to two dimensions as follows:
Given a 2D matrix
Then, compute the 2D DFT ŷ of y. Observe that ŷ is a folded version of x̂:
3
Simple and Practical Algorithm
3.1 Introduction
In this chapter, we propose a new sublinear Sparse Fourier Transform algorithm over the complex field. The key feature of this algorithm is its simplicity: the algorithm has a simple structure, which leads to efficient runtime with low big-Oh constant. This was the first algorithm to outperform FFT in practice for a practical range of sparsity as we will show later in Chapter 6.
3.1.1 Results
We present an algorithm which has the runtime of
where n is the size of the signal and k is the number of non-zero frequency coefficients. Thus, the algorithm is faster than FFT for k up to O(n/log n). In contrast, earlier algorithms required asymptotically smaller bounds on k. This asymptotic improvement is also reflected in empirical runtimes. For example, we show in Chapter 6 that for n = 222, this algorithm outperforms FFT for k up to about 2,200, which is an order of magnitude higher than what was achieved by prior work.
The estimations provided by our algorithm satisfy the so-called ℓ∞/ℓ2 guarantee. Specifically, let y be the minimizer of ||x̂ − y||2. For a precision parameter δ = 1/nO(1), and a constant ∊ > 0, our (randomized) algorithm outputs x̂′ such that:
with probability 1 − 1/n. The additive term that depends on δ appears in all past algorithms [Akavia 2010, Akavia et al. 2003, Gilbert et al. 2002, Gilbert et al. 2005a, Iwen 2010b, Mansour 1992], although typically (with the exception of Iwen [2010a]) it is eliminated by assuming that all coordinates are integers in the range {−nO(1) … nO(1)}. In this chapter, we keep the dependence on δ explicit.
The ℓ∞/ℓ2 guarantee of Equation (3.1) is stronger than the ℓ2/ℓ2 guarantee of Equation (1.2). In particular, the ℓ∞/ℓ2 guarantee with a constant approximation factor C implies the ℓ2/ℓ2 guarantee with a constant approximation factor C′, if one sets all but the k largest entries in x̂′ to 0.1 Furthermore, instead of bounding only the collective error, the ℓ∞/ℓ2 guarantee ensures that every Fourier coefficient is well approximated.
3.1.2 Techniques
Recall from Chapter 1 that the Sparse Fourier Transform algorithms work by binning2 the Fourier coefficients into a small number of buckets. Since the signal is sparse in the frequency domain, each bucket is likely3 to have only one large coefficient, which can then be located (to find its position) and estimated (to find its value). For the algorithm to be sublinear, the binning has to be done in sublinear time. Binning the Fourier coefficient is done using an n-dimensional filter vector G that is concentrated both in time and frequency, i.e., G is zero except at a small number of time coordinates, and its Fourier transform
Prior work uses different types of filters. Depending on the choice of the filter G,
