The Sparse Fourier Transform. Haitham Hassanieh

      By Claims 4.1 and 4.2, and for any i ∈ S

      Claim 4.4 For any i ∈ S, .

      Proof For each j ≠ i, by Lemma 2.1.

      Then

      The result follows by Markov’s inequality.

      We will show for i ∈ S that if none of E_coll(i), E_off(i), and E_noise(i) hold then SPARSEFFTINNER recovers with 1 − O(α) probability.

      Lemma 4.5 Let a ∈ [n] uniformly at random, B divide n, and the other parameters be arbitrary in

      Then for any i ∈ [n] with and none of E_coll(i), E_off(i), or E_noise(i) holding,

      Proof The proof can be found in Appendix A.5.

      Properties of LOCATESIGNAL

      In our intuition, we made a claim that if uniformly at random, and i > 16w, then is “roughly uniformly distributed about the circle” and hence not concentrated in any small region. This is clear if β is chosen as a random real number; it is less clear in our setting where β is a random integer in this range. We now prove a lemma that formalizes this claim.

      Lemma 4.6 Let T ⊂ [m] consist of t consecutive integers, and suppose β ∈ T uniformly at random. Then for any i ∈ [n] and set S ⊂ [n] of l consecutive integers,

      Proof Note that any interval of length l can cover at most elements of any arithmetic sequence of common difference i. Then is such a sequence, and there are at most intervals an + S overlapping this sequence. Hence, at most of the β ∈ [m] have βi mod n ∈ S. Hence, .

      Lemma 4.7 Let i ∈ S. Suppose none of E_coll(i), E_off(i), and E_noise(i) hold, and let j = hσ,b(i). Consider any run of LOCATEINNER with . Let f > 0 be a parameter such that

      for C larger than some fixed constant. Then with probability at least ,