Sparse Fourier Transform in Any Constant Dimension with
Nearly-Optimal Sample Complexity in Sublinear Time

arXiv:1604.00845v1 [] 4 Apr 2016

Michael Kapralov
EPFL
April 5, 2016

Abstract
We consider the problem of computing a k-sparse approximation to the Fourier transform of a length N
signal. Our main result is a randomized algorithm for computing such an approximation (i.e. achieving the
ℓ2 /ℓ2 sparse recovery guarantees using Fourier measurements) using Od (k log N log log N ) samples of the
signal in time domain that runs in time Od (k logd+3 N ), where d ≥ 1 is the dimensionality of the Fourier
transform. The sample complexity matches the lower bound of Ω(k log(N/k)) for non-adaptive algorithms
due to [DIPW10] for any k ≤ N 1−δ for a constant δ > 0 up to an O(log log N ) factor. Prior to our work a
result with comparable sample complexity k log N logO(1) log N and sublinear runtime was known for the
Fourier transform on the line [IKP14], but for any dimension d ≥ 2 previously known techniques either
suffered from a poly(log N ) factor loss in sample complexity or required Ω(N ) runtime.

Contents
1 Introduction

2

2 Preliminaries

5

3 The algorithm and proof overview

9

4 Organization

13

5 Analysis of L OCATE S IGNAL: main definitions and basic claims

13

6 Analysis of L OCATE S IGNAL: bounding ℓ1 norm of undiscovered elements
6.1 Bounding noise from heavy hitters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Bounding effect of tail noise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3 Putting it together . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19
20
23
25

7 Analysis of R EDUCE L1N ORM and S PARSE FFT
7.1 Analysis of R EDUCE L1N ORM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.2 Analysis of SNR reduction loop in S PARSE FFT . . . . . . . . . . . . . . . . . . . . . . . . .
7.3 Analysis of S PARSE FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26
26
32
35

8 ℓ∞ /ℓ2 guarantees and constant SNR case
8.1 ℓ∞ /ℓ2 guarantees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8.2 Recovery at constant SNR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36
36
38

9 Utilities
9.1 Properties of E STIMATE VALUES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.2 Properties of H ASH T O B INS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9.3 Lemmas on quantiles and the median estimator . . . . . . . . . . . . . . . . . . . . . . . . .

42
42
43
44

10 Semi-equispaced Fourier Transform

46

11 Acknowledgements

48

A Omitted proofs

50

1

1 Introduction
The Discrete Fourier Transform (DFT) is a fundamental mathematical concept that allows to represent a discrete
signal of length N as a linear combination of N pure harmonics, or frequencies. The development of a fast
algorithm for Discrete Fourier Transform, known as FFT (Fast Fourier Transform) in 1965 revolutionized digital
signal processing, earning FFT a place in the top 10 most important algorithms of the twentieth century [Cip00].
Fast Fourier Transform (FFT) computes the DFT of a length N signal in time O(N log N ), and finding a faster
algorithm for DFT is a major open problem in theoretical computer science. While FFT applies to general
signals, many of the applications of FFT (e.g. image and video compression schemes such as JPEG and MPEG)
rely on the fact that the Fourier spectrum of signals that arise in practice can often be approximated very well by
only a few of the top Fourier coefficients, i.e. practical signals are often (approximately) sparse in the Fourier
basis.
Besides applications in signal processing, the Fourier sparsity property of real world signal plays and important role in medical imaging, where the cost of measuring a signal, i.e. sample complexity, is often a major
bottleneck. For example, an MRI machine effectively measures the Fourier transform of a signal x representing the object being scanned, and the reconstruction problem is exactly the problem of inverting the Fourier
transform x
b of x approximately given a set of measurements. Minimizing the sample complexity of acquiring a
signal using Fourier measurements thus translates directly to reduction in the time the patient spends in the MRI
machine [LDSP08] while a scan is being taken. In applications to Computed Tomography (CT) reduction in
measurement cost leads to reduction in the radiation dose that a patient receives [Sid11]. Because of this strong
practical motivation, the problem of computing a good approximation to the FFT of a Fourier sparse signal
fast and using few measurements in time domain has been the subject of much attention several communities.
In the area of compressive sensing [Don06, CT06], where one studies the task of recovering (approximately)
sparse signals from linear measurements, Fourier measurements have been one of the key settings of interest. In
particular, the seminal work of [CT06, RV08] has shown that length N signals with at most k nonzero Fourier
coefficients can be recovered using only k logO(1) N samples in time domain. The recovery algorithms are
based on linear programming and run in time polynomial in N . A different line of research on the Sparse
Fourier Transform (Sparse FFT), initiated in the fields of computational complexity and learning theory, has
been focused on developing algorithms whose sample complexity and running time scale with the sparsity as
opposed to the length of the input signal. Many such algorithms have been proposed in the literature, including
[GL89, KM91, Man92, GGI+ 02, AGS03, GMS05, Iwe10, Aka10, HIKP12b, HIKP12a, BCG+ 12, HAKI12,
PR13, HKPV13, IKP14]. These works show that, for a wide range of signals, both the time complexity and the
number of signal samples taken can be significantly sub-linear in N , often of the form k logO(1) N .
In this paper we consider the problem of computing a sparse approximation to a signal x ∈ CN given access
to its Fourier transform x
b ∈ CN .1 The best known results obtained in both compressive sensing literature and
sparse FFT literature on this problem are summarized in Fig. 1. We focus on algorithms that work for worstcase signals and recover k-sparse approximations satisfying the so-called ℓ2 /ℓ2 approximation guarantee. In
this case, the goal of an algorithm is as follows: given m samples of the Fourier transform x
b of a signal x, and
the sparsity parameter k, output x′ satisfying
kx − x′ k2 ≤ C min kx − yk2 ,
k-sparse y

(1)

The algorithms are randomized2 and succeed with at least constant probability.
Higher dimensional Fourier transform. While significant attention in the sublinear Sparse FFT literature
has been devoted to the basic case of Fourier transform on the line (i.e. one-dimensional signals), the spars1

Note that the problem of reconstructing a signal from Fourier measurements is equivalent to the problem of computing the Fourier
transform of a signal x whose spectrum is approximately sparse, as the DFT and its inverse are only different by a conjugation.
2
Some of the algorithms [CT06, RV08, CGV12] can in fact be made deterministic, but at the cost of satisfying a somewhat weaker
ℓ2 /ℓ1 guarantee.

2

Reference

Time

Samples

C

Dimension
d > 1?

[CT06, RV08, CGV12]
[Bou14, HR16]
[CP10]
[HIKP12a]
[IKP14]
[IK14]
[DIPW10]

N × m linear program
N × m linear program
O(k log(N ) log(N/k))
k log2 (N ) logO(1) log N
N logO(1) N

O(k log2 (k) log(N ))
O(k log N )
O(k log(N ) log(N/k))
k log(N ) logO(1) log N
O(k log N )
Ω(k log(N/k))

O(1)
(log N )O(1)
any
any
any
O(1)

yes
yes
no
no
yes
lower bound

Figure 1: Bounds for the algorithms that recover k-sparse Fourier approximations. All algorithms produce an
output satisfying Equation 1 with probability of success that is at least constant. The forth column specifies
constraints on approximation factor C. For example, C = O(1) means that the algorithm can only handle
constant C as opposed to any C > 1. The last column specifies whether the sample complexity bounds are
unchanged, up to factors that depend on dimension d only, for higher dimensional DFT.
est signals often occur in applications involving higher-dimensional DFTs. Although a reduction from DFT
on a two-dimensional grid with relatively prime side lengths p × q to a one-dimensional DFT of length pq
is possible [GMS05, Iwe12]), the reduction does not apply to the most common case when the side lengths
of the grid are equal to the same powers of two. It turns out that most sublinear Sparse FFT techniques developed for the one-dimensional DFT do not extend well to the higher dimensional setting, suffering from
at least a polylogaritmic loss in sample complexity. Specifically, the only prior sublinear time algorithm that
applies to general m × m grids is due to to [GMS05], has O(k logc N ) sample and time complexity for a
rather large value of c. If N is a power of 2, a two-dimensional adaptation of the [HIKP12a] algorithm (outlined in [GHI+ 13]) has roughly O(k log3 N ) time and sample complexity, and an adaptation of [IKP14] has
O(k log2 N (log log N )O(1) ) sample complexity. In general dimension d ≥ 1 both of these algorithms have
sample complexity Ω(k logd N ).
Thus, none of the results obtained so far was able to guarantee sparse recovery from high dimensional (any
d ≥ 2) Fourier measurements without suffering at least a polylogarithmic loss in sample complexity, while at
the same time achieving sublinear runtime.
Our results. In this paper we give an algorithm that achieves the ℓ2 /ℓ2 sparse recovery guarantees (1) with
d-dimensional Fourier measurements that uses Od (k log N log log N ) samples of the signal and has the running
time of Od (k logd+3 N ). This is the first sublinear time algorithm that comes within a poly(log log N ) factor
of the sample complexity lower bound of Ω(k log(N/k)) due to [DIPW10] for any dimension higher than one.
Sparse Fourier Transform overview. The overall outline of our algorithm follows the framework of [GMS05,
HIKP12a, IKP14, IK14], which adapt the methods of [CCFC02, GLPS10] from arbitrary linear measurements
to Fourier measurements. The idea is to take, multiple times, a set of B = O(k) linear measurements of the
form
X
ũj =
s i xi
i:h(i)=j

for random hash functions h : [N ] → [B] and random sign changes si with |si | = 1. This corresponds to
hashing to B buckets. With such ideal linear measurements, O(log(N/k)) hashes suffice for sparse recovery,
giving an O(k log(N/k)) sample complexity.
The sparse Fourier transform algorithms approximate ũ using linear combinations of Fourier samples.
Specifically, the coefficients of x are first permuted via a random affine permutation of the input space. Then the
coefficients are partitioned into buckets. This step uses the“filtering” process that approximately partitions the

3

range of x into intervals (or, in higher dimension, squares, or ℓ∞ balls) with N/B coefficients each, where each
interval corresponds to one bucket. Overall, this ensures that most of the large coefficients are “isolated”, i.e.,
are hashed to unique buckets, as well as that the contributions from the “tail” of the signal x to those buckets
is not much greater than the average (the tail of the signal defined as Errk (x) = mink−sparse y ||x − y||2 ). This
allows one to mimic the iterative recovery algorithm described for linear measurements above. However, there
are several difficulties in making this work using an optimal number of samples.
This enables the algorithm to identify the locations of the dominant coefficients and estimate their values,
producing a sparse estimate χ of x. To improve this estimate, we repeat the process on x − χ by subtracting
the influence of χ during hashing, thereby refining the approximation of x constructed. After a few iterations
of this refinement process the algorithm obtains a good sparse approximation χ of x.
A major hurdle in implementing this strategy is that any filter that has been constructed in the literature so far
is imprecise in that coefficients contribute (“leak”’) to buckets other than the one they are technically mapped
into. This contribution, however, is limited and can be controlled by the quality of the filter. The details of
filter choice have played a crucial role in recent developments in Sparse FFT algorithms. For example, the
best known runtime for one-dimensional Sparse FFT, due to [HIKP12b], was obtained by constructing filters
that (almost) precisely mimic the ideal hash process, allowing for a very fast implementation of the process in
dimension one. The price to pay for the precision of the filter, however, is that each hashing becomes a logd N
factor more costly in terms of sample complexity and runtime than in the idealized case. At the other extreme,
the algorithm of [GMS05] uses much less precise filters, which only lead to a C d loss of sample complexity
in higher dimensions d, for a constant C > 0. Unfortunately, because of the imprecision of the filters the
iterative improvement process becomes quite noisy, requiring Ω(log N ) iterations of the refinement process
above. As [GMS05] use fresh randomness for each such iteration, this results in an Ω(log N ) factor loss in
sample complexity. The result of [IKP14] uses a hybrid strategy, effectively interpolating between [HIKP12b]
and [GMS05]. This gives the near optimal O(k log N logO(1) log N ) sample complexity in dimension one (i.e.
Fourier transform on the line), but still suffers from a logd−1 N loss in dimension d.
Techniques of [IK14]. The first algorithm to achieve optimal sample complexity was recently introduced
in [IK14]. The algorithms uses an approach inspired by [GMS05] (and hence uses ‘crude’ filters that do not
lose much in sample complexity), but introduces a key innovation enabling optimal sample complexity: the
algorithm does not use fresh hash functions in every repetition of the refinement process. Instead, O(log N )
hash functions are chosen at the beginning of the process, such that each large coefficient is isolated by most of
those functions with high probability. The same hash functions are then used throughout the execution of the
algorithm. As every hash function required a separate set of samples to construct the buckets, reusing the hash
functions makes sample complexity independent of the number of iterations, leading to the optimal bound.
While a natural idea, reusing hash functions creates a major difficulty: if the algorithm identified a nonexistent large coefficient (i.e. a false positive) by mistake and added it to χ, this coefficient would be present
in the difference vector x − χ (i.e. residual signal) and would need to be corrected later. As the spurious
coefficient depends on the measurements, the ‘isolation’ properties required for recovery need not hold for it
as its position is determined by the hash functions themselves, and the algorithm might not be able to correct
the mistake. This hurdle was overcome in [IK14] by ensuring that no large coefficients are created spuriously
throughout the execution process. This is a nontrivial property to achieve, as the hashing process is quite
noisy due to use of the ‘crude’ filters to reduce the number of samples (because the filters are quite simple,
the bucketing process suffers from substantial leakage). The solution was to recover the large coefficients
in decreasing order of their magnitude. Specifically, in each step, the algorithm recovered coefficients with
magnitude that exceeded a specific threshold (that decreases at an exponential rate). With this approach the
ℓ∞ norm of the residual signal decreases by a constant factor in every round, resulting in the even stronger
ℓ∞ /ℓ2 sparse recovery guarantees in the end. The price to pay for this strong guarantee was the need for a very
strong primitive for locating dominant elements in the residual signal: a primitive was needed that would make
mistakes with at most inverse polynomial probability. This was achieved by essentially brute-force decoding
4

over all potential elements in [N ]: the algorithm loops over all elements i ∈ [N ] and for each i tests, using the
O(log N ) measurements taken, whether i is a dominant element in the residual signal. This resulted in Ω(N )
runtime.
Our techniques. In this paper we show how to make the aforementioned algorithm run in sub-linear
time, at the price of a slightly increased sampling complexity of Od (k log N log log N ). To achieve a sublinear runtime, we need to replace the loop over all N coefficients by a location primitive (similar to that in
prior works) that identifies the position of any large coefficient that is isolated in a bucket in logO(1) N time
per bucket, i.e. without resorting to brute force enumeration over the domain of size N . Unfortunately, the
identification step alone increases the sampling complexity by O(log N ) per hash function, so unlike [IK14],
here we cannot repeat this process using O(log N ) hash functions to ensure that each large coefficient is isolated
by one of those functions. Instead, we can only afford O(log log N ) hash functions overall, which means that
1/ logO(1) N fraction of large coefficients will not be isolated in most hashings. This immediately precludes
the possibility of using the initial samples to achieve ℓ∞ norm reduction as in [IK14]. Another problem,
however, is that the weaker location primitive that we use may generate spurious coefficients at every step
of the recovery process. These spurious coefficients, together with the 1/ log O(1) N fraction of non-isolated
elements, contaminate the recovery process and essentially render the original samples useless after a small
number of refinement steps. To overcome these hurdles, instead of the ℓ∞ reduction process of [IK14] we
use a weaker invariant on the reduction of mass in the ‘heavy’ elements of the signal throughout our iterative
process. Specifically, instead of reduction of ℓ∞ norm of the residual as in [IK14] we give a procedure for
reducing the ℓ1 norm of the ‘head’ of the signal. To overcome the contamination coming from non-isolated as
well as spuriously created coefficients, we achieve ℓ1 norm reduction by alternating two procedures. The first
procedure uses the O(log log N ) hash functions to reduce the ℓ1 norm of ‘well-hashed’ elements in the signal,
and the second uses a simple sparse recovery primitive to reduce the ℓ∞ norm of offending coefficients when
the first procedure gets stuck. This can be viewed as a signal-to-noise ratio (SNR) reduction step similar in spirit
the one achieved in [IKP14]. The SNR reduction phase is insufficient for achieving the ℓ2 /ℓ2 sparse recovery
guarantee, and hence we need to run a cleanup phase at the end, when the signal to noise ratio is constant. It has
been observed before (in [IKP14]) that if the signal to noise ratio is constant, then recovery can be done using
standard techniques with optimal sample complexity. The crucial difference between [IKP14] and our setting
is, however, that we only have bounds on ℓ1 -SNR as opposed to ℓ2 -SNR In [IKP14]. It turns out, however, that
this is not a problem – we give a stronger analysis of the corresponding primitive from [IKP14], showing that
ℓ1 -SNR bound is sufficient.
Related work on continuous Sparse FFT. Recently [BCG+ 12] and [PS15] gave algorithms for the related
problem of computing Sparse FFT in the continuous setting. These results are not directly comparable to ours,
and suffer from a polylogarithmic inefficiency in sample complexity bounds.

2 Preliminaries
For a positive even integer a we will use the notation [a] = {− a2 , − a2 + 1, . . . , −1, 0, 1, . . . , a2 − 1}. We will
consider signals of length N = nd , where n is a power of 2 and d ≥ 1 is the dimension. We use the notation
ω = e2πi/n for the root of unity of order n. The d-dimensional forward and inverse Fourier transforms are
given by
1 X iT j
1 X −iT j
ω
xi and xj = √
ω x̂i
(2)
x̂j = √
N i∈[n]d
N i∈[n]d
respectively, where j ∈ [n]d . We will denote the forward Fourier transform by F and Note that we use
the orthonormal version of the Fourier transform. We assume that the input signal has entries of polynomial
precision and range. Thus, we have ||x̂||2 = ||x||2 for all x ∈ CN (Parseval’s identity). Given access to samples
5

of x
b, we recover a signal z such that

||x − z||2 ≤ (1 + ǫ)

min

k− sparse y

||x − y||2

We will use pseudorandom spectrum permutations, which we now define. We write Md×d for the set of
d × d matrices over Zn with odd determinant. For Σ ∈ Md×d , q ∈ [n]d and i ∈ [n]d let πΣ,q (i) = Σ(i − q)
mod n. Since Σ ∈ Md×d , this is a permutation. Our algorithm will use π to hash heavy hitters into B buckets,
where we will choose B ≈ k. We will often omit the subscript Σ, q and simply write π(i) when Σ, q is fixed
or clear from context. For i, j ∈ [n]d we let oi (j) = π(j) − (n/b)h(i) be the “offset” of j ∈ [n]d relative to
i ∈ [n]d (note that this definition is different from the one in [IK14]). We will always have B = bd , where b is
a power of 2.
Definition 2.1. Suppose that Σ−1 exists mod n. For a, q ∈ [n]d we define the permutation PΣ,a,q by (PΣ,a,q x̂)i =
T
x̂ΣT (i−a) ω i Σq .
T Σi

Lemma 2.2. F −1 (PΣ,a,q x̂)πΣ,q (i) = xi ω a

The proof is given in [IK14] and we do not repeat it here. Define
Errk (x) =

min

k−sparse y

||x − y||2 and µ2 = Err2k (x)/k.

(3)

In this paper, we assume knowledge of µ (a constant factor upper bound on µ suffices). We also assume that
the signal to noise ration is bounded by a polynomial, namely that R∗ := ||x||∞ /µ ≤ N O(1) . We use the
d
∞
notation B∞
r (x) to denote the ℓ∞ ball of radius r around x: Br (x) = {y ∈ [n] : ||x − y||∞ ≤ r}, where
||x − y||∞ = maxs∈d ||xs − ys ||◦ , and ||xs − ys ||◦ is the circular distance on Zn . We will also use the notation
f . g to denote f = O(g). For a real number a we write |a|+ to denote the positive part of a, i.e. |a|+ = a if
a ≥ 0 and |a|+ = 0 otherwise.
We will use the filter G, Ĝ constructed in [IK14]. The filter is defined by a parameter F ≥ 1 that governs
its decay properties. The filter satisfies supp Ĝ ⊆ [−F · b, F · b]d and
n
and
Lemma 2.3 (Lemma 3.1 in [IK14]). One has (1) Gj ∈ [ (2π)1F ·d , 1] for all j ∈ [n]d such that ||j||∞ ≤ 2b
F

2
(2) |Gj | ≤ 1+(b/n)||j||
for all j ∈ [n]d as long as b ≥ 3 and (3) Gj ∈ [0, 1] for all j as long as F is even.
∞

Remark 2.4. Property (3) was not stated explicitly in Lemma 3.1 of [IK14], but follows directly from their
construction.

The properties above imply that most of the mass of the filter is concentrated in a square of side O(n/b),
approximating the “ideal” filter (whose value would be equal to 1 for entries within the square and equal to
0 outside of it). Note that for each i ∈ [n]d one has |Goi (i) | ≥ (2π)1d·F . We refer to the parameter F as the
sharpness of the filter. Our hash functions are not pairwise independent, but possess a property that still makes
hashing using our filters efficient:
Lemma 2.5 (Lemma 3.2 in [IK14]). Let i, j ∈ [n]d . Let Σ be uniformly random with odd determinant. Then
for all t ≥ 0 one has Pr[||Σ(i − j)||∞ ≤ t] ≤ 2(2t/n)d .
Pseudorandom spectrum permutations combined with a filter G give us the ability to ‘hash’ the elements
of the input signal into a number of buckets (denoted by B). We formalize this using the notion of a hashing.
A hashing is a tuple consisting of a pseudorandom spectrum permutation π, target number of buckets B and a
sharpness parameter F of our filter, denoted by H = (π, B, F ). Formally, H is a function that maps a signal x
to B signals, each corresponding to a hash bucket, allowing us to solve the k-sparse recovery problem on input
x by reducing it to 1-sparse recovery problems on the bucketed signals. We give the formal definition below.
6

Definition 2.6 (Hashing H = (π, B, F )). For a permutation π = (Σ, q), parameters b > 1, B = bd and F ,
d
a hashing H := (π, B, F ) is a function mapping a signal x ∈ C[n] to B signals H(x) = (us )s∈[b]d , where
d

us ∈ C[n] for each s ∈ [b]d , such that for each i ∈ [n]d
X
T
us,i =
Gπ(j)−(n/b)·s xj ω i Σj ∈ C,
j∈[n]d

where G is a filter with B buckets and sharpness F constructed in Lemma 2.3.
For a hashing H = (π, B, F ), π = (Σ, q) we sometimes write PH,a , a ∈ [n]d to denote PΣ,a,q . We will
consider hashings of the input signal x, as well as the residual signal x − χ, where
d

Definition 2.7 (Measurement m = m(x, H, a)). For a signal x ∈ C[n] , a hashing H = (π, B, F ) and a
d
parameter a ∈ [n]d , a measurement m = m(x, H, a) ∈ C[b] is the B-dimensional complex valued vector of
d
evaluations of a hashing H(x) at a ∈ C[n] , i.e. length B, indexed by [b]d and given by evaluating the hashing
H at a ∈ [n]d , i.e. for s ∈ [b]d
X
T
ms =
Gπ(j)−(n/b)·s xj ω a Σj ,
j∈[n]d

where G is a filter with B buckets and sharpness F constructed in Lemma 2.3.
d

d

Definition 2.8. For any x ∈ C[n] and any hashing H = (π, B, G) define the vector µ2H,· (x) ∈ R[n] by letting
for every i ∈ [n]d
X
|
|xj |2 |Goi (j) |2 .
µ2H,i (x) := |G−1
oi (i)
j∈[n]d \{i}

We access the signal x in Fourier domain via the function H ASH T O B INS (x̂, χ, (H, a)), which evaluates
the hashing H of residual signal x − χ at point a ∈ [n]d , i.e. computes the measurement m(x, H, a) (the
computation is done with polynomial precision). One can view this function as “hashing” x into B bins by
convolving it with the filter G constructed above and subsampling appropriately. The pseudocode for this
function is given in section 9.2. In what follows we will use the following properties of H ASH T O B INS:
Lemma 2.9. There exists a constant C > 0 such that for any dimension d ≥ 1, any integer B ≥ 1, any
d
x, χ ∈ C[n] , x′ := x − χ, if Σ ∈ Md×d , a, q ∈ [n]d are selected uniformly at random, the following conditions
hold.
Let π = (Σ, q), H = (π, B, G), where G is the filter with B buckets and sharpness F constructed in
Lemma 2.3, and let u = H ASH T O B INS (x̂, χ, (H, a)). Then if F ≥ 2d, F = Θ(d), for any i ∈ [n]d
P
−1
′
−aT Σi u
′
(1) For any H one has maxa∈[n]d |G−1
h(i) − xi | ≤ Goi (i) ·
j∈S\{i} Goi (j) |xj |. Furthermore,
oi (i) ω
P
′
d·F · C d ||x′ || /B + N −Ω(c) ;
EH [G−1
1
j∈S\{i} Goi (j) |xj |] ≤ (2π)
oi (i) ·
(2) EH [µ2H,i (x′ )] ≤ (2π)2d·F · C d kx′ k22 /B,
Furthermore,
(3) for any hashing H, if a is chosen uniformly at random from [n]d , one has
T Σi

−a
Ea [|G−1
oi (i) ω

uh(i) − x′i |2 ] ≤ µ2H,i (x′ ) + N −Ω(c) .

Here c > 0 is an absolute constant that can be chosen arbitrarily large at the expense of a factor of cO(d) in
runtime.
7

The proof of Lemma 2.9 is given in Appendix A. We will need several definitions and lemmas from [IK14],
which we state here. We sometimes need slight modifications of the corresponding statements from [IK14],
in which case we provide proofs in Appendix A. Throughout this paper the main object of our analysis is a
properly defined set S ⊆ [n]d that contains the ’large’ coefficients of the input vector x. Below we state our
definitions and auxiliary lemmas without specifying the identity of this set, and then use specific instantiations
of S to analyze outer primitives such as R EDUCE L1N ORM, R EDUCE I NF N ORM and R ECOVER AT C ONSTSNR. This is convenient because the analysis of all of these primitives can then use the same basic claims
about estimation and location primitives. The definition of S given in (4) above is the one we use for analyzing
R EDUCE L1N ORM and the SNR reduction loop. Analysis of R EDUCE I NF N ORM (section 8.1) and R ECOVER AT C ONSTANT SNR (section 8.2) use different instantiations of S, but these are local to the corresponding
sections, and hence the definition in (4) is the best one to have in mind for the rest of this section.
First, we need the definition of an element i ∈ [n]d being isolated under a hashing H = (π, B, F ). Intuitively, an element i ∈ S is isolated under hashing H with respect to set S if not too many other elements S are
hashed too close to i. Formally, we have
Definition 2.10 (Isolated element). Let H = (π, B, F ), where π = (Σ, q), Σ ∈ Md×d , q ∈ [n]d . We say that
an element i ∈ [n]d is isolated under hashing H at scale t if
t
−d·F
|π(S \ {i}) ∩ B∞
· αd/2 2(t+1)d · 2t .
(n/b)·h(i) ((n/b) · 2 )| ≤ (2π)

We say that i is simply isolated under hashing H if it is isolated under H at all scales t ≥ 0.
The following lemma shows that any element i ∈ S is likely to be isolated under a random permutation π:
Lemma 2.11. For any integer k ≥ 1 and any S ⊆ [n]d , |S| ≤ 2k, if B ≥ (2π)4d·F ·k/αd for α ∈ (0, 1) smaller
than an absolute constant, F ≥ 2d, and a hashing H = (π, B, F ) is chosen randomly (i.e. Σ ∈ Md×d , q ∈ [n]d
are chosen uniformly at random, and π = (Σ, q)), then each i ∈ [n]d is isolated under permutation π with
√
probability at least 1 − 12 α.
The proof of the lemma is very similar to Lemma 5.4 in [IK14] (the only difference is that the ℓ∞ ball is
centered at the point that i hashes to in Lemma 2.11, whereas it was centered at π(i) in Lemma 5.4 of [IK14])
and is given in Appendix A for completeness.
As every element i ∈ S is likely to be isolated under one random hashing, it is very likely to be isolated
under a large fraction of hashings H1 , . . . , Hrmax :
Lemma 2.12. For any integer k ≥ 1, and any S ⊆ [n]d , |S| ≤ 2k, if B ≥ (2π)4d·F · k/αd for α ∈ (0, 1)
smaller than an absolute constant, F ≥ 2d, Hr = (πr , B, F ), r = 1, . . . , rmax a sequence of random hashings,
√
then every i ∈ [n]d is isolated with
√ respect to S under at least (1 − α)rmax hashings Hr , r = 1, . . . , rmax
with probability at least 1 − 2−Ω( αrmax ) .
Proof. Follows by an application of Chernoff bounds and Lemma 2.11.
It is convenient for our location primitive (L OCATE S IGNAL, see Algorithm 1) to sample the signal at pairs
of locations chosen randomly (but in a correlated fashion). The two points are then combined into one in a
linear fashion. We now define notation for this common operation on pairs of numbers in [n]d . Note that we are
viewing pairs in [n]d × [n]d as vectors in dimension 2, and the ⋆ operation below is just the dot product over this
two dimensional space. However, since our input space is already endowed with a dot product (for i, j ∈ [n]d
we denote their dot product by iT j), having special notation here will help avoid confusion.

8

Operations on vectors in [n]d . For a pair of vectors (α1 , β1 ), (α2 , β2 ) ∈ [n]d × [n]d we let (α1 , β1 ) ⋆ (α2 , β2 )
denote the vector γ ∈ [n]d such that
γi = (α1 )i · (α2 )i + (β1 )i · (β2 )i for all i ∈ [d].
Note that for any a, b, c ∈ [n]d × [n]d one has a ⋆ b + a ⋆ c = a ⋆ (b + c), where addition for elements of
[n]d × [n]d is componentwise. We write 1 ∈ [n]d for the all ones vector in dimension d, and 0 ∈ [n]d for the
zero vector. For a set A ⊆ [n]d × [n]d and a vector (α, β) ∈ [n]d × [n]d we denote
A ⋆ (α, β) := {a ⋆ (α, β) : a ∈ A}.
Definition 2.13 (Balanced set of points). For an integer ∆ ≥ 2 we say that a (multi)set Z ⊆ [n]d is ∆-balanced
r·zs
}z∈Z
in coordinate s ∈ [1 : d] if for every r = 1, . . . , ∆ − 1 at least 49/100 fraction of elements in the set {ω∆
belong to the left halfplane {u ∈ C : Re(u) ≤ 0} in the complex plane, where ω∆ = e2πi/∆ is the ∆-th root of
unity.
r·zs
is uniformly distributed over the
Note that if ∆ divides n, then for any fixed value of r the point ω∆
′
roots of unity for some ∆ between 2 and ∆ for every r = 1, . . . , ∆ − 1 when zs is uniformly random
in [n]. Thus for r 6= 0 we expect at least half the points to lie in the halfplane {u ∈ C : Re(u) ≤ 0}. A set
Z is balanced if it does not deviate from expected behavior too much. The following claim is immediate via
standard concentration bounds:

∆′ -th

Claim 2.14. There exists a constant C > 0 such that for any ∆ a power of two, ∆ = logO(1) n, and n a power
of 2 the following holds if ∆ < n. If elements of a (multi)set A ⊆ [n]d × [n]d of size C log log N are chosen
uniformly at random with replacement from [n]d × [n]d , then with probability at least 1 − 1/ log4 N one has
that for every s ∈ [1 : d] the set A ⋆ (0, es ) is ∆-balanced in coordinate s.
Since we only use one value of ∆ in the paper (see line 8 in Algorithm 1), we will usually say that a set is
simply ‘balanced’ to denote the ∆-balanced property for this value of ∆.

3 The algorithm and proof overview
In this section we state our algorithm and give an outline of the analysis. The formal proofs are then presented
in the rest of the paper (the organization of the rest of the paper is presented in section 4). Our algorithm
(Algorithm 2), at a high level, proceeds as follows.
Measuring x
b. The algorithms starts by taking measurements of the signal in lines 5-16. Note that the
algorithm selects O(log log N ) hashings Hr = (πr , B, F ), r = 1, . . . , O(log log N ), where πr are selected
uniformly at random, and for each r selects a set Ar ⊆ [n]d ×[n]d of size O(log log N ) that determines locations
to access in frequency domain. The signal x
b is accessed via the function H ASH T O B INS (see Lemma 2.9 above
for its properties. The function H ASH T O B INS accesses filtered versions of x
b shifted by elements of a randomly
selected set (the number of shifts is O(log N/ log log N )). These shifts are useful for locating ‘heavy’ elements
from the output of H ASH T O B INS. Note that since each hashing takes O(B) = O(k) samples, the total sample
complexity of the measurement step is O(k log N log log N ). This is the dominant contribution to sample
complexity, but it is not the only one. The other contribution of O(k log N log log N ) comes from invocations of
E STIMATE VALUES from our ℓ1 -SNR reduction loop (see below). The loop goes over O(log R∗ ) = O(log N )
iterations, and in each iteration E STIMATE VALUES uses O(log log N ) fresh hash functions to keep the number
of false positives and estimation error small.
The location algorithm is Algorithm 1. Our main tool for bounding performance of L OCATE S IGNAL is
Theorem 3.1, stated below. Theorem 3.1 applies to the following setting. Fix a set S ⊆ [n]d and a set of
hashings H1 , . . . , Hrmax that encode signal measurement patterns, and let S ∗ ⊆ S denote the set of elements
9

of S that are not isolated with respect to most of these hashings. Theorem 3.1 shows that for any signal x and
partially recovered signal χ, if L denotes the output list of an invocation of L OCATE S IGNAL on the pair (x, χ)
with measurements given by H1 , . . . , Hrmax and a set of random shifts, then the ℓ1 norm of elements of the
residual (x − χ)S that are not discovered by L OCATE S IGNAL can be bounded by a function of the amount of
ℓ1 mass of the residual that fell outside of the ‘good’ set S \ S ∗ , plus the ‘noise level’ µ ≥ ||x[n]d \S ||∞ times k.
If we think of applying Theorem 3.1 iteratively, we intuitively get that the fixed set of measurements given
by hashings H1 , . . . , Hr allows us to always reduce the ℓ1 norm of the residual x′ = x − χ on the ‘good’
set S \ S ∗ to about the amount of mass that is located outside of this good set(this is exactly how we use
L OCATE S IGNAL in our signal to noise ratio reduction loop below). In section 6 we prove
Theorem 3.1. For any constant C ′ > 0 there exist absolute constants C1 , C2 , C3 > 0 such that for any x, √
χ∈
CN , x′ = x−χ, any integer k ≥ 1 and any S ⊆ [n]d such that ||x[n]d \S ||∞ ≤ C ′ µ, where µ = ||x[n]d \[k] ||2 / k,
the following conditions hold if ||x′ ||∞ /µ = N O(1) .
Let πr = (Σr , qr ), r = 1, . . . , rmax denote permutations, and let Hr = (πr , B, F ), F ≥ 2d, F = Θ(d),
where B ≥ (2π)4d·F k/αd for α ∈ (0, 1) smaller than a constant. Let S ∗ ⊆ S denote the set of elements
√
that are not isolated with respect to at least a α fraction of hashings {Hr }. Then if additionally for every
s ∈ [1 : d] the sets Ar ⋆ (1, es ) are balanced in coordinate s (as per Definition 2.13) for all r = 1, . . . , rmax ,
√
and rmax , cmax ≥ (C1 / α) log log N , then
L :=

r[
max
r=1



max
L OCATE S IGNAL χ, k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W

satisfies

2

||x′S\S ∗ \L ||1 ≤ (C2 α)d/2 ||x′S ||1 + C3d (||χ[n]d \S ||1 + ||x′S ∗ ||1 ) + 4µ|S|.
Reducing signal to noise ratio. Once the samples have been taken, the algorithm proceeds to the signal to
noise (SNR) reduction loop (lines 17-23). The objective of this loop is to reduce the mass of the top (about k)
elements in the residual signal to roughly the noise level µ · k (once this is done, we run a ‘cleanup’ primitive,
referred to as R ECOVER AT C ONSTANT SNR, to complete the recovery process – see below). Specifically, we
define the set S of ‘head elements’ in the original signal x as
S = {i ∈ [n]d : |xi | > µ},

(4)

where µ2 = Err2k (x)/k is the average tail noise level. Note that we have |S| ≤ 2k. Indeed, if |S| > 2k, more
than k elements of S belong to the tail, amounting to more than µ2 · k = Err2k (x) tail mass. Ideally, we would
like this loop to construct and approximation χ(T ) to x supported only on S such that ||(x−χ(T ) )S ||1 = O(µk),
i.e. the ℓ1 -SNR of the residual signal on the set S of heavy elements is reduced to a constant. As some false
positives will unfortunately occur throughout the execution of our algorithm due to the weaker sublinear time
location and estimation primitives that we use, our SNR reduction loop is to construct an approximation χ(T )
to x with the somewhat weaker properties that
||(x − χ(T ) )S ||1 + ||χ(T ) ||[n]d \S = O(µk)

and

||χ(T ) ||0 ≪ k.

(5)

Thus, we reduce the ℓ1 -SNR on the set S of ‘head’ elements to a constant, and at the same time not introduce
too many spurious coefficients (i.e. false positives) outside S, and these coefficients do not contribute much
ℓ1 mass. The SNR reduction loop itself consists of repeated alternating invocations of two primitives, namely
R EDUCE L1N ORM and R EDUCE I NF N ORM. Of these two the former can be viewed as performing most of
the reduction, and R EDUCE I NF N ORM is naturally viewed as performing a ‘cleanup’ phase to fix inefficiencies
of R EDUCE L1N ORM that are due to the small number of hash functions (only O(log log N ) as opposed to
10

O(log N ) in [IK14]) that we are allowed to use, as well as some mistakes that our sublinear runtime location
and estimation primitives used in R EDUCE L1N ORM might make.
Algorithm 1 Location primitive: given a set of measurements corresponding to a single hash function, returns
a list of elements in [n]d , one per each hash bucket
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

procedure L OCATE S IGNAL(χ, H, {m(b
x , H, a ⋆ (1, w)}a∈A,w∈W )
⊲ H = (π, B, F ), B = bd
Let x′ := x − χ. Compute {m(xb′ , H, a ⋆ (1, w)}a∈A,w∈W using Corollary 10.2 and H ASH T O B INS.
L←∅
for j ∈ [b]d do
⊲ Loop over all hash buckets, indexed by j ∈ [b]d
d
f ←0
for s = 1 to d do
⊲ Recovering each of d coordinates separately
1
∆ ← 2⌊ 2 log2 log2 n⌋
for g = 1 to log∆ n − 1 do
w ← n∆−g · es
⊲ Note that w ∈ W
If there exists a unique r ∈ [0 : ∆ − 1] such that
mj (xb′ ,H,a⋆(1,w))
mj (xb′ ,H,a⋆(1,0))

− 1 < 1/3 for at least 3/5 fraction of a =

then f ← f + ∆g−1 · r · es else return FAIL
end for
end for
L ← L ∪ {Σ−1 f }
end for
return L
end procedure

⊲ Add recovered element to output list

−r·βs
· ω −(n·∆
ω∆

11:

12:
13:
14:
15:
16:
17:
18:

−g f

s )·βs

·

(α, β) ∈ A

R EDUCE L1N ORM is presented as Algorithm 3 below. The algorithm performs O(log log N ) rounds of
the following process: first, run L OCATE S IGNAL on the current residual signal, then estimate values of the
elements that belong to the list L output by L OCATE S IGNAL, and only keep those that are above a certain
1
threshold (see threshold 10000
2−t ν + 4µ in the call the E STIMATE VALUES in line 9 of Algorithm 3). This
thresholding operation is crucial, and allows us to control the number of false positives. In fact, this is very
similar to the approach of [IK14] of recovering elements starting from the largest. The only difference is that (a)
our ‘reliability threshold’ is dictated by the ℓ1 norm of the residual rather than the ℓ∞ norm, as in [IK14], and (b)
some false positives can still occur due to our weaker estimation primitives. Our main tool for formally stating
the effect of R EDUCE L1N ORM is Lemma 3.2 below. Intuitively, the lemma shows that R EDUCE L1N ORM
reduces the ℓ1 norm of the head elements of the input signal x − χ by a polylogarthmic factor, and does not
introduce too many new spurious elements (false positives) in the process. The introduced spurious elements,
if any, do not contribute much ℓ1 mass to the head of the signal. Formally, we show in section 7.1
Lemma 3.2. For any x ∈ CN , any integer k ≥ 1, B ≥ (2π)4d·F · k/αd for α ∈ (0, 1] smaller than an absolute
constant and F ≥ 2d, F = Θ(d) the following conditions hold for the set S := {i ∈ [n]d : |xi | > µ}, where
µ2 := ||x[n]d \[k] ||22 /k. Suppose that ||x||∞ /µ = N O(1) .
For any sequence of hashings Hr = (πr , B, F ), r = 1, . . . , rmax , if S ∗ ⊆ S denotes the set of elements of
√
S that are not isolated with respect to at least a α fraction of the hashings Hr , r = 1, . . . , rmax , then for any
d
χ ∈ C[n] , x′ := x − χ, if ν ≥ (log4 N )µ is a parameter such that
A ||(x − χ)S ||1 ≤ (ν + 20µ)k;
B ||χ[n]d \S ||0 ≤

1
k;
log19 N

11

C ||(x − χ)S ∗ ||1 + ||χ[n]d \S ||1 ≤

ν
k,
log4 N

the following conditions hold.
√
If parameters rmax , cmax are chosen to be at least (C1 / α) log log N , where C1 is the constant from
Theorem 3.1 and measurements are taken as in Algorithm 2, then the output χ′ of the call
max
, 4µ(log 4 n)T −t , µ)
R EDUCE L1N ORM (χ, k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W

satisfies
1. ||(x′ − χ′ )S ||1 ≤

1
νk
log4 N

+ 20µk

2. ||(χ + χ′ )[n]d \S ||0 ≤ ||χ[n]d \S ||0 +

(ℓ1 norm of head elements is reduced by ≈ log4 N factor)
1
k
log20 N

(few spurious coefficients are introduced)

3. ||(x′ − χ′ )S ∗ ||1 + ||(χ + χ′ )[n]d \S ||1 ≤ ||x′S ∗ ||1 + ||χ[n]d \S ||1 +
coefficients does not grow fast)

1
νk
log20 N

(ℓ1 norm of spurious

with probability at least 1 − 1/ log2 N over the randomness used to take measurements m and by calls to E S 2
TIMATE VALUES . The number of samples used is bounded by 2O(d ) k(log log N )2 , and the runtime is bounded
2
by 2O(d ) k logd+2 N .
Equipped with Lemma 3.2 as well as its counterpart Lemma 8.1 that bounds the performance of R EDU (see section 8.1) we are able to prove that the SNR reduction loop indeed achieves its cause,
namely (5). Formally, we prove in section 7.2
CE I NF N ORM

Theorem 3.3. For any x ∈ CN , any integer k ≥ 1, if µ2 = Err2k (x)/k and R∗ ≥ ||x||∞ /µ = N O(1) , the
following conditions hold for the set S := {i ∈ [n]d : |xi | > µ} ⊆ [n]d .
Then the SNR reduction loop of Algorithm 2 (lines 19-25) returns χ(T ) such that
||(x − χ(T ) )S ||1 . µ
(T )
||χ[n]d \S ||1

(ℓ1 -SNR on head elements is constant)

.µ
1

(T )

||χ[n]d \S ||0 .

(spurious elements contribute little in ℓ1 norm)

log

19

N

k

(small number of spurious elements have been introduced)

with probability at least 1 − 1/ log N over the internal randomness used by Algorithm 2. The sample
2
2
complexity is 2O(d ) k log N (log log N ). The runtime is bounded by 2O(d ) k logd+3 N .
Recovery at constant ℓ1 -SNR. Once (5) has been achieved, we run the R ECOVER AT C ONSTANT SNR
primitive (Algorithm 5) on the residual signal. Adding the correction χ′ that it outputs to the output χ(T ) of the
SNR reduction loop gives the final output of the algorithm. We prove in section 8.2
√
Lemma 3.4. For any ǫ > 0, x̂, χ ∈ CN , x′ = x − χ and any integer k ≥ 1 if ||x′[2k] ||1 ≤ O(||x[n]d \[k] ||2 k)

and ||x′[n]d \[2k] ||22 ≤ ||x[n]d \[k] ||22 , the following conditions hold. If ||x||∞ /µ = N O(1) , then the output χ′ of
R ECOVER AT C ONSTANT SNR(x̂, χ, 2k, ǫ) satisfies
||x′ − χ′ ||22 ≤ (1 + O(ǫ))||x[n]d \[k] ||22
2) 1

with at least 99/100 probability over its internal randomness. The sample complexity is 2O(d
2
the runtime complexity is at most 2O(d ) 1ǫ k logd+1 N.

12

ǫ k log N ,

and

We give the intuition behind the proof here, as the argument is somewhat more delicate than the analysis
of R ECOVER AT C ONST SNR in [IKP14], due to the ℓ1 -SNR, rather than ℓ2 -SNR assumption. Specifically, if
instead of ||(x − χ)[2k] ||1 ≤ O(µk) we had ||(x − χ)[2k] ||22 ≤ O(µ2 k), then it would be essentially sufficient
to note that after a single hashing into about k/(ǫα) buckets for a constant α ∈ (0, 1), every element i ∈ [2k]
is recovered with probability at least 1 − O(ǫα), say, as it is enough to (on average) recover all but about an
ǫ fraction of coefficients. This would not be sufficient here since we only have a bound on the ℓ1 norm of the
residual, and hence some elements can contribute much more ℓ2 norm than others. However, we are able to
2
αǫµ
show that the probability that an element of the residual signal x′i is not recovered is bounded by O( αǫµ
|x′i |2 + |x′i | ),
where the first term corresponds to contribution of tail noise and the second corresponds to the head elements.
This bound implies that the total expected ℓ22 mass in the elements that are not recovered is upper bounded by
P
P
αǫµ
αǫµ2
′ 2
2
′
2
i∈[2k] |xi | · O( |x′i |2 + |x′i | ) ≤ O(ǫµ k + ǫµ
i∈[2k] |xi |) = O(ǫµ k), giving the result.
Finally, putting the results above together, we prove in section 7.3
d

Theorem 3.5. For any ǫ > 0, x ∈ C[n] and any integer k ≥ 1, if R∗ ≥ ||x||∞ /µ = N O(1) , µ2 =
O(||x[n]d \[k] ||22 /k) and α > 0 is smaller than an absolute constant, S PARSE FFT(x̂, k, ǫ, R∗ , µ) solves the
2
2
ℓ2 /ℓ2 sparse recovery problem using 2O(d ) (k log N log log N + 1ǫ k log N ) samples and 2O(d ) 1ǫ k logd+3 N
time with at least 98/100 success probability.

4 Organization
The rest of the paper is organized as follows. In section 5 we set up notation necessary for the analysis of
L OCATE S IGNAL, and specifically for a proof of Theorem 3.1, as well as prove some basic claims. In section 6
we prove Theorem 3.1. In section 7 we prove performance guarantees for R EDUCE L1N ORM (Lemma 3.2),
then combine them with Lemma 8.1 to prove that the main loop in Algorithm 2 reduces ℓ1 norm of the head
elements. We then conclude with a proof of correctness for Algorithm 2. Section 8.1 is devoted to analyzing
the R EDUCE I NF N ORM procedure, and section 8.2 is devoted to analyzing the R ECOVER AT C ONSTANT SNR
procedure. Some useful lemmas are gathered in section 9, and section 10 describes the algorithm for semiequispaced Fourier transform that we use to update our samples with the residual signal. Appendix A contains
proofs omitted from the main body of the paper.

5 Analysis of L OCATE S IGNAL: main definitions and basic claims
In this section we state our main signal location primitive, L OCATE S IGNAL (Algorithm 1). Given a sequence of
d
measurements m(b
x, Hr , a ⋆ (1, w))}a∈Ar ,w∈W , r = 1, . . . , rmax a signal x
b ∈ C[n] and a partially recovered
d
signal χ ∈ C[n] , L OCATE S IGNAL outputs a list of locations L ⊆ [n]d that, as we show below in Theorem 3.1
(see section 6), contains the elements of x that contribute most of its ℓ1 mass. An important feature of L O CATE S IGNAL is that it is an entirely deterministic procedure, giving recovery guarantees for any signal x and
any partially recovered signal χ. As Theorem 3.1 shows, however, these guarantees are strongest when most
of the mass of the residual x − χ resides on elements in [n]d that are isolated with respect to most hashings
H1 , . . . , Hrmax used for measurements. This flexibility is crucial for our analysis, and is exactly what allows
us to reuse measurements and thereby achieve near-optimal sample complexity.
In the rest of this section we first state Algorithm 1, and then derive useful characterization of elements i
of the input signal (x − χ)i that are successfully located by L OCATE S IGNAL. The main result of this section
is Corollary 5.2. This comes down to bounding, for a given input signal x and partially recovered signal χ,
the expected ℓ1 norm of the noise contributed to the process of locating heavy hitters in a call to L OCATE S IG NAL(b
x, χ, H, {m(b
x, H, a ⋆ (1, w))}a∈A,w∈W ) by (a) the tail of the original signal x (tail noise etail ) and (b)
13

Algorithm 2 S PARSE FFT(x̂, k, ǫ, R∗ , µ)
1: procedure S PARSE FFT(x̂, k, ǫ, R∗ , µ)
2:
χ(0) ← 0
⊲ in Cn .
∗
3:
T ← log(log4 N ) R
4:
F ← 2d
5:
B ← (2π)4d·F · k/αd , α > 0 sufficiently small constant
√
√
6:
rmax ← (C/ α) log log N, cmax ← (C/ α) log log N for a sufficiently large constant C > 0
1
7:
W ← {0d }, ∆ ← 2⌊ 2 log2 log2 n⌋
⊲ 0d is the zero vector in dimension d
8:
for g = 1 to ⌈log
S∆ n⌉ do
9:
W ← W ∪ ds=1 n∆−g · es
⊲ es is the unit vector in direction s
10:
end for
11:
G ← filter with B buckets and sharpness F , as per Lemma 2.3
12:
for r = 1 to rmax do
⊲ Samples that will be used for location
d
13:
Choose Σr ∈ Md×d , qr ∈ [n] uniformly at random, let πr := (Σr , qr ) and let Hr := (πr , B, F )
14:
Let Ar ← C log log N elements of [n]d × [n]d sampled uniformly at random with replacement
15:
for w ∈ W do
16:
m(b
x, Hr , a ⋆ (1, w)) ← H ASH T O B INS (x̂, 0, (Hr , a ⋆ (1, w))) for all a ∈ Ar , w ∈ W
17:
end for
18:
end for
19:
for t = 0, 1, . . . , T − 1 do 

4
T −t , µ
max
,
4µ(log
n)
20:
χ′ ← R EDUCE L1N ORM χ(t) , k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W
21:
⊲ Reduce ℓ1 norm of dominant elements in the residual signal
22:
ν ′ ← (log4 N )(4µ(log 4 N )T −(t+1) + 20µ)
⊲ Threshold
4
′′
(t)
′
′
′
23:
χ ← R EDUCE I NF N ORM (x̂, χ + χ , 4k/(log N ), ν , ν )
24:
⊲ Reduce ℓ∞ norm of spurious elements introduced by R EDUCE L1N OM
25:
χ(t+1) ← χ(t) + χ′ + χ′′
26:
end for
27:
χ′ ← R ECOVER AT C ONSTANT SNR(x̂, χ(T ) , 2k, ǫ)
28:
return χ(T ) + χ′
29: end procedure


max
,
ν,
µ
Algorithm 3 R EDUCE L1N ORM x
b, χ, k, χ(t) , k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W
1:

2:

3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

max
, ν, µ)
procedure R EDUCE L1N ORM(b
x , χ, k, χ(t) , k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W
(0)
χ ←0
⊲ in Cn
B ← (2π)4d·F · k/αd
for t = 0 to log2 (log4 N ) do
for r = 1 to rmax do


max
Lr ← L OCATE S IGNAL χ + χ(t) , k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W
end for
S max
Lr
L ← rr=1
1
ν2−t + 4µ, C(log log N + d2 + log(B/k)))
χ′ ← E STIMATE VALUES (b
x, χ + χ(t) , L, 4k, 1, 1000
χ(t+1) ← χ(t) + χ′
end for
return χ + χ(T )
end procedure

14

the heavy hitters and false positives (heavy hitter noise ehead ). It is useful to note that unlike in [IK14], we
cannot expect the tail of the signal to not change, but rather need to control this change.
In what follows we derive useful conditions under which an element i ∈ [n]d is identified by L OCATE SIGNAL. Let S ⊆ [n]d be any set of size at most 2k, and let µ be such that x[n]d \S ≤ µ. Note that this fits the
definition of S given in (4) (but other instantiations are possible, and will be used later in section 8.2).
Consider a call to
L OCATE S IGNAL (χ, H, {m(b
x, H, a ⋆ (1, w)}a∈A,w∈W ).

For each a ∈ A and fixed w ∈ W we let z := a ⋆ (1, w) ∈ [n]d to simplify notation. The measurement vectors
m := m(xb′ , H, z) computed in L OCATE S IGNAL satisfy, for every i ∈ S, (by Lemma 9.2)
X
T
mh(i) =
Goi (j) x′j ω z Σj + ∆h(i),z ,
j∈[n]d

where ∆ corresponds to polynomially small estimation noise due to approximate computation of the Fourier
transform, and the filter Goi (j) is the filter corresponding to hashing H. In particular, for each hashing H and
parameter a ∈ [n]d one has:
X
T
−z T Σi
−z T Σi
Goi (j) x′j ω z Σ(j−i) + G−1
= x′i + G−1
G−1
oi (i) ∆h(i),z ω
oi (i)
oi (i) mh(i) ω
j∈[n]d \{i}

It is useful to represent the residual signal x as a sum of three terms: x′ = (x − χ)S − χ[n]d \S + x[n]d \S ,
where the first term is the residual signal coming from the ‘heavy’ elements in S, the second corresponds to
false positives, or spurious elements discovered and erroneously subtracted by the algorithm, and the third
corresponds to the tail of the signal. Similarly, we bound the noise contributed by the first two (head elements
and false positives) and the third (tail noise) parts of the residual signal to the location process separately. For
each i ∈ S we write
T

−z Σi
= x′i
G−1
oi (i) mh(i) ω

X
T

+ G−1
Goi (j) x′j ω z Σ(j−i) −
oi (i) ·
j∈S\{i}

+

G−1
oi (i)

·

X

Goi (j) xj ω z

j∈[n]d \S

−z
+ G−1
oi (i) · ∆h(i) ω

T Σi

T Σ(j−i)

X

Goi (j) χj ω z

j∈[n]d \S

T Σ(j−i)




(head elements and false positives)
(tail noise)

.
(6)

Noise from heavy hitters. The first term in (6) corresponds to noise from (x − χ)S\{i} − χ[n]d \(S\{i}) , i.e.
noise from heavy hitters and false positives. For every i ∈ S, hashing H we let
X
Goi (j) |yj |, where y = (x − χ)S − χ[n]d \S .
(7)
ehead
(H, x, χ) := G−1
i
oi (i) ·
j∈S\{i}

We thus get that ehead
(H, x, χ) upper bounds the absolute value of the first error term in (6). Note that G ≥ 0 by
i
Lemma 2.3 as long as F is even, which is the setting that we are in. If ehead
(H, x, χ) is large, L OCATE S IGNAL
i
may not be able to locate i using measurements of the residual signal x− χ taken with hashing H. However, the
noise in other hashings may be smaller, allowing recovery. In order to reflect this fact we define, for a sequence
d
of hashings H1 , . . . , Hr and a signal y ∈ C[n]
head
(Hr , x, χ),
ehead
({Hr }, x, χ) := quant1/5
i
r ei

15

(8)

where for a list of reals u1 , . . . , us and a number f ∈ (0, 1) we let quantf (u1 , . . . , us ) denote the ⌈f · s⌉-th
largest element of u1 , . . . , us .
Tail noise. To capture the second term in (6) (corresponding to tail noise), we define, for any i ∈ S, z ∈
[n]d , w ∈ W, permutation π = (Σ, q) and hashing H = (π, B, F )
−1
etail
i (H, z, x) := Goi (i) ·

X

Goi (j) xj ω z

T Σ(j−i)

.

(9)

j∈[n]d \S

With this definition in place etail
i (H, z, x) upper bounds the second term in (6). As our algorithm uses
d
several values of a ∈ Ar ⊆ [n] × [n]d to perform location, a more robust version of etail
i (H, z) will be useful.
To that effect we let for any Z ⊆ [n]d (we will later use Z = Ar ⋆ (1, w) for various w ∈ W)
1/5

−1
etail
i (H, Z, x) := quantz∈Z Goi (i) ·

X

Goi (j) xj ω z

T Σ(j−i)

.

(10)

j∈[n]d \S

Note that the algorithm first selects sets Ar ⊆ [n]d ×[n]d , and then access the signal at locations Ar ⋆(1, w), w ∈
W.
The definition of etail
i (H, A⋆(1, w), x) for a fixed w ∈ W allows us to capture the amount of noise that our
measurements that use H suffer from for locating a specific set of bits of Σi. Since the algorithm requires all
w ∈ W to be not too noisy in order to succeed (see precondition 2 of Lemma 5.1), it is convenient to introduce
notation that captures this. We define
etail
i (H, A, x) := 40µH,i (x) +

X

w∈W

etail
i (H, A ⋆ (1, w), x) − 40µH,i (x)

+

(11)

where for any η ∈ R one has |η|+ = η if η > 0 and |η|+ = 0 otherwise.
The following definition is useful for bounding the norm of elements i ∈ S that are not discovered by
several calls to L OCATE S IGNAL on a sequence of hashings {Hr }. For a sequence of measurement patterns
{Hr , Ar } we let
1/5 tail
etail
(12)
i ({Hr , Ar }, x) := quantr ei (Hr , Ar , x).
Finally, for any S ⊆ [n]d we let

ehead
(·) :=
S

X

ehead
(·) and etail
i
S (·) :=

i∈S

X

etail
i (·),

i∈S

where · stands for any set of parameters as above.
Equipped with the definitions above, we now prove the following lemma, which yields sufficient conditions
for recovery of elements i ∈ S in L OCATE S IGNAL in terms of ehead and etail .
Lemma 5.1. Let H = (π, B, R) be a hashing, and let A ⊆ [n]d × [n]d . Then for every S ⊆ [n]d and for every
d
x, χ ∈ C[n] and x′ = x − χ, the following conditions hold. Let L denote the output of
L OCATE S IGNAL (χ, H, {m(b
x, H, a ⋆ (1, w))}a∈A,w∈W ).
Then for any i ∈ S such that |x′i | > N −Ω(c) , if there exists r ∈ [1 : rmax ] such that
1. ehead
(H, x′ ) < |x′i |/20;
i
16

′
′
2. etail
i (H, A ⋆ (1, w), x ) < |xi |/20 for all w ∈ W;

3. for every s ∈ [1 : d] the set A ⋆ (0, es ) is balanced in coordinate s (as per Definition 2.13),
then i ∈ L. The time taken by the invocation of L OCATE S IGNAL is O(B · logd+1 N ).
Proof. We show that each coordinate s = 1, . . . , d of Σi is successfully recovered in L OCATE S IGNAL. Let
q = Σi for convenience. Fix s ∈ [1 : d]. We show by induction on g = 0, . . . , log∆ n − 1 that after the
g-th iteration of lines 6-10 of Algorithm 1 we have that fs coincides with qs on the bottom g · log2 ∆ bits, i.e.
fs − qs = 0 mod ∆g (note that we trivially have fs < ∆g after iteration g).
The base of the induction is trivial and is provided by g = 0. We now show the inductive step. Assume
by the inductive hypothesis that fs − qs = 0 mod ∆g−1 , so that qs = fs + ∆g−1 (r0 + ∆r1 + ∆2 r2 + . . .)
for some sequence r0 , r1 , . . ., 0 ≤ rj < ∆. Thus, (r0 , r1 , . . .) is the expansion of (qs − fs )/∆g−1 base ∆, and
r0 is the least significant digit. We now show that r0 is the unique value of r that satisfies the conditions of
lines 8-10 of Algorithm 1.
First, we have by (6) together with (7) and (9) one has for each a ∈ A and w ∈ W
T
−Ω(c)
mh(i) (xb′ , H, a ⋆ (1, w)) − Goi (i) x′i ω ((a⋆(1,w)) q ≤ ehead
(H, x, χ) + etail
.
i
i (H, a ⋆ (1, w), x) + N

Since 0 ∈ W, we also have for all a ∈ A

T
−Ω(c)
mh(i) (xb′ , H, a ⋆ (1, 0)) − Goi (i) x′i ω (a⋆(1,0)) q ≤ ehead
(H, x, χ) + etail
,
i
i (H, a ⋆ (1, 0), x) + N

where the N −Ω(c) terms correspond to polynomially small error from approximate computation of the Fourier
transform via Lemma 10.2.
Let j := h(i). We will show that i is recovered from bucket j. The bounds above imply that
T
x′ ω (a⋆(1,w)) q + E ′
mj (xb′ , H, a ⋆ (1, w))
= ′i (a⋆(1,0))T q
xi ω
+ E ′′
mj (xb′ , H, a ⋆ (1, 0))

(13)

−Ω(c) and |E ′′ | ≤ ehead (H, x, χ)+
for some E ′ , E ′′ satisfying |E ′ | ≤ ehead
(H, x, χ)+etail
i
i (H, a⋆(1, w), x)+N
i
tail
−Ω(c)
ei (H, a ⋆ (1, 0)) + N
. For all but 1/5 fraction of a ∈ A we have by definition of etail (see (10)) that
both
tail
′
etail
(14)
i (H, a ⋆ (1, w), x) ≤ ei (H, A ⋆ (1, w), x) ≤ |xi |/20

and
tail
′
etail
i (H, a ⋆ (1, 0) ≤ ei (H, A ⋆ (1, 0), x) ≤ |xi |/20.

(15)

In particular, we can rewrite (13) as
T
x′ ω (a⋆(1,w)) q + E ′
mj (xb′ , H, a ⋆ (1, w))
= ′i (a⋆(1,0))T q
xi ω
+ E ′′
mj (xb′ , H, a ⋆ (1, 0))
T

=

T

ω (a⋆(1,w)) q
1 + ω −(a⋆(1,w)) q E ′ /x′i
·
ξ
where
ξ
=
ω (a⋆(1,0))T q
1 + ω −(a⋆(1,0))T q E ′′ /x′i
T q−(a⋆(1,0))T q

= ω (a⋆(1,w))
=ω

(a⋆(0,w))T q

(16)

·ξ

· ξ.

Let A∗ ⊆ A denote the set of values of a ∈ A that satisfy the bounds (14) and (15) above. We thus have
for a ∈ A∗ , combining (16) with assumptions 1-2 of the lemma, that
|E ′ |/x′i ≤ (2/20) + 1/N −Ω(c) ≤ 1/8 and
17

|E ′′ |/x′i ≤ (2/20) + 1/N −Ω(c) ≤ 1/8

(17)

for sufficiently large N , where O(c) is the word precision of our semi-equispaced Fourier transform computation. Note that we used the assumption that |x′i | ≥ N −Ω(c) .
Writing a = (α, β) ∈ [n]d × [n]d , we have by (16) that

mj (xb′ ,H,a⋆(1,w))
mj (xb′ ,H,a⋆(1,0))

Tq

= ω ((α,β)⋆(0,w))

wT q = n∆−g qs when w = n∆−g es (as in line 8 of Algorithm 1), we get

· ξ, and since

mj (xb′ , H, a ⋆ (1, w))
T
−g
−g
−g
= ω (a⋆(0,w)) q · ξ = ω n∆ βs qs · ξ = ω n∆ βs qs + ω n∆ βs qs (ξ − 1).
′
b
mj (x , H, a ⋆ (1, 0))

We analyze the first term now, and will show later that the second term is small. Since qs = fs + ∆g−1 (r0 +
∆r1 + ∆2 r2 + . . .) by the inductive hypothesis, we have, substituting the first term above into the expression
in line 10 of Algorithm 1,
−r·βs
· ω −n∆
ω∆

−g f

s ·βs

· ω n∆

−g β

s qs

−r·βs
· ω n∆
= ω∆

−r·βs
· ω n∆
= ω∆

−g (q

s −fs )·βs

−g (∆g−1 (r

0 +∆r1 +∆

−r·βs
· ω (n/∆)·(r0 +∆r1 +∆
= ω∆

2r

2r

2 +...))·βs

2 +...)·βs

r0 ·βs
−r·βs
· ω∆
= ω∆
(−r+r0 )·βs

= ω∆

.

We used the fact that ω n/∆ = e2πi(n/∆)/n = e2πi/∆ = ω∆ and (ω∆ )∆ = 1. Thus, we have
−r·βs −(n2
ω
ω∆

−g f

s )·βs

mj (xb′ , H, a ⋆ (1, w))
(−r+r0 )·βs
(−r+r0 )·βs
(ξ − 1).
+ ω∆
= ω∆
′
b
mj (x , H, a ⋆ (1, 0))

(18)

(−r+r )·β

s
0
= 1, and it remains to note that
We now consider two cases. First suppose that r = r0 . Then ω∆
1+1/8
∗
by (17) we have |ξ − 1| ≤ 1−1/8 − 1 ≤ 2/7 < 1/3. Thus every a ∈ A passes the test in line 9 of Algorithm 1.
Since |A∗ | ≥ (4/5)|A| > (3/5)|A| by the argument above, we have that r0 passes the test in line 9. It remains
to show that r0 is the unique element in 0, . . . , ∆ − 1 that passes this test.
Now suppose that r 6= r0 . Then by the assumption that A ⋆ (0, es ) is balanced (assumption 3 of the lemma)
(−r+r0 )·βs
have negative real part. This means that for at least 49/100 of a ∈ A we
at least 49/100 fraction of ω∆
have using triangle inequality
i
h
(−r+r0 )·βs
(−r+r0 )·βs
(−r+r0 )·βs
(−r+r0 )·βs
(ξ − 1)
− 1 − ω∆
(ξ − 1) − 1 ≥ ω∆
+ ω∆
ω∆

≥ |i − 1| − 1/3
√
≥ 2 − 1/3 > 1/3,

and hence the condition in line 9 of Algorithm 1 is not satisfied for any r 6= r0 . This shows that location is
successful and completes the proof of correctness.
Runtime bounds follow by noting that L OCATE S IGNAL recovers d coordinates with log n bits per coordinate. Coordinates are recovered in batches of log ∆ bits, and the time taken is bounded by B · d(log∆ n)∆ ≤
B(log N )3/2 . Updating the measurements using semi-equispaced FFT takes B logd+1 N time.
We also get an immediate corollary of Lemma 5.1. The corollary is crucial to our proof of Theorem 3.1
(the main result about efficiency of L OCATE S IGNAL) in the next section.
Corollary 5.2. For any integer rmax ≥ 1, for any sequence of rmax hashings Hr = (πr , B, R), r ∈ [1 : rmax ]
d
and evaluation points Ar ⊆ [n]d ×[n]d , for every S ⊆ [n]d and for every x, χ ∈ C[n] , x′ := x−χ, the following
18

conditions hold. If for eachS
r ∈ [1 : rmax ] Lr ⊆ [n]d denotes the output of L OCATE S IGNAL(b
x , χ, Hr , {m(b
x, Hr , a⋆
rmax
(1, w))}a∈Ar ,w∈W ), L = r=1 Lr , and the sets Ar ⋆ (0, w) are balanced for all w ∈ W and r ∈ [1 : rmax ],
then
−Ω(c)
||x′S\L ||1 ≤ 20||ehead
({Hr }, x, χ)||1 + 20||etail
.
(*)
S
S ({Hr , Ar }, x)||1 + |S| · N
Furthermore, every element i ∈ S such that
−Ω(c)
|x′i | > 20(ehead
({Hr }, x, χ) + etail
i
i ({Hr , Ar }, x)) + N

(**)

belongs to L.
Proof. Suppose that i ∈ S fails to be located in any of the R calls, and |x′i | ≥ N −Ω(c) . By Lemma 5.1 and the
assumption that Ar ⋆ (0, w) is balanced for all w ∈ W and r ∈ [1 : rmax ] this means that for at least one half
of values r ∈ [1 : rmax ] either (A) ehead
(Hr , x, χ) ≥ |xi |/20 or (B) etail
i
i (Hr , Ar ⋆ (1, w), x) > |xi |/20 for at
least one w ∈ W. We consider these two cases separately.
(Hs , x, χ) ≥ |xi |/20 for at least one half of r ∈ [1 : rmax ], so in
Case (A). In this case we have ehead
i
1/5 head
head
particular ei ({Hr }, x, χ) ≥ quantr ei (Hr , x, χ) ≥ |x′i |/20.
′
Case (B). Suppose that etail
i (Hr , Ar ⋆ (1, w), x) > |xi |/20 for some w = w(r) ∈ W for at least one half of
r ∈ [1 : rmax ] (denote this set by Q ⊆ [1 : rmax ]). We then have
1/5

tail
etail
i ({Hr , Ar }, x) = quantr∈[1:rmax ] ei (Hr , Ar , x)
"

=

1/5
quantr∈[1:rmax ]



40µHr ,i (x) +

X

w∈W

etail
i (Hr , Ar

⋆ (1, w), x) − 40µHr ,i (x)

≥ min 40µHr ,i (x) + etail
i (Hr , Ar ⋆ (1, w(r)), x) − 40µHr ,i (x)
r∈Q

≥
≥

min etail
i (Hr , Ar
r∈Q
|x′i |/20

⋆ (1, w(r)), x)

+



+

#

as required. This completes the proof of (*) as well as (**).

6 Analysis of L OCATE S IGNAL: bounding ℓ1 norm of undiscovered elements
The main result of this section is Theorem 3.1, which is our main tool for showing efficiency of L OCATE S IG NAL. Theorem 3.1 applies to the following setting. Fix a set S ⊆ [n]d and a set of hashings H1 , . . . , Hrmax ,
and let S ∗ ⊆ S denote the set of elements of S that are not isolated with respect to most of these hashings
H1 , . . . , Hrmax . Theorem 3.1 shows that for any signal x and partially recovered signal χ, if L denotes the
output list of an invocation of L OCATE S IGNAL on the pair (x, χ) with hashings H1 , . . . , Hrmax , then the ℓ1
norm of elements of the residual (x − χ)S that are not discovered by L OCATE S IGNAL can be bounded by a
function of the amount of ℓ1 mass of the residual that fell outside of the ‘good’ set S \ S ∗ , plus the ‘noise level’
µ ≥ ||x[n]d \S ||∞ times k.
If we think of applying Theorem 3.1 iteratively, we intuitively get that the fixed set of measurements with
hashings {Hr } allows us to always reduce the ℓ1 norm of the residual x′ = x − χ on the ‘good’ set S \ S ∗ to
about the amount of mass that is located outside of this good set.
Theorem 3.1 There exist absolute constants C1 , C2 , C3 > 0 such that for any x, χ ∈ CN and residual signal
x′ = x − χ the following conditions hold. Let S ⊆ [n]d , |S| ≤ 2k, be such that ||x[n]d \S ||∞ ≤ µ. Suppose that
19

||x||∞ /µ ≤ N O(1) . Let B ≥ (2π)4d·F · k/αd . Let S ∗ ⊆ S denote the set of elements that are not isolated with
√
max
. Suppose that for every s ∈ [1 : d] the sets Ar ⋆ (0, es )
respect to at least a α fraction of hashings {Hr }rr=1
are balanced (as per Definition 2.13), r = 1, . . . , rmax , and the exponent F of the filter G is even and satisfies
F ≥ 2d. Let
r[
max
L OCATE S IGNAL (χ, Hr , {m(b
x, Hr , a ⋆ (1, w)}a∈Ar ,w∈Wr ).
L=
r=1

√
Then if rmax , cmax ≥ (C1 / α) log log N , one has

2

||x′S\S ∗ \L ||1 ≤ (C2 α)d/2 ||x′S ||1 + C3d (||χ[n]d \S ||1 + ||x′S ∗ ||1 ) + 4µ|S|.
As we will show later, Theorem 3.1 can be used to show that (assuming perfect estimation) invoking L O repeatedly allows one to reduce to ℓ1 norm of the head elements down to essentially

CATE S IGNAL

||x′S ∗ ||1 + ||χ[n]d \S ||1 ,
i.e. the ℓ1 norm of the elements that are not well isolated and the set of new elements created by the process
due to false positives in location. In what follows we derive bounds on ||ehead ||1 (in section 6.1) and ||etail ||1
(in section 6.2) that lead to a proof of Theorem 3.1.

6.1 Bounding noise from heavy hitters
We first derive bounds on noise from heavy hitters that a single hashing H results in, i.e. ehead (H, x), (see
Lemma 6.1), and then use these bounds to bound ehead ({H}, x) (see Lemma 6.3). These bounds, together with
upper bounds on contribution of tail noise from the next section, then lead to a proof of Theorem 3.1.
Lemma 6.1. Let x, χ ∈ CN , x′ = x − χ. Let S ⊆ [n]d , |S| ≤ 2k, be such that ||x[n]d \S ||∞ ≤ µ. Suppose that
||x||∞ /µ ≤ N O(1) . Let B ≥ (2π)4d·F · k/αd . Let π = (Σ, q) be a permutation, let H = (π, B, F ), F ≥ 2d be
∗ ⊆ S denote the set of elements i ∈ S that are
a hashing into B buckets and filter G with sharpness F . Let SH
head
not isolated under H. Then one has, for e
defined with respect to S,
O(d) d/2
α ||x′S\S ∗ ||1 + (2π)d·F · 2O(d) (||x′S ∗ ||1 + ||χ[n]d \S ||1 ).
||ehead
S\S ∗ (H, x, χ)||1 ≤ 2
H

H

∗ = ∅, then one has ||ehead (H, x, χ)||
O(d) αd/2 ||x′ || .
Furthermore, if χ[n]d \S = 0 and SH
∞ ≤2
S
S ∞
∗
Proof. By (7) for i ∈ S \ SH
X
|
·
(H, x′ ) = |G−1
ehead
i
oi (i)

∗ \{i}
j∈S\SH




+ |G−1
oi (i) | ·
=

|G−1
oi (i) |

X

∗
j∈SH

|Goi (j) |x′j |

|Goi (j) |x′j | +

(isolated head elements)
X

j∈[n]d \S

· (A1 (i) + A2 (i)).



|Goi (j) ||χj | (non-isolated head elements and false positives)
(19)

P
P
Let A1 := i∈S\S ∗ A1 (i), A2 := i∈S\S ∗ A2 (i).
H
H
We bound A1 and A2 separately.

20

Bounding A1 . We start with a convenient upper bound on A1 :
X
X
|Goi (j) ||x′j |
(recall that oi (j) = π(j) − (n/b)h(i))
A1 =
∗ j∈S\S ∗ \{i}
i∈S\SH
H

=

X X

∗
t≥0 i∈S\SH

≤
=

X X

∗
j∈S\SH

∗ \{i} s.t.
j∈S\SH
||π(j)−π(i)||∞ ∈(n/b)·[2t −1,2t+1 −1)

max

∗
t≥0 i∈S\SH

X

X

||π(j)−π(i)||∞ ≥(n/b)·(2t −1)

|x′j | ·

X
t≥0

max

||π(j)−π(i)||∞ ≥
(n/b)·(2t −1)

|Goi (j) ||x′j |, (consider all scales t ≥ 0)

Goi (j) ·

Goi (j) ·

X

∗ \{i} s.t.
j∈S\SH
||π(j)−π(i)||∞ ≤(n/b)·(2t+1 −1)

|x′j |


∗
i ∈ S \ SH
\ {j} s.t. ||π(j) − π(i)||∞ ≤ (n/b) · (2t+1 − 1)
(20)

∗
S \ SH

Note that in the first line we summed, over all i ∈
(i.e. all isolated i), the contributions of all other i ∈ S
to the noise in their buckets. We need to bound the first line in terms of ||x′S\S ∗ ||1 . For that, we first classified
H
∗ according to the ℓ
all j ∈ S \ SH
∞ distance from i to j (in the second line), then upper bounded the value of
the filter Goi (j) based on the distance ||π(i) − π(j)||∞ , and finally changed order of summation to ensure that
∗ 3 . In order to upper bound
the outer summation is a weighted sum of absolute values of x′j over all j ∈ S \ SH
′
A1 it now suffices to upper bound all factors multiplying xj in the last line of the equation above. As we now
show, a strong bound follows from isolation properties of i.
We start by upper bounding G using Lemma 2.3, (2). We first note that by triangle inequality
||π(j)− (n/b)h(i)||∞ ≥ ||π(j)− π(i)||∞ − ||π(i)− (n/b)h(i)||∞ ≥ (n/b)(2t − 1)− (n/b) = (n/b)(2t−1 − 2).

The rhs is positive for all t ≥ 3 and for such t satisfies 2t−1 − 2 ≤ 2t−2 . We hence get for all t ≥ 3
F 
F

2
2
≤
≤ 2−(t−3)F .
max
Goi (j) ≤
1 + ||π(j) − (n/b)h(i)||∞
1 + 2t−2
||π(j)−π(i)||∞ ≥(n/b)·(2t−1 −1)

(21)

We also have the bound ||G||∞ ≤ 1 from Lemma 2.3, (3). It remains to bound the last term on the rhs of the
last line in (20). We need the fact that for a pair i, j such that ||π(j) − π(i)||∞ ≤ 2t+1 − 1 we have by triangle
inequality
||π(j) − (n/b)h(i)||∞ ≤ ||π(j) − π(i)||∞ + ||π(i) − (n/b)h(i)||∞ ≤ (n/b)(2t+1 − 1) + (n/b) = (n/b)2t+1 .

Equipped with this bound, we now conclude that

∗
i ∈ S \ SH
\ {j} s.t. ||π(j) − π(i)||∞ ≤ (n/b) · (2t+1 − 1)

t+1
= |π(S \ {i}) ∩ B∞
)| ≤ (2π)−d·F · αd/2 2(t+2)d+1 · 2t ,
(n/b)h(i) ((n/b) · 2

(22)

∗ are isolated (see Definition 2.10). We thus get for any j ∈ S \S ∗
where we used the assumption that i ∈ S \SH
H
X

∗
t+1
Goi (j) · i ∈ S \ SH \ {j} s.t. ||π(j) − π(i)||∞ ≤ (n/b) · (2
− 1)
ηj :=
max
t≥0

≤

||π(j)−π(i)||∞ ≥
(n/b)·(2t −1)

X
t≥0

((2π)−d·F · αd/2 2(t+2)d+1 · 2t ) min{1, 2−(t−3)F }

≤ (2π)−d·F · αd/2 22d+1

X
t≥0

2t(d+1) · min{1, 2−(t−3)F }

3

We note here that we started by summing over i first and then over j, but switched the order of summation to the opposite in the
last line. This is because the quantity Goi (j) , which determines contribution of j ∈ S to the estimation error of i ∈ S is not symmetric
in i and j. Indeed, even though G itself is symmetric around the origin, we have oi (j) = π(j) − (n/b)h(i) 6= oj (i).

21

.

We now note that
X
X
2(t−3)(d+1) · min{1, 2−(t−3)F }
2t(d+1) · min{1, 2−(t−3)F } = 1 + 22(d+1) + 23(d+1)
t≥3

t≥0

2(d+1)

=1+2

3(d+1)

+2

X
t≥3

2(t−3)(d+1−F ) ≤ 1 + 22(d+1) + 23(d+1)+1 ≤ 24(d+1)+1 ,

∗ one has η ≤ (2π)−d·F · 2O(d) αd/2 .
since F ≥ 2d by assumption of the lemma, and hence for all j ∈ S \ SH
j
Combining the estimates above, we now get
X
|x′j | · ηj ≤ ||x′S ||1 (2π)−d·F · 2O(d) αd/2 ,
A1 ≤
∗
j∈S\SH

as required. The ℓ∞ bound for the case when χ[n]d \S = 0 follows in a similar manner and is hence omitted.
We now turn to bounding A2 . The bound that we get here is weaker since χ[n]d \S is an adversarially placed
signal and we do not have isolation properties with respect to it, resulting in a weaker bound on (the equivalent
∗ than we had for j ∈ S \ S ∗ . We let y := x′ − χ
of) ηj for j ∈ SH
[n]d \S to simplify notation. We have, as
H
S∗
in (20),
X
|x′j | · κj ,
A2 ≤
∗
j∈S\SH

where
X
κj =

max

||π(j)−π(i)||∞ ≥
t≥0
(n/b)·(2t −1)

Goi (j) ·



∗
i ∈ S \ SH
\ {j} s.t. ||π(j) − π(i)||∞ ≤ (n/b) · (2t+1 − 1)

.

The first term can be upper bounded as before. For the second term, we note that every pair of points i1 , i2 ∈
∗ by triangle inequality satisfy
S \ SH
(n/b)||π(i1 ) − π(i2 )||∞ ≤ (n/b)||π(i1 ) − π(j)||∞ + ||π(j) − π(i2 )||∞ ≤ (n/b) · (2t+2 − 2) ≤ (n/b) · 2t+2

Since both i1 and i2 are isolated under π, this means that

∗
i ∈ S \ SH
\ {j} s.t. ||π(j) − π(i)||∞ ≤ (n/b) · (2t+1 − 1)

≤ (2π)−d·F · αd/2 2(t+3)d · 2t+2 + 1,

where we used the bound from Definition 2.10 for i, but counted the point i itself (this is what makes the bound
on κj weaker than the bound on ηj ). A similar calculation to the one above for A1 now gives
X

∗
Goi (j) · i ∈ S \ SH
\ {j} s.t. ||π(j) − π(i)||∞ ≤ (n/b) · (2t+1 − 1)
κj :=
max
t≥0

≤

||π(j)−π(i)||∞ ≥
(n/b)·(2t −1)

X
((2π)−d·F · αd/2 2(t+3)d · 2t+2 + 1) min{1, 2−(t−3)F }
t≥0

≤ 2O(d) ((2π)−d·F · αd/2 + 1) = 2O(d) .
We thus have
A2 ≤

X

j∈[n]d

|yj |κj ≤ 2O(d) ||y||1 .

Plugging our bounds on A1 and A2 into (19), we get
O(d)
−1
(2π)−d·F · αd/2 ||x′S ||1 + 2O(d) ||y||1 )
ehead
(H, x, χ) ≤ |G−1
i
oi (i) | · (A1 + A2 ) ≤ |Goi (i) |(2

≤ 2O(d) αd/2 ||x′S ||1 + (2π)d·F · 2O(d) ||y||1

as required.

22

Remark 6.2. The second bound of this lemma will be useful later in section 8.1 for analyzing R EDUCE I NF N ORM.
We now bound the final error induced by head elements, i.e. ehead ({Hr }, x, χ):
Lemma 6.3. Let x, χ ∈ [n]d , x′ = x − χ. Let S ⊆ [n]d , |S| ≤ 2k, be such that ||x[n]d \S ||∞ ≤ µ. Suppose that
max
be a set of permutations, let Hr = (πr , B, F ), F ≥
||x||∞ /µ ≤ N O(1) . Let B ≥ (2π)4d·F · k/αd . Let {πr }rr=1
2d be a hashing into B buckets and filter G with sharpness F . Let S ∗ denote the set of elements i ∈ S that are
√
not isolated under at least α fraction of Hr . Then, one has for ehead defined with respect to S,
O(d) d/2
||ehead
α ||x′S ||1 + (2π)d·F · 2O(d) ||χ[n]d \S ||1 .
S\S ∗ ({Hr }, x, χ)||1 ≤ 2
d/2 αd/2 ||x′ || .
Furthermore, if χ[n]d \S = 0, then ||ehead
S ∞
S\S ∗ ({Hr }, x, χ)||∞ ≤ 2
1/5

(Hr , x, χ). This
Proof. Recall that by (8) one has for each i ∈ [n]d ehead
({Hr }, x, χ) = quantr∈[1:rmax ] ehead
i
i
√
∗
head
means that for each i ∈ S \ S there exist at least (1/5 − α)rmax values of r such that ei (Hr , x, χ) >
ehead
({Hr }, x, χ), and hence
i
||ehead
S\S ∗ ({Hr }, x, χ)||1 ≤

(1/5 −

1
√

α)rmax

rX
max
r=1

||ehead
S\Sr∗ (Hr , x, χ)||1 .

By Lemma 6.1 one has
O(d) d/2
α ||x′S ||1 + (2π)d·F · 2O(d) ||χ[n]d \S ||1
||ehead
S\S ∗ (Hr , x, χ)||1 ≤ 2
Hr

for all r, implying that
||ehead
S\S ∗ ({Hr }, x, χ)||1 ≤

1
√ (2O(d) αd/2 ||x′S ||1 + (2π)d·F · 2O(d) ||χ[n]d \S ||1 )
(1/5 − α)

≤ 2O(d) αd/2 ||x′S ||1 + (2π)d·F · 2O(d) ||χ[n]d \S ||1

as required.
The proof of the second bound follows analogously using the ℓ∞ bound from Lemma 6.1.
Remark 6.4. The second bound of this lemma will be useful later in section 8.1 for analyzing R EDUCE I NF N ORM.

6.2 Bounding effect of tail noise
d

[n]
Lemma 6.5. For any constant C ′ > 0 there exists an absolute constant C
√ > 0 such that for any x ∈ C ,
d
′
any integer k ≥ 1 and S ⊆ [n] such that ||x[n]d \S ||∞ ≤ C ||x[n]d \[k] ||2 / k, for any integer B ≥ 1 a power
of 2d the following conditions hold. If (H, A) are random measurements as in Algorithm 2, H = (π, B, F )
satisfies F ≥ 2d and ||x[n]d \[k] ||2 ≥ N −Ω(c) , where O(c) is the word precision of our semi-equispaced Fourier
transform computation, then for any i ∈ [n]d one has, for etail defined with respect to S,
h
i
√
d·F
d
−Ω(|A|)
B.
(H,
A,
x)
≤
(2π)
·
C
(40
+
|W|2
)||x
||
/
EH,A etail
d
2
i
[n] \[k]

23

Proof. Recall that for any H = (π, B, G), a, w one has (etail (H, a ⋆ (1, w), x[n]d \[k] ))2 = |ui |2 , where
u = H ASH T O B INS (x\
[n]d \S , 0, (H, a ⋆ (1, w))).
Since the elements of A are selected uniformly at random, we have for any H and w by Lemma 2.9, (3),
since a ⋆ (1, w) is uniformly random in [n]d , that
T Σi

−1
−(a⋆(1,w))
2
Ea [(etail
i (H, a ⋆ (1, w), x)) ] = Ea [|Goi (i) ω

uh(i) − xi |2 ] ≤ µ2H,i (x) + N −Ω(c) ,

(23)

where c > 0 is the large constant that governs the precision of our Fourier transform computations. By
Lemma 2.9, (2) applied to the pair (x\
[n]d \S , 0) there exists a constant C > 0 such that
EH [µ2H,i ] ≤ (2π)2d·F · C d ||x[n]d \S ||22 /B
We would like to upper bound the rhs in terms of ||x[n]d \[k] ||22 (the tail energy), but this requires an argument
since S is not exactly the set of top k elements of x. However, since S contains the large coefficients of x, a
bound is easy to obtain. Indeed, denoting the set of top k coefficients of x by [k] ⊆ [n]d as usual, we get
||x[n]d \S ||22 ≤ ||x[n]d \(S∪[k]) ||22 + ||x[k]\S ||22 ≤ ||x[n]d \[k] ||22 + k · ||x[k]\S ||2∞ ≤ (C ′ + 1)||x[n]d \[k] ||2 .
Thus, we have
EH [µ2H,i (x) + N −Ω(c) ] ≤ (2π)2d·F · (C ′ + 2)C d ||x[n]d \[k] ||22 /B,
where we used the assumption that ||x[n]d \k ||2 ≥ N −Ω(c) . We now get by Jensen’s inequality
√
EH [µH,i (x)] ≤ (2π)d·F · (C ′′ )d ||x[n]d \k ||2 / B

(24)

for a constant C ′′ > 0. Note that
By (23) for each i ∈ [n]d , hashing H, evaluation point a ∈ [n]d × [n]d and direction w we have
2
2
Ea [(etail
i (H, a ⋆ (1, w), x)) ] = (µH,i (x)) . Applying Jensen’s inequality, we hence get for any H and w ∈ W
Ea [etail
i (H, a ⋆ (1, w), x)] ≤ µH,i (x).

(25)

tail
Applying Lemma 9.5 with Y = etail
i (H, a ⋆ (1, w), x) and γ = 1/5 (recall that the definition of ei (H, z, x)
involves a 1/5-quantile over A) and using the previous bound, we get, for any fixed H and w ∈ W


tail
EA ei (H, A ⋆ (1, w), x) − 40 · µH,i (x)
≤ µH,i (x) · 2−Ω(|A|) ,
(26)
+

and hence by a union bound over all w ∈ W we have
#
"
X
tail
≤ µH,i (x) · |W|2−Ω(|A|) .
ei (H, A ⋆ (1, w), x) − 40 · µH,i (x)
EA
+

w∈W

Putting this together with (24), we get
h
i
(H,
A,
x)
EH,A etail
i
"
"

= EH EA 40µH,i (x) +

≤ EH

h

X

w∈W

etail
i (H, A ⋆ (1, w), x) − 40 · µH,i (x)

i
µH,i (x)(40 + |W|2−Ω(|A|) )

√
≤ (2π)d·F (C ′′ )d (40 + |W|2−Ω(|A|) )||x[n]d \k ||2 / B
as required.
24

+

##

d

Lemma 6.6. For any constant C ′ > 0 there exists an absolute constant
C > 0 such that for any x ∈ C[n] , any
√
integer k ≥ 1 and S ⊆ [n]d such that ||x[n]d \S ||∞ ≤ C ′ ||x[n]d \[k] ||/ k, if B ≥ 1, then the following conditions
hold , for etail defined with respect to S.
If hashings Hr = (πr , B, F ), F ≥ 2d and sets Ar , |Ar | ≥ cmax for r = 1, . . . , rmax are chosen at random,
then
(1) for every i ∈ [n]d one has
h
i
√
({H
,
A
},
x)
≤ (2π)d·F C d (40 + |W|2−Ω(cmax ) )||x[n]d \[k] ||2 / B.
E{(Hr ,Ar )} etail
r
r
i
(2) for every i ∈ [n]d one has
h
√ i
d·F d
C (40 + |W|2−Ω(cmax ) )||x[n]d \[k] ||2 / B = 2−Ω(rmax )
Pr{(Hr ,Ar )} etail
i ({Hr , Ar }, x) > (2π)
and

E{(Hr ,Ar )}



etail
i ({Hr , Ar }, x)

d·F

− (2π)

d

−Ω(cmax )

C (40 + |W|2

√
= 2−Ω(rmax ) · (2π)d·F C d (40 + |W|2−Ω(cmax ) )||x[n]d \[k] ||2 / B.

√
)||x[n]d \[k] ||2 / B

+



Proof. Follows by applying Lemma 9.5 with Y = etail
i (Hr , Ar , x).

6.3 Putting it together
The bounds from the previous two sections yield a proof of Theorem 3.1, which we restate here for convenience
of the reader:
Theorem 3.1 For any constant C ′ > 0 there exist absolute constants C1 , C2 , C3 > 0 such that √
for any
d
x ∈ C[n] , any integer k ≥ 1 and any S ⊆ [n]d such that ||x[n]d \S ||∞ ≤ C ′ µ, where µ = ||x[n]d \[k] ||2 / k, the
following conditions hold.
Let πr = (Σr , qr ), r = 1, . . . , rmax denote permutations, and let Hr = (πr , B, F ), F ≥ 2d, where
B ≥ (2π)4d·F k/αd for α ∈ (0, 1) smaller than a constant. Let S ∗ ⊆ S denote the set of elements that are not
√
√
isolated with respect to at least a α fraction of hashings {Hr }. Then if rmax , cmax ≥ (C1 / α) log log N ,
d
then with probability at least 1 − 1/ log2 N over the randomness of the measurements for all χ ∈ C[n] such
that x′ := x − χ satisifies ||x′ ||∞ /µ ≤ N O(1) one has
L :=

r[
max
r=1



max
L OCATE S IGNAL χ, k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W

satisfies

2

||x′S\S ∗ \L ||1 ≤ (C2 α)d/2 ||x′S ||1 + C3d (||χ[n]d \S ||1 + ||x′S ∗ ||1 ) + 4µ|S|.
Proof. First note that with probability at least 1 − 1/(10 log 2 N ) for every s ∈ [1 : d] the sets Ar ⋆ (0, es ) are
balanced (as per Definition 2.13) for all r = 1, . . . , rmax and all w ∈ W by Claim 2.14.
By Corollary 5.2 applied with S ′ = S \ S ∗ one has
′
tail
({Hr , Ar }, x)||1 ) + ||x′ ||∞ |S| · N −Ω(c) .
||(x − χ)(S\S ∗ )\L ||1 ≤ 20 · (||ehead
S\S ∗ ({Hr }, x )||1 + ||e

We also have
′
O(d) d/2
α ||x′S ||1 + (2π)d·F · 2O(d) ||χ[n]d \S ||1
||ehead
S\S ∗ ({Hr }, x )||1 ≤ 2

25

by Lemma 6.3 and with probability at least 1 − 1/(10 log 2 N )

√
d·F d
−Ω(cmax )
B
({H
,
A
},
x)||
≤
(2π)
C
(40
+
|W|2
)||x
||
|S|/
||etail
d
∗
r
r
1
2
[n] \[k]
S\S

by Lemma 6.6. The rhs of the previous equation is bounded by |S|µ by the choice of B as long as α is smaller
than a absolute constant, as required. Putting these bounds together and using the fact that |W| ≤ log N (so that
|W| · (2−Ω(rmax ) + 2−Ω(cmax ) ) ≤ 1), and taking a union bound over the failure events, we get the result.

7 Analysis of R EDUCE L1N ORM and S PARSE FFT
In this section we first give a correctness proof and runtime analysis for R EDUCE L1N ORM (section 7.1), then
analyze the SNR reduction loop in S PARSE FFT(section 7.2) and finally prove correctness of S PARSE FFT and
provide runtime bounds in section 7.3.

7.1 Analysis of R EDUCE L1N ORM
The main result of this section is Lemma 3.2 (restated below). Intuitively, the lemma shows that R EDU CE L1N ORM reduces the ℓ1 norm of the head elements of the input signal x − χ by a polylogarthmic factor, and
does not introduce too many new spurious elements (false positives) in the process. The introduced spurious
elements, if any, do not contribute much ℓ1 mass to the head of the signal. Formally, we show
Lemma 3.2(Restated) For any x ∈ CN , any integer k ≥ 1, B ≥ (2π)4d·F · k/αd for α ∈ (0, 1] smaller than an
absolute constant and F ≥ 2d, F = Θ(d) the following conditions hold for the set S := {i ∈ [n]d : |xi | > µ},
where µ2 ≥ ||x[n]d \[k] ||22 /k. Suppose that ||x||∞ /µ = N O(1) .
For any sequence of hashings Hr = (πr , B, F ), r = 1, . . . , rmax , if S ∗ ⊆ S denotes the set of elements of
√
S that are not isolated with respect to at least a α fraction of the hashings Hr , r = 1, . . . , rmax , then for any
d
χ ∈ C[n] , x′ := x − χ, if ν ≥ (log4 N )µ is a parameter such that
A ||(x − χ)S ||1 ≤ (ν + 20µ)k;
B ||χ[n]d \S ||0 ≤

1
k;
log19 N

C ||(x − χ)S ∗ ||1 + ||χ[n]d \S ||1 ≤

ν
k,
log4 N

the following conditions hold.
√
If parameters rmax , cmax are chosen to be at least (C1 / α) log log N , where C1 is the constant from
Theorem 3.1 and measurements are taken as in Algorithm 2, then the output χ′ of the call
max
, 4µ(log 4 n)T −t , µ)
R EDUCE L1N ORM (χ, k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W

satisfies
1. ||(x′ − χ′ )S ||1 ≤

1
νk
log4 N

+ 20µk

2. ||(χ + χ′ )[n]d \S ||0 ≤ ||χ[n]d \S ||0 +

(ℓ1 norm of head elements is reduced by ≈ log4 N factor)
1
k
log20 N

(few spurious coefficients are introduced)

3. ||(x′ − χ′ )S ∗ ||1 + ||(χ + χ′ )[n]d \S ||1 ≤ ||x′S ∗ ||1 + ||χ[n]d \S ||1 +
coefficients does not grow fast)

1
νk
log20 N

(ℓ1 norm of spurious

with probability at least 1 − 1/ log2 N over the randomness used to take measurements m and by calls to E S 2
TIMATE VALUES . The number of samples used is bounded by 2O(d ) k(log log N )2 , and the runtime is bounded
2
by 2O(d ) k logd+2 N .
Before giving the proof of Lemma 3.2, we prove two simple supporting lemmas.
26

Lemma 7.1 (Few spurious elements are introduced in R EDUCE L1N ORM). For any x ∈ CN , any integer k ≥ 1,
B ≥ (2π)4d·F · k/αd for α ∈ (0, 1] smaller than an absolute constant and F ≥ 2d, F = Θ(d) the following
conditions hold for the set S := {i ∈ [n]d : |xi | > µ}, where µ2 ≥ ||x[n]d \[k] ||22 /k.
For any sequence of hashings Hr = (πr , B, F ), r = 1, . . . , rmax , if S ∗ ⊆ S denotes the set of elements of
√
S that are not isolated with respect to at least a α fraction of the hashings Hr , r = 1, . . . , rmax , then for any
d
χ ∈ C[n] , x′ := x − χ the following conditions hold.
Consider the call
max
, 4µ(log 4 n)T −t , µ),
R EDUCE L1N ORM (χ, k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W

where we assume that measurements of x are taken as in Algorithm 2. Denote, for each t = 0, . . . , log2 (log4 N ),
the signal recovered by step t in this call by χ(t) (see Algorithm 3). There exists an absolute constant C > 0
such that if for a parameter ν ≥ 2t µ at step t
A ||(x′ − χ(t) )S ||1 ≤ (2−t ν + 20µ)k;
B ||(χ + χ(t) )[n]d \S ||0 ≤

2
k,
log19 N

C ||(x′ − χ(t) )S ∗ ||1 + ||(χ + χ(t) )[n]d \S ||1 ≤

2ν
k,
log4 N

then with probability at least 1 − (log N )−3 over the randomness used in E STIMATE VALUES at step t one has
||(χ + χ(t+1) )[n]d \S ||0 − ||(χ + χ(t) )[n]d \S ||0 ≤

1
log

21

N

k.

Proof. Recall that L′ ⊆ L is the list output by E STIMATE VALUES. We let
n
o
L′′ = i ∈ L : |χ′i − x′i | > α1/2 2−t ν + 20µ


denote the set of elements in L′ that failed to be estimated to within an additive α1/2 2−t ν + 20µ error term.
For any element i ∈ L we consider two cases, depending on whether i ∈ L′ \ L′′ or i ∈ L′′ .

Case 1: First suppose that i ∈ L′ \ L′′ , i.e. |x′i − χ′i | < α1/2 (2−t ν + 20µ). Then if α is smaller than an
absolute constant, we have
|x′i | >

1
ν2−t + 4µ − (α1/2 (2−t ν + 20µ)) ≥ 2µ,
1000

because only elements i with |χ′i | >

1
−t
1000 ν2

+ 4µ are included in the set L′ in the call

χ′ ← E STIMATE VALUES (x, χ(t) , L, k, ǫ, C(log log N + d2 + O(log(B/k))),

1
ν2−t + 4µ)
1000

1
due to the pruning threshold of 1000
ν2−t + 4µ passed to E STIMATE VALUES in the last argument.
Since ||x[n]d \S ||∞ ≤ µ by definition of S, this means that either i ∈ S, or i ∈ supp χ(t) . In both cases i
contributes at most 0 to ||(χ + χ(t+1) )[n]d \S ||0 − ||(χ + χ(t) )[n]d \S ||0 .

27

Case 2: Now suppose that i ∈ L′′ , i.e. |(x′ − χ′ )i | ≥ α1/2 (2−t ν + 20µ). In this case i may contribute 1
to ||(χ + χ(t+1) )[n]d \S ||0 − ||(χ + χ(t) )[n]d \S ||0 . However, the number of elements in L′′ is small. To show
this, we invoke Lemma 9.1 to obtain precision guarantees for the call to E STIMATE VALUES on the pair x, χ
and set of ‘head elements’ S ∪ supp χ. Note that |S| ≤ 2k, as otherwise we would have ||x[n]d \[k] ||22 > µ · k,
a contradiction. Further, by assumption B of the lemma we have ||(χ + χ(t) )[n]d \S ||0 ≤ k, so |S ∪ supp(χ +
χ(t) )| ≤ 4k. The ℓ1 norm of x′ − χ(t) on S ∪ supp(χ + χ(t) ) can be bounded as
||(x′ − χ(t) )S ||1 + ||(x′ − χ(t) )supp(χ+χ(t) )\S ||1
4k

(t)

≤
≤

||(x′ − χ(t) )S ||1 + ||χ[n]d \S ||1 + ||x′[n]d \S ||∞ · | supp(χ + χ(t) )|
(2−t ν

+ 20µ)k +

2ν
k
log4 N

2k

4k
+ µ · (4k)

≤ 2−t ν + 20µ,

For the ℓ2 bound on the tail of the signal we have
||(x′ − χ(t) )[n]d \(S∪supp(χ+χ(t) )) ||22
4k

≤

||x[n]d \S ||22
4k

≤ µ2 .

We thus have by Lemma 9.1, (1) for every i ∈ L′ that the estimate wi returned by E STIMATE VALUES
satisfies
Pr[|wi − x′i | > α1/2 (2−t ν + 20µ)] < 2−Ω(rmax ) .

Since rmax is chosen as rmax = C(log log N + d2 + log(B/k)) for a sufficiently large absolute constant
C > 0, we have
Pr[|wi − x′i | > α1/2 (2−t ν + 20µ)] < 2−Ω(rmax ) ≤ (k/B) · (log N )−25 .
This means that
E[|L′′ |] ≤ |L| · (k/B) · (log N )−25 ≤ (B · rmax )(k/B) · (log N )−25 ≤ (log N )−23 ,
where the expectation is over the randomness used in E STIMATE VALUES. We used the fact that |L′ | ≤ |L| ≤
B · rmax and that rmax to derive the upper bound above. An application of Markov’s inequality completes the
proof.
Lemma 7.2 (Spurious elements do not introduce significant ℓ1 error). For any x ∈ CN , any integer k ≥ 1,
B ≥ (2π)4d·F · k/αd for α ∈ (0, 1] smaller than an absolute constant and F ≥ 2d, F = Θ(d) the following
conditions hold for the set S := {i ∈ [n]d : |xi | > µ}, where µ2 ≥ ||x[n]d \[k] ||22 /k.
For any sequence of hashings Hr = (πr , B, F ), r = 1, . . . , rmax , if S ∗ ⊆ S denotes the set of elements of
√
S that are not isolated with respect to at least a α fraction of the hashings Hr , r = 1, . . . , rmax , then for any
d
χ ∈ C[n] , x′ := x − χ the following conditions hold.
Consider the call
max
, 4µ(log 4 n)T −t , µ),
R EDUCE L1N ORM (χ, k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W

where we assume that measurements of x are taken as in Algorithm 2. Denote, for each t = 0, . . . , log2 (log4 N ),
the signal recovered by step t in this call by χ(t) (see Algorithm 3). There exists an absolute constant C > 0
such that if for a parameter ν ≥ 2t µ at step t
A ||(x′ − χ(t) )S ||1 ≤ (2−t ν + 20µ)k;
B ||(χ + χ(t) )[n]d \S ||0 ≤

2
k;
log19 N

28

C ||(x′ − χ(t) )S ∗ ||1 + ||(χ + χ(t) )[n]d \S ||1 ≤

2ν
k,
log4 N

then with probability at least 1 − (log N )−3 over the randomness used in E STIMATE VALUES at step t one has
||(x′ − χ(t+1) )([n]d \S)∪S ∗ ||1 − ||(x′ − χ(t) )([n]d \S)∪S ∗ ||1 ≤

1
k(ν + µ)
log21 N

Proof. We let Q := ([n]d \ S) ∪ S ∗ to simplify notation, and recall that L′ ⊆ L is the list output by E STIMATE VALUES. We let
n
o
L′′ = i ∈ L : |χ′i − x′i | > α1/2 2−t ν + 20µ

denote the set of elements in L′ that failed to be estimated to within an additive α1/2 2−t ν + 20µ error term.
We write
||(x − χ(t+1) )Q ||1 = ||(x − χ(t+1) )Q\L′ ||1 + ||(x − χ(t+1) )(Q∩L′ )\L′′ ||1 + ||(x − χ(t+1) )Q∩L′′ ||1
(t+1)

(27)

(t)

= χi for all i 6∈ L′ , and hence ||(x′ − χ(t+1) )Q\L ||1 = ||(x′ − χ(t) )Q\L ||1 .
√
(t+1)
Second, for i ∈ (Q ∩ L′ ) \ L′′ (second term) one has |x′i − χi
| ≤ α(ν2−t + 4µ). Since only elements
1
ν2−t + 4µ are reported by the threshold setting in E STIMATE VALUES, so |x′i − χ′ | ≤
i ∈ L with |χ′i | > 1000
√
α(2−t ν + 20µ) ≤ x′i as long as α is smaller than a constant. We thus get that ||(x − χ(t+1) )(Q∩L′ )\L′′ ||1 ≤
||(x − χ(t) )(Q∩L′ )\L′′ ||1 .
For the third term, we note that for each i ∈ L the estimate wi computed in the call to E STIMATE VALUES
satisfies
h
i √
√
(28)
E |wi − x′i | − α(2−t ν + 20µ) + ≤ α(2−t ν + µ)k2−Ω(rmax )

We first note that χi

by Lemma 9.1, (2). Verification of the preconditions of the lemma is identical to Lemma 7.1 (note that the
assumptions of this lemma and Lemma 7.1 are identical) and is hence omitted. Since rmax = C(log log N +
√
log(B/k)), the rhs of (28) is bounded by (log N )−25 α(2−t ν +µ)k as long as C > 0 is larger than an absolute
constant. We thus have

X √
√
α(2−t ν + 20µ) + |wi − x′i | − α(2−t ν + 20µ) + .
||(x′ − χ(t+1) )S∩L′′ ||1 ≤
i∈S∩L′′

Combining (28) with the fact that by by Lemma 9.1, (1), we have for every i ∈ L


√
Pr |wi − x′i | > α(2−t ν + 20µ) ≤ 2−Ω(rmax ) ≤ (k/B) · (log N )−25

by our choice of rmax , we get that

√
||(x′ − χ(t+1) )S∩L′′ ||1 ≤ 2 α(2−t ν + 20µ) · |L| · (k/B) · (log N )−25 .
An application of Markov’s inequality then implies, if α is smaller than an absolute constant, that
Pr[||(x′ − χ(t+1) )S∩L′′ ||1 >

1
log

21

N

(ν + µ)k] < 1/ log 3 N.

Substituting the bounds we just derived into (27), we get
||(x − χ(t+1) )Q ||1 ≤ ||(x − χ(t) )Q ||1 +
as required.

29

1
log

21

N

(ν + µ)k

Equipped with the two lemmas above, we can now give a proof of Lemma 3.2:
Proof of Lemma 3.2: We prove the result by strong induction on t = 0, . . . , log2 (log4 N ). Specifically, we
prove that there exist events Et , t = 0, . . . , log2 (log4 N ) such that (a) Et depends on the randomness used in the
call to E STIMATE VALUES at step t, Et satisfies Pr[Et |E0 ∧. . . Et−1 ] ≥ 1−3/ log 2 N and (b) for all t conditional
on E0 ∧ E1 ∧ . . . ∧ Et one has
(1) ||(x′ − χ(t) )S\S ∗ ||1 ≤ (2−t ν + 20µ)k;
(2) ||(χ + χ(t) )[n]d \S ||0 ≤ ||χ[n]d \S ||0 +

t
k;
log21 N

(3) ||(x′ − χ(t) )S ∗ ||1 + ||(χ + χ(t) )[n]d \S ||1 ≤ ||x′S ∗ ||1 + ||χ[n]d \S ||1 +

t
νk
log21 N

The base is provided by t = 0 and is trivial since χ(0) = 0. We now give the inductive step.
We start by proving the inductive step for (2) and (3). We will use Lemma 7.1 and Lemma 7.2, and hence we
start by verifying that their preconditions (which are identical for the two lemmas) are satisfied. Precondition
A is satisfied directly by inductive hypothesis (1). Precondition B is satisfied since
||(χ + χ(t) )[n]d \S ||0 ≤ ||χ[n]d \S ||0 +

t
log21 N

k≤

1
log19 N

k+

log 2(log4 N )
2
≤
k,
21
19
log N
log N

where we used assumption B of this lemma and inductive hypothesis (2). Precondition C is satisfied since
||(x′ −χ(t) )S ∗ ||1 +||(χ+χ(t) )[n]d \S ||1 ≤ ||x′S ∗ ||1 +||χ[n]d \S ||1 +

t
log

21

N

νk ≤

ν
t
2ν
k+ 21 νk ≤
k,
4
log N
log N
log4 N

where we used assumption 3 of this lemma, inductive assumption (3) and the fact that t ≤ log2 (log4 N ) ≤
log N for sufficiently large N .
Proving (2). To prove the inductive step for (2), we use Lemma 7.1. Lemma 7.1 shows that with probability
at least 1 − (log N )−2 over the randomness used in E STIMATE VALUES (denote the success event by Et1 ) we
have
1
k,
||(χ + χ(t+1) )[n]d \S ||0 − ||(χ + χ(t) )[n]d \S ||0 ≤
21
log N
so ||(χ + χ(t+1) )[n]d \S ||0 ≤ ||(χ + χ(t) )[n]d \S ||0 +

1
k
log21 N

≤ ||χ[n]d \S ||0 +

t+1
k
log21 N

as required.

Proving (3). At the same time we have by Lemma 7.2 that with probability at least 1 − (log N )−2 (denote
the success event by Et2 )
||(x′ − χ(t+1) )([n]d \S)∪S ∗ ||1 − ||(x′ − χ(t) )([n]d \S)∪S ∗ ||1 ≤

1
kν,
log21 N

so by combing this with assumption (3) of the lemma we get
||(x′ − χ(t+1) )([n]d \S)∪S ∗ ||1 ≤
as required.

30

1
log

20

N

νk +

t+1
νk
log21 N

Proving (1). We let L′′ ⊆ L denote the set of elements in L that fail to be estimated to within a small additive
error. Specifically, we let
n
o
L′′ = i ∈ L : |χ′i − x′i | > α1/2 2−t ν + 20µ ,

where χ′ is the output of E STIMATE VALUES in iteration t. We bound ||(x′ − χ(t+1) )S\S ∗ ||1 by splitting this
ℓ1 norm into three terms, depending on whether the corresponding elements were updated in iteration t and
whether they were well estimated. We have
||(x′ − χ(t+1) )S\S ∗ ||1 = ||(x′ − (χ(t) + χ′ ))S\S ∗ ||1

≤ ||(x′ − (χ(t) + χ′ ))S\(S ∗ ∪L) ||1 + ||(x′ − (χ(t) + χ′ ))(S∩L)\L′ \L′′ ||1 + ||(x′ − (χ(t) + χ′ ))(S∩L′ )\L′′ ||1

+ ||(x′ − (χ(t) + χ′ ))L′′ ||1

= ||(x′ − χ(t) )S\(S ∗ ∪L) ||1 + ||(x′ − (χ(t) + χ′ ))(S∩L)\L′ \L′′ ||1 + ||(x′ − (χ(t) + χ′ ))(S∩L′ )\L′′ ||1

+ ||(x′ − (χ(t) + χ′ ))(L∩S)∩L′′ ||1
=: S1 + S2 + S3 + S4 ,

(29)
where we used the fact that χ′S\L ≡ 0 to go from the second line to the third. We now bound the four terms.
The second term (i.e. S2 ) captures elements of S that were estimated precisely (and hence they are not
in L′′ ), but were not included into L′ as they did not pass the threshold test (being estimated as larger than
1
−t
1000 2 ν + 4µ) in E STIMATE VALUES . One thus has
||(x − (χ(t) + χ′ ))(S∩L)\L′ \L′′ ||1 ≤ α1/2 (2−t ν + 20µ) · |(S ∩ L′ ) \ L′′ | + (
≤ ((

1 −t
2 ν + 4µ) · |(S ∩ L′ ) \ L′′ |
1000

1
+ α1/2 )2−t ν + (4 + 20α1/2 )µ)2k
1000

(30)
since |S| ≤ 2k by assumption of the lemma.
The third term (i.e. S3 ) captures elements of S that were reported by E STIMATE VALUES (hence do not
belong to L′ ) and were approximated well (hence belong to L′′ ). One has, by definition of the set L′′ ,
||(x − (χ(t) + χ′ ))(S∩L′ )\L′′ ||1 = α1/2 (2−t ν + 20µ) · |(S ∩ L′ ) \ L′′ |

(31)

≤ 2α1/2 (2−t ν + 20µ)k

since |S| ≤ 2k by assumption of the lemma.
For the forth term (i.e. S4 ) we have
X


|χ′i − x′i | − α1/2 2−t ν + 20µ
||(x′ − (χ(t) + χ′ ))L′′ ||1 ≤ α1/2 2−t ν + 20µ · |L′′ | +
i∈S

+

.

By Lemma 9.1, (1) (invoked on the set S ∪ supp(χ + χ(t) + χ′ )) we have E[|L′′ |] ≤ B · 2−Ω(rmax ) and by
Lemma 9.1, (2) for any i one has




′
′
1/2
−t
2 ν + 20µ
E |χi − xi | − α
≤ |L| · α1/2 2−t ν + 20µ 2−Ω(rmax ) .
+

Since the parameter rmax in E STIMATE VALUES is chosen to be at least C(log log N + d2 + log(B/k)) for a
sufficiently large constant C, and |L| = O(log N )B, we have
i
h


1
2−t ν + 20µ k
E ||(x′ − (χ(t) + χ′ ))L′′ ||1 ≤ α1/2 2−t ν + 20µ |L|2−Ω(rmax ) ≤
25
log N
31

By Markov’s inequality we thus have

||(x′ − (χ(t) + χ′ ))L′′ ||1 ≤ α1/2 2−t ν + 20µ |L|2−Ω(rmax ) ≤

1
log

22

N


2−t ν + 20µ k

(32)

with probability at least 1 − 1/ log 3 N . Denote the success event by Et0 .
Finally, in order to bound the first term (i.e. S1 ), we invoke Theorem 3.1 to analyze the call to L OCATE S IG √
NAL in the t-th iteration. We note that since rmax , cmax ≥ (C1 / α) log log N (where C1 is the constant from
Theorem 3.1) by assumption of the lemma, the preconditions of Theorem 3.1 are satisfied. By Theorem 3.1
together with (1) and (3) of the inductive hypothesis we have
2

||(x′ − χ(t) )S\(S ∗ ∪L) ||1 ≤ (4C2 α)d/2 ||(x′ − χ(t) )S\S ∗ ||1 + (4C)d (||(χ + χ(t) )[n]d \S ||1 + ||(x′ − χ(t) )S ∗ ||1 ) + 4µ|S|
2
2
≤ O((4C2 α)d/2 )(2−t ν + 20µ)k + (4C)d ( 20 νk) + 8µk
log N
1
(2−t ν + 20µ)k + 8µk
≤
1000
(33)
if α is smaller than an absolute constant and N is sufficiently large.
Now substituting bounds on S1 , S2 , S3 , S4 provided by (33), (30), (31) and (32) into (29) we get
2
||(x′ − χ(t+1) )S\S ∗ ||1 ≤ (
+ O(α1/2 ))2−t ν + (16 + O(α1/2 ))µk
1000
≤ 2−t ν + 20µk

when α is a sufficiently small constant, as required. This proves the inductive step for (1) and completes the
proof of the induction.
Let Et = Et0 ∧Et1 ∧Et2 denote the success event for step t. We have by a union bound Pr[Et ] ≥ 1−3t/ log2 N
as required.
Sample complexity and runtime It remains to bound the sampling complexity and runtime. First note that
R EDUCE L1N ORM only takes fresh samples in the calls to E STIMATE VALUES that it issues. By Lemma 9.1
2
2
each such call uses 2O(d ) k(log log N ) samples, amounting to 2O(d ) k(log log N )2 samples over O(log log N )
iterations.
By Lemma 5.1 each call to L OCATE S IGNAL takes O(B(log N )3/2 ) time. Updating the measurements
m(b
x, Hr , a ⋆ (1, w)), w ∈ W takes
2

|W|cmax rmax · F O(d) · B logd+1 N log log N = 2O(d ) · k logd+2 N
2

time overall. The runtime complexity of the calls to E STIMATE VALUES is 2O(d ) · k logd+1 N (log log N )2 time
2
overall. Thus, the runtime is bounded by 2O(d ) k logd+2 N .

7.2 Analysis of SNR reduction loop in S PARSE FFT
In this section we prove
Theorem 3.3 For any x ∈ CN , any integer k ≥ 1, if µ2 ≥ Err2k (x)/k and R∗ ≥ ||x||∞ /µ = N O(1) , the
following conditions hold for the set S := {i ∈ [n]d : |xi | > µ} ⊆ [n]d .
Then the SNR reduction loop of Algorithm 2 (lines 19-25) returns χ(T ) such that
||(x − χ(T ) )S ||1 . µ

(ℓ1 -SNR on head elements is constant)

||χ[n]d \S ||1 . µ

(spurious elements contribute little in ℓ1 norm)

(T )

(T )

||χ[n]d \S ||0 .

log

1
19

N

k

(small number of spurious elements have been introduced)
32

with probability at least 1 − 1/ log N over the internal randomness used by Algorithm 2. The sample
2
2
complexity is 2O(d ) k log N (log log N ). The runtime is bounded by 2O(d ) k logd+3 N .
Proof. We start with correctness. We prove by induction that after the t-th iteration one has
(1) ||(x − χ(t) )S ||1 ≤ 4(log4 N )T −t µk + 20µk;
(2) ||x − χ(t) ||∞ = O((log4 N )T −(t−1) µ);
(t)

(3) ||χ[n]d \S ||0 ≤

t
k.
log20 N

The base is provided by t = 0, where all claims are trivially true by definition of R∗ . We now prove the
inductive step. The main tool here is Lemma 3.2, so we start by verifying that its preconditions are satisfied.
First note that
1
First, since |S ∗ | ≤ 2−Ω(rmax ) |S| ≤ 2−Ω(rmax ) k ≤ log19
k with probability at least 1 − 2−Ω(rmax ) ≥
N
√
1 − 1/ log N by Lemma 2.12 and choice of rmax ≥ (C/ α) log log N for a sufficiently large constant C > 0.
Also, by Claim 2.14 we have that with probability at least 1−1/ log2 N for every s ∈ [1 : d] the sets Ar ⋆(0, es )
1
are balanced (as per Definition 2.13 with ∆ = 2⌊ 2 log2 log2 n⌋ , as needed for Algorithm 1). Also note that by (2)
of the inductive hypothesis one has ||x − χ(t) ||∞ /µ = R∗ · O(log N ) = N O(1) .
First, assuming the inductive hypothesis (1)-(3), we verify that the preconditions of Lemma 3.2 are satisfied with ν = 4(log 4 N )T −t µk. First, for (A) one has ||(x − χ(t) )S ||1 ≤ 4(log4 N )T −t µk. This satisfies
precondition A of Lemma 3.2. We have
(t)

(t)

||(x − χ(t) )S ∗ ||1 + ||χ[n]d \S ||1 ≤ ||x − χ(t) ||∞ · (||(x − χ(t) )S ∗ ||0 + ||χ[n]d \S ||0 )


t
16
1
4
k+
k ≤
νk
≤ O(log N ) · ν ·
19
20
log N
log N
log14 N

(34)

for sufficiently large N . Since the rhs is less than log14 N νk, precondition (C) of Lemma 3.2 is also satisfied. Precondition (B) of Lemma 3.2 is satisfied by inductive hypothesis, (3) together with the fact that
T = o(log R∗ ) = o(log N ).
Thus, all preconditions of Lemma 3.2 are satisfied. Then by Lemma 3.2 with ν = 4(log4 N )T −t µ one has
with probability at least 1 − 1/ log 2 N
1. ||(x′ − χ(t) − χ′ )S ||1 ≤

1
νk
log4 N
(t)

+ 20µk;

2. ||(χ(t) + χ′ )[n]d \S ||0 − ||χ[n]d \S ||0 ≤

1
k;
log20 N
(t)

3. ||(x′ − (χ(t) + χ′ ))S ∗ ||1 + ||(χ(t) + χ′ )[n]d \S ||1 ≤ ||(x′ − χ(t) )S ∗ ||1 + ||χ[n]d \S ||1 +

1
νk.
log20 N

Combining 1 above with (34) proves (1) of the inductive step:
||(x − χ(t+1) )S ||1 = ||(x − χ(t) − χ′ )S ||1 ≤

1
1
νk + 20µk =
4(log4 N )T −t µk + 20µk
4
log N
log4 N

= 4(log4 N )T −(t+1) µk + 20µk.
(t+1)

(t)

t
k yields ||χ[n]d \S ||0 ≤ logt+1
k as required.
Also, combining 2 above with the fact that ||χ[n]d \S ||0 ≤ log20
20
N
N
In order to prove the inductive step is remains to analyze the call to R EDUCE I NF N ORM, for which we use
Lemma 8.1 with parameter k̃ = 4k/ log 4 N . We first verify that preconditions of the lemma are satisfied. Let
y := x − (χ + χ(t) + χ′ ) to simplify notation. For that we need to verify that

||y[k̃] ||1 /k̃ ≤ 4(log4 N )T −(t+1) µ = (log4 N ) · (
33

1
ν + 20µ)
log4 N

(35)

and

p
||y[n]d \[k̃] ||2 / k̃ ≤ (log4 N ) · (

1
ν + 20µ),
log4 N

(36)

where we denote k̃ := 4k/ log 4 N for convenience. The first condition is easy to verify, as we now show.
Indeed, we have
||yk̃ ||1 ≤ ||yS ||1 + ||ysupp(χ(t) +χ′ )\S ||1 + ||x[n]d \S ||∞ · k̃

≤ ||yS ||1 + ||(χ(t) + χ′ )[n]d \S ||1 + ||xsupp(χ(t) +χ′ )\S ||∞ · k̃ + ||x[n]d \S ||∞ · k̃
1
1
2
≤
νk + 20µk +
νk + 2µk̃ ≤
νk + 40µk,
4
4
log N
log N
log4 N

where we used the triangle inequality to upper bound ||ysupp(χ(t) +χ′ )\S ||1 by ||(χ(t) +χ′ )[n]d \S ||1 +||xsupp(χ(t) +χ′ )\S ||∞ ·
k̃ to go from the first line to the second. We thus have
||y[k̃] ||1 /k̃ ≤ (

1
2
νk + 40µk)/(4k/ log 4 N ) ≤ (log4 N ) · ( 4 ν + 20µ)
4
log N
log N

as required. This establishes (35).
To verify the second condition, we first let S̃ := S ∪ supp(χ + χ(t) + χ′ ) to simplify notation. We have
||y[n]d \[k̃] ||22 = ||yS̃\[k̃] ||22 + ||y([n]d \S̃)\[k̃] ||22 ≤ ||yS̃\[k̃] ||22 + µ2 k,

(37)

where we used the fact that y[n]d\S̃ = x[n]d \S̃ and hence ||y([n]d \S̃)\[k̃] ||22 ≤ µ2 k. We now note that ||yS̃\[k̃] ||1 ≤
||yS̃ ||1 ≤ 2( log14 N νk + 20µk), and so it must be that ||yS\[k̃] ||∞ ≤ 2( log14 N νk + 20µk)(k/k̃), as otherwise the

top k̃ elements of y[k̃] would contribute more than 2( log14 N νk + 20µk) to ||yS̃ ||1 , a contradiction. With these

constraints ||yS̃\[k̃] ||22 is maximized when there are k̃ elements in yS̃\[k̃] , all equal to the maximum possible

value, i.e. ||yS̃\[k̃] ||22 ≤ 4( log14 N νk+20µk)2 (k/k̃)2 k̃. Plugging this into (37), we get ||y[n]d \[k̃] ||22 ≤ ||yS̃\[k̃] ||22 +

µ2 k ≤ 4( log14 N νk + 20µk)2 (k/k̃)2 k̃ + µ2 k. This implies that
s

s
1
1
4( 4 νk + 20µk)2 (k/k̃)2 + µ2 (k/k̃) ≤ 2(k/k̃) ( 4 νk + 20µk)2 + µ2
log N
log N
1
1
≤ 2(( 4 νk + 20µk) + µ)(k/k̃) ≤ (log4 N )( 4 νk + 20µk),
log N
log N

p
||y[n]d \[k̃] ||2 / k̃ ≤

establishing (36).
Finally, also recall that ||yS\[k̃] ||∞ ≤ 2( log14 N νk + 20µk)(k/k̃) ≤ (log4 N ) · ( log14 N νk + 20µk) and
||y[n]d \S̃ ||∞ = ||x[n]d \S ||∞ ≤ µ.
We thus have that all preconditions of Lemma 8.1 are satisfied for the set of top k̃ elements of y, and hence
its output satisfies
1
||x − (χ(t) − χ′ − χ′′ )||∞ = O(log4 N ) · ( 4 νk + 20µk).
log N

Putting these bounds together establishes (2), and completes the inductive step and the proof of correctness.
Finally, taking a union bound over all failure events (each call to E STIMATE VALUES succeeds with probability at least 1 − log12 N , and with probability at least 1 − 1/ log2 N for all s ∈ [1 : d] the set Ar ⋆ (0, es )
is balanced in coordinate s) and using the fact that log T = o(log N ) and each call to L OCATE S IGNAL is
deterministic, we get that success probability of the SNR reduction look is lower bounded by 1 − 1/ log N .
34

Sample complexity and runtime The sample complexity is bounded by the the sample complexity of the
calls to R EDUCE L1N ORM and R EDUCE I NF N ORM inside the loop times O(log N/ log log N ) for the num2
ber of iterations. The former is bounded by 2O(d ) k(log log N )2 by Lemma 3.2, and the latter is bounded by
2
2
2O(d ) k/ log N by Lemma 8.1, amounting to at most 2O(d ) k log N (log log N ) samples overall. The run2
time complexity is at most 2O(d ) k logd+3 N overall for the calls to R EDUCE L1N ORM and no more than
2
2O(d ) k logd+3 N overall for the calls to R EDUCE I NF N ORM.

7.3 Analysis of S PARSE FFT
d

Theorem 3.5 For any ǫ > 0, x ∈ C[n] and any integer k ≥ 1, if R∗ ≥ ||x||∞ /µ = poly(N ), µ2 ≥
||x[n]d \[k] ||22 /k, µ2 = O(||x[n]d \[k] ||22 /k) and α > 0 is smaller than an absolute constant, S PARSE FFT(x̂, k, ǫ, R∗ , µ)
2
2
solves the ℓ2 /ℓ2 sparse recovery problem using 2O(d ) (k log N log log N + 1ǫ k log N ) samples and 2O(d ) 1ǫ k logd+3 N
time with at least 98/100 success probability.
Proof. By Theorem 3.3 the set S := {i ∈ [n]d : |xi | > µ} satisfies
||(x − χ(T ) )S ||1 . µk
and
(T )

||χ[n]d \S ||1 . µk
1

(T )

||χ[n]d \S ||0 .

log

19

N

k

with probability at least 1 − 1/ log N .
We now show that the signal x′ := x− χ(T ) satisfies preconditions of Lemma 3.4 with parameter k. Indeed,
letting Q ⊆ [n]d denote the top 2k coefficients of x′ , we have
(T )

||x′Q ||1 ≤ ||x′Q∩S ||1 + ||χ(Q\S)∩supp χ(T ) ||1 + |Q| · ||x[n]d \S ||1 ≤ O(µk)
Furthermore, since Q is the set of top 2k elements of x′ , we have
||x′[n]d \Q ||22 ≤ ||x′[n]d \(S∪supp χ(T ) ) ||22 ≤ ||x[n]d \(S∪supp χ(T ) ) ||22 ≤ ||x[n]d \S ||22
≤ µ2 |S| + ||x[n]d \[k] ||22 = O(µ2 k)

as required.
Thus, with at least 99/100 probability we have by Lemma 3.4 that
||x − χ(T ) − χ′ ||2 ≤ (1 + O(ǫ)) Errk (x).
By a union bound over the 1/ log N failure probability of the SNR reduction loop we have that S PARSE FFT is
correct with probability at least 98/100, as required.
It remains to bound the sample and runtime complexity. The number of samples needed to compute
m(b
x, Hr , a ⋆ (1, w)) ← H ASH T O B INS (x̂, 0, (Hr , a ⋆ (1, w)))
2

2

for all a ∈ Ar , w ∈ W is bounded by 2O(d ) k log N (log log N ) by our choice of B = 2O(d ) k, rmax =
O(log log N ), |W| = O(log N/ log log N ) and |Ar | = O(log log N ), together with Lemma 9.2. This is
2
asymptotically the same as the 2O(d ) k log N (log log N ) sample complexity of the ℓ1 norm reduction loop by
2
Theorem 3.3. The sampling complexity of the call to R ECOVER AT C ONSTANT SNR is at most 2O(d ) 1ǫ k log N
by Lemma 3.4, yielding the claimed bound.
2
The runtime of the SNR reduction loop is bounded by 2O(d ) k logd+3 N by Theorem 3.3, and the runtime
2
of R ECOVER AT C ONSTANT SNR is at most 2O(d ) 1ǫ k logd+2 N by Lemma 3.4.
35

8 ℓ∞ /ℓ2 guarantees and constant SNR case
In this section we state and analyze our algorithm for obtaining ℓ∞ /ℓ2 guarantees in Õ(k) time, as well as a
procedure for recovery under the assumption of bounded ℓ1 norm of heavy hitters (which is very similar to the
R ECOVER AT C ONST SNR procedure used in [IKP14]).

8.1 ℓ∞ /ℓ2 guarantees
The algorithm is given as Algorithm 4.
Algorithm 4 R EDUCE I NF N ORM(x̂, χ, k, ν, R∗ , µ)
1: procedure R EDUCE I NF N ORM (x̂, χ, k, ν, R∗ , µ)
2:
χ(0) ← 0
⊲ in Cn
3:
B ← (2π)4d·F · k/αd for a small constant α > 0
4:
T ← log2 R∗
√
5:
rmax ← (C/ α) log N for sufficiently large constant C > 0
1
6:
W ← {0d }, ∆ ← 2⌊ 2 log2 log2 n⌋
⊲ 0d is the zero vector in dimension d
7:
for g = 1 to ⌈log
S∆ n⌉ do
8:
W ← W ∪ ds=1 {n∆−g · es }
⊲ es is the unit vector in direction s
9:
end for
10:
G ← filter with B buckets and sharpness F , as per Lemma 2.3
11:
for r = 1 to rmax do
⊲ Samples that will be used for location
d
12:
Choose Σr ∈ Md×d , qr ∈ [n] uniformly at random, let πr := (Σr , qr ) and let Hr := (πr , B, F )
13:
Let Ar ← C log log N elements of [n]d × [n]d sampled uniformly at random with replacement
14:
for w ∈ W do
15:
m(b
x, Hr , a ⋆ (1, w)) ← H ASH T O B INS (x̂, 0, (Hr , a ⋆ (1, w))) for all a ∈ Ar , w ∈ W
16:
end for
17:
end for
18:
for t = 0 to T − 1 do
⊲ Locating elements of the residual that pass a threshold test
19:
for r = 1 to rmax do


max
20:
Lr ← L OCATE S IGNAL χ(t) , k, {m(b
x, Hr , a ⋆ (1, w))}rr=1,a∈A
r ,w∈W
21:
end for
S max
Lr
22:
L ← rr=1
′
23:
χ ← E STIMATE VALUES (x̂, χ(t) , L, k, 1, O(log n), 5(ν2T −(t+1) + µ), ∞)
24:
χ(t+1) ← χ(t) + χ′
25:
end for
26:
return χ(T )
27: end procedure
Lemma 8.1. For any x, χ ∈ Cn , x′ = x − χ, any integer k ≥ 1, if parameters ν and µ satisfy ν ≥
||x′[k] ||1 /k, µ2 ≥ ||x′[n]d \[k] ||22 /k, then the following conditions hold. If S ⊆ [n]d is the set of top k eld

ements of x′ in terms of absolute value, and ||x′[n]d \S ||∞ ≤ ν, then the output χ ∈ C[n] of a call to
R EDUCE I NF N ORM(b
x , χ, k, ν, R∗ , µ) with probability at least 1 − N −10 over the randomness used in the call
satisfies
||x′ − χ||∞ ≤ 8(ν + µ) + O(1/N c ),

(all elements in S have been reduced to about ν + µ),

36

where the O(||x′ ||∞ /N c ) term corresponds to polynomially small error in our computation of the semiequispaced Fourier transform. Furthermore, we have χ[n]d \S ≡ 0. The number of samples used is bounded by
2
2
2O(d ) k log3 N . The runtime is bounded by 2O(d ) k logd+3 N .
Proof. We prove by induction on t that with probability at least 1 − N −10 one has for each t = 0, . . . , T − 1
(1) ||(x′ − χ(t) )S ||∞ ≤ 8(ν2T −t + µ)
(t)

(2) χ[n]d \S ≡ 0
(3) |(x′i − χ(t) )i | ≤ |x′i | for all i ∈ [n]d

for all such t.
The base t = 0 holds trivially. We now prove the inductive step. First, since r = C log N for a constant
√
C > 0, we have by Lemma 2.12 that each i ∈ √S is isolated under at least a 1 − α fraction of hashings
H1 , . . . , Hrmax with probability at least 1 − 2−Ω( αrmax ) ≥ 1 − N −10 as long as C > 0 is sufficiently large.
This lets us invoke Lemma 6.3 with S ∗ = ∅. We now use Lemma 6.3 to obtain bounds on functions ehead and
etail applied to our hashings {Hr } and vector x′ . Note that ehead and etail are defined in terms of a set S ⊆ [n]d
(this dependence is not made explicit to alleviate notation). We use S = [k̃], i.e. S is the top k elements of x′ .
The inductive hypothesis together with the second part of Lemma 6.3 gives for each i ∈ S
||ehead
({Hr }, x′ , χ(t) )||∞ ≤ (Cα)d/2 ||(x′ − χ(t) )S ||∞ .
S

To bound the effect of tail noise, we invoke the second part of Lemma 6.6, which states that if rmax = C log N
√
′
for a sufficiently large constant C > 0 , we have ||etail
S ({Hr , Ar }, x )||∞ = O( αµ).
These two facts together imply by the second claim of Corollary 5.2 that each i ∈ S such that
√
√
|(x′ − χ(t) )i | ≥ 20 α||(x′ − χ(t) )S ||∞ + 20 αµ
is located. In particular, by the inductive hypothesis this means that every i ∈ S such that
√
|(x′ − χ(t) )i | ≥ 20 α(ν2T −t + 2µ) + (4µ)

is located and reported in the list L . This means that

√
||(x′ − χ(t) )[n]d \L ||∞ ≤ 20 α(ν2T −t + 2µ) + (4µ),

and hence it remains to show that each such element in L is properly estimated in the call to E STIMATE VALUES,
and that no elements outside of S are updated.
We first bound estimation quality. First note that by part (3) of the inductive hypothesis together with
Lemma 9.1, (1) one has for each i ∈ L
√
Pr[|χ′ − (x′ − χ(t) )i | > α · (ν + µ)] < 2−Ω(rmax ) < N −10 ,

as long as rmax ≥ C log N for a sufficiently large constant C > 0. This means that all elements in the list L
are estimated up to an additive (ν + µ)/10 ≤ (ν2T −t + µ)/10 term as long as α is smaller than an absolute
constant. Putting the bounds above together proves part (1) of the inductive step.
To prove parts (2) and (3) of the inductive step, we recall that the only elements i ∈ [n]d that are updated are
the ones that satisfy |χ′ | ≥ 5(ν2T −(t+1) + µ). By the triangle inequality and the bound on additive estimation
error above that
|(x′ − χ(t) )i | ≥ 5(ν2T −(t+1) + µ) − (ν + µ)/10 > 4(ν2T −(t+1) + µ) ≥ 4(ν + µ).

Since |(x′ − χ(t) )i | ≤ |xi | by part (2) of the inductive hypothesis, we have that only elements i ∈ [n]d with
|x′i | ≥ 4(ν + µ) are updated, but those belong to S since ||x′[n]d \S ||∞ ≤ ν by assumption of the lemma. This
proves part (3) of the inductive step. Part (2) of the inductive step follows since |(x′ − χ(t) − χ′ )i | ≤ (ν + µ)/10
by the additive error bounds above, and the fact that |(x′ − χ(t) )i | > 4(ν + µ). This completes the proof of the
inductive step and the proof of correctness.
37

Sample complexity and runtime Since H ASH T O B INS uses B · F d samples by Lemma 9.2, the sample
complexity of location is bounded by
2

B · F d · rmax · cmax · |W| = 2O(d ) k log3 N.
Each call to E STIMATE VALUES uses B · F d · k · rmax samples, and there are O(log N ) such calls overall,
resulting in sample complexity of
2

B · F d · rmax · log N = 2O(d ) k log2 N.
2

Thus, the sample complexity is bounded by 2O(d ) k log3 N . The runtime bound follows analogously.

8.2 Recovery at constant SNR
The algorithm is given by
Algorithm 5 R ECOVER AT C ONSTANT SNR(x̂, χ, k, ǫ)
1: procedure R ECOVER AT C ONSTANT SNR(x̂, χ, k, ǫ)
2:
B ← (2π)4d·F · k/(ǫαd )
3:
Choose Σ ∈ Md×d , q ∈ [n]d uniformly at random, let π := (Σ, q) and let Hr := (πr , B, F )
4:
Let A ← C log log N elements of [n]d × [n]d sampled uniformly at random with replacement
1
⊲ 0d is the zero vector in dimension d
5:
W ← {0d }, ∆ ← 2⌊ 2 log2 log2 n⌋
6:
for g = 1 to ⌈log
S∆ n⌉ do
7:
W ← W ∪ ds=1 n∆−g · es
⊲ es is the unit vector in direction s
8:
end for
9:
for w ∈ W do
10:
m(b
x, H, a ⋆ (1, w)) ← H ASH T O B INS (x̂, 0, (H, a ⋆ (1, w))) for all a ∈ A, w ∈ W
11:
end for

12:
L ← L OCATE S IGNAL χ(t) , k, {m(b
x, H, a ⋆ (1, w))}a∈A,w∈W
13:
χ′ ← E STIMATE VALUES (x̂, χ, 2k, ǫ, O(log N ), 0)
14:
L′ ←top 4k elements of χ′
15:
return χ + χ′L′
16: end procedure
Our analysis will use
Lemma 8.2 (Lemma 9.1 from [IKP14]). Let x, z ∈ Cn and k ≤ n. Let S contain the largest k terms of x, and
T contain the largest 2k terms of z. Then ||x − zT ||22 ≤ ||x − xS ||22 + 4||(x − z)S∪T ||22 .
√
Lemma 3.4 For any ǫ > 0, x̂, χ ∈ CN , x′ = x − χ and any integer k ≥ 1 if ||x′[2k] ||1 ≤ O(||x[n]d \[k] ||2 k)
and ||x′[n]d \[2k] ||22 ≤ ||x[n]d \[k] ||22 , the following conditions hold. If ||x||∞ /µ = N O(1) , then the output χ′ of
R ECOVER AT C ONSTANT SNR(x̂, χ, 2k, ǫ) satisfies
||x′ − χ′ ||22 ≤ (1 + O(ǫ))||x[n]d \[k] ||22
2) 1

with at least 99/100 probability over its internal randomness. The sample complexity is 2O(d
2
the runtime complexity is at most 2O(d ) 1ǫ k logd+1 N.

ǫ k log N ,

and

Remark 8.3. We note that the error bound is in terms of the k-term approximation error of x as opposed to the
2k-term approximation error of x′ = x − χ.
38

Proof. Let S denote the top 2k coefficients of x′ . We first derive bounds on the probability that an element
i ∈ S is not located. Recall that by Lemma 5.1 for any i ∈ S if
1. ehead
(H, x′ , 0) < |x′i |/20;
i
′
′
2. etail
i (H, A ⋆ (1, w), x ) < |xi |/20 for all w ∈ W;

3. for every s ∈ [1 : d] the set A ⋆ (0, es ) is balanced (as per Definition 2.13),
then i ∈ L, i.e. i is successfully located in L OCATE S IGNAL.
We now upper bound the probability that an element i ∈ S is not located. We let µ2 := ||x[n]d \k ||22 /k to
simplify notation.
We need to bound, for i ∈ S, the quantity
X
−1
′
·
Goi (j) |x′j |.
(H,
x
,
0)
=
G
ehead
i
oi (i)

Contribution from head elements.

j∈S\{i}

Recall that m(b
x, H, a ⋆ (1, w)) = H ASH T O B INS (x̂, 0, (H, a ⋆ (1, w))), and let m := m(b
x, H, a ⋆ (1, w)) to
simplify notation. By Lemma 2.9, (1) one has
T Σi

ω −a
EH [ max |G−1
oi (i)
a∈[n]d

mh(i) − (x′S )i |] ≤ (2π)d·F · C d ||x′S ||1 /B + µ/N 2

(38)

for a constant C > 0. This yields
(H, x′ , 0)] ≤ (2π)d·F · C d ||x′S ||1 /B . (2π)d·F · C d µk/B . αd C d ǫµ.
EH [ehead
i
by the choice of B in R ECOVER AT C ONSTANT SNR. Now by Markov’s inequality we have for each i ∈ [n]d
PrH [ehead
(H, x′ , 0) > |x′i |/20] . αd C d ǫµ/|x′i | . αǫµ/|x′i |
i

(39)

as long as α is smaller than a constant.
Contribution of tail elements
(see (9), (10), (11) and (12)).
We have

We restate the definitions of etail variables here for convenience of the reader

−1
etail
i (H, z, x) := Goi (i) ·

X

Goi (j) xj ω z

T Σ(j−i)

.

j∈[n]d \S

For any Z ⊆ [n]d we have
1/5

−1
etail
i (H, Z, x) := quantz∈Z Goi (i) ·

X

Goi (j) xj ω z

T Σ(j−i)

.

j∈[n]d \S

Note that the algorithm first selects sets Ar ⊆ [n]d × [n]d , and then accesses the signal at locations given by
Ar ⋆ (1, w), w ∈ W (after permuting input space).
′
The definition of etail
i (H, Ar , x ) for permutation π = (Σ, q) allows us to capture the amount of noise that
our measurements for locating a specific set of bits of Σi suffer from. Since the algorithm requires all w ∈ W
to be not too noisy in order to succeed (see preconditions 2 and 3 of Lemma 5.1), we have
X
′
′
′
etail
(H,
A,
x
)
=
40µ
(x)
+
etail
H,i
i
i (H, A ⋆ (1, w), x ) − 40µH,i (x )
+

w∈W

39

where for any η ∈ R one has |η|+ = η if η > 0 and |η|+ = 0 otherwise.
For each i ∈ S we now define an error event Ei∗ whose non-occurrence implies location of element i, and
then show that for each i ∈ S one has
αǫµ2
(40)
PrH,A [Ei∗ ] . ′ 2 .
|xi |

Once we have (40), together with (39) it allows us to prove the main result of the lemma. In what follows we
concentrate on proving (40). Specifically, for each i ∈ S define
′
′
Ei∗ = {(H, A) : ∃w ∈ W s.t. etail
i (H, A ⋆ (1, w), x ) > |xi |/20}.

′
Recall that etail
[n]d \S , χ[n]d \S , (H, z)) by definition of the measurements m.
i (H, z, x ) = H ASH T O B INS (x\
′ 2
2
′
By Lemma 2.9, (3) one has, for a uniformly random z ∈ [n]d , that Ez [|etail
i (H, z, x )| |] = µH,i (x ). By
Lemma 2.9, (2), we have that

EH [µ2H,i (x′ )] ≤ (2π)2d·F · C d k(x − χ)[n]d \S k22 /B + µ2 /N 2 ≤ αǫµ2 .

(41)

Thus by Markov’s inequality
′ 2
′
2
′ 2
′
2
Prz [etail
i (H, z, x ) > (|xi |/20) ] ≤ αǫ(µH,i (x )) /(|xi |/20) .

Combining this with Lemma 9.5, we get for all τ ≤ (1/20)(|x′i |/20) and all w ∈ W
1/5

′
′
2
′
′
Ω(|A|)
.
PrA [quantz∈A⋆(1,w) etail
i (H, z, x ) > |xi |/20|µH,i (x ) = τ ] < (4τ /(|xi |/20))

(42)

Equipped with the bounds above, we now bound Pr[Ei∗ ]. To that effect, for each τ > 0 let the event Ei (τ )
be defined as Ei (τ ) = {µH,i (x′ ) = τ }. Note that since we assume that we operate on O(log n) bit integers,
µH,i (x′ ) takes on a finite number of values, and hence Ei (τ ) is well-defined. It is convenient to bound Pr[Ei∗ ]
as a sum of three terms:


[
′
′
Ei (τ )
PrH,A [Ei∗ ] ≤ PrH,A  etail
i (H, A, x ) > |xi |/20
+
+

Z

(1/8)(|x′i |/20)

√

Z

αǫµ
∞

√
τ ≤ αǫµ

h
i
′
′
(H,
A,
x
)
>
|x
|/20
|E
(τ
)
Pr[Ei (τ )]dτ
PrH,A etail
i
i
i

Pr[Ei (τ )]dτ

(1/8)(|x′i |/20)

√
We now bound each of the three terms separately for i such that |x′i |/20 ≥ 2 αǫµH,i (x′ ). This is sufficient
for our purposes, as other elements only contribute a small amount of ℓ22 mass.
1. By (42) and a union bound over W the first term is bounded by
√
|W| · ( αǫµ/(|x′i |/20))Ω(|A|) ≤ αǫµ2 /|x′i |2 · |W| · 2−Ω(|A|) ≤ αǫµ2 /|x′i |2 .

(43)

since |A| ≥ C log log N for a sufficiently large constant C > 0 in R ECOVER AT C ONSTANT SNR.
2. The second term, again by a union bound over W and using (42), is bounded by
Z (1/8)(|x′ |/20)
i
|W| · (4τ /(|x′i |/20))Ω(|A|) Pr[Ei (τ )]dτ
√
≤

Z

αǫµ

(1/8)(|x′i |/20)

√

αǫµ

|W|

· (4τ /(|x′i |/20))Ω(|A|) (4τ /(|x′i |/20))2 Pr[Ei (τ )]dτ
40

(44)

Since |A| ≥ C log log N for a sufficiently large constant C > 0 and (4τ /(|x′i |/20)) ≤ 1/2 over the
√
whole range of τ by our assumption that |x′i |/20 ≥ 2 αǫµH,i (x′ ), we have
|W| · (4τ /(|x′i |/20))Ω(|A|) ≤ |W| · (1/2)Ω(|A|) = o(1)

√
for each τ ∈ [ αǫµ, (1/8)(|x′i |/20)]. Thus, (44) is upper bounded by
Z (1/8)(|x′ |/20)
i
(4τ /(|x′i |/20))2 Pr[Ei (τ )]dτ
√
αǫµ

1
.
′
(|xi |/20)2

Z

(1/8)(|x′i |/20)

√
αǫµ

τ 2 Pr[Ei (τ )]dτ
≤

since

Z

(1/8)(|x′i |/20)

√

by (41).

αǫµ

τ 2 Pr[Ei (τ )]dτ ≤

3. For the third term we have
Z ∞

(1/8)(|x′i |/20)

Z

∞
0

αǫµ2
(|x′i |/20)2

τ 2 Pr[Ei (τ )]dτ = EH [µ2H,i (x′ )] = O(α)ǫµ2

Pr[Ei (τ )]dτ = Pr[µH,i (x′ ) > (1/8)(|x′i |/20)] .

αǫµ2
|x′i |2

by Markov’s inequality applied to (41).
Putting the three estimates together, we get Pr[Ei∗ ] =

O(α)ǫµ2
.
|x′i |2

Pr[i 6∈ L] .

Together with (39) this yields for i ∈ S

αǫµ2 αǫµ
+ ′ .
|x′i |2
|xi |

In particular,
E

"
X
i∈S

|x′i |2

#

· 1i∈S\L ≤
.

X
i∈S

X
i∈S

|x′i |2 Pr[i 6∈ L]
|x′i |2



αǫµ αǫµ2
+ ′2
|x′i |
|xi |



. αǫµ2 k,

√
where we used the assumption of the lemma that ||x′[2k] ||1 ≤ O(||x[n]d \[k] ||2 k) and ||x′[n]d \[2k] ||22 ≤ ||x[n]d \[k] ||22
in the last line. By Markov’s inequality we thus have Pr[||x′S\L ||22 > ǫµ2 k] < 1/10 as long as α is smaller than
a constant.
We now upper bound ||x′ − χ′ ||22 . We apply Lemma 8.2 to vectors x′ and χ′ with sets S and L′ respectively,
getting
||x′ − χ′L′ ||22 ≤ ||x′ − x′S ||22 + 4||(x′ − χ′ )S∪L′ ||22

≤ ||x[n]d \[k] ||22 + 4||(x′ − χ′ )S\L ||22 + 4||(x′ − χ′ )S∩L ||22
≤ ||x[n]d \[k] ||22 + 4ǫµ2 k + 4ǫµ2 |S|

≤ ||x[n]d \[k] ||22 + O(ǫµ2 k),
√
where we used the fact that ||(x′ − χ′ )S∩L ||∞ ≤ ǫµ with probability at least 1 − 1/N over the randomness
used in E STIMATE VALUES by Lemma 9.1, (3). This completes the proof of correctness.
41

2

Sample complexity and runtime The number of samples taken is bounded by 2O(d ) 1ǫ k log N by Lemma 9.2,
2
the choice of B. The sampling complexity of the call to E STIMATE VALUES is at most 2O(d ) 1ǫ k log N . The
2
x, H, a ⋆ (1, w)) and
runtime is bounded by 2O(d ) 1ǫ k logd+1 N log log N for computing the measurements m(b
2) 1
d+1
O(d
2
N for estimation.
ǫ k log

9 Utilities
9.1 Properties of E STIMATE VALUES
In this section we describe the procedure E STIMATE VALUES (see Algorithm 6), which, given access to a signal
x in frequency domain (i.e. given x
b), a partially recovered signal χ and a target list of locations L ⊆ [n]d ,
estimates values of the elements in L, and outputs the elements that are above a threshold ν in absolute value.
The SNR reduction loop uses the thresholding function of E STIMATE VALUES and passes a nonzero threshold,
while R ECOVER AT C ONSTANT SNR uses ν = 0.
Algorithm 6 E STIMATE VALUES(x, χ, L, k, ǫ, ν, rmax )
1: procedure E STIMATE VALUES(x, χ, L, k, ǫ, ν, rmax )
⊲ rmax controls estimate confidence
2:
B ← (2π)4d·F · k/(ǫα2d )
3:
for r = 0 to rmax do
4:
Choose Σr ∈ Md×d , qr , zr ∈ [n]d uniformly at random
5:
Let πr := (Σr , qr ), Hr := (πr , B, F ), F = 2d
6:
ur ← H ASH T O B INS (x̂, χ, χ, (Hr , zr ))
7:
⊲ Using semi-equispaced Fourier transform (Corollary 10.2)
8:
end for
9:
L′ ← ∅
⊲ Initialize output list to empty
10:
for f ∈ L do
11:
for r = 0 to rmax do
12:
j ← hr (f )
−zrT Σr f
⊲ Estimate x′f from each measurement
13:
wfr ← vr,j G−1
of (f ) ω
14:
end for
max
⊲ Median is taken coordinatewise
15:
wf ← median{wfr }rr=1
′
16:
If |wf | > ν then L ← L′ ∪ {f }
17:
end for
18:
return wL′
19: end procedure

Lemma 9.1 (ℓ1 /ℓ2 bounds on estimation quality). For any ǫ ∈ (0, 1], any x, χ ∈ Cn , x′ = x − χ, any
L ⊆ [n]d , any integer k and any set S ⊆ [n]d , |S| ≤ 2k the following conditions hold. If ν ≥ ||(x − χ)S ||1 /k
and µ2 ≥ ||(x − χ)[n]d \S ||22 /k, then the output w of E STIMATE VALUES(x̂, χ, L, k, ǫ, ν, rmax ) satisfies the
following bounds if rmax is larger than an absolute constant.
For each i ∈ L
√
(1) Pr[|wi − x′i | > ǫα(ν + µ)] < 2−Ω(rmax ) ;

 √
√
(2) E ||wi − x′i | − ǫα(ν + µ)|+ ≤ ǫα(ν + µ)2−Ω(rmax ) ;
h
i
(3) E |wi − x′i |2 − ǫα(ν + µ)2 + ≤ 2−Ω(rmax ) ǫ(ν 2 + µ2 ).
42

2

2) 1

The sample complexity is bounded by 1ǫ 2O(d ) krmax . The runtime is bounded by 2O(d

ǫ k log

d+1

N rmax .

Proof. We analyze the vector ur ← H ASH T O B INS (x̂, χ, (Hr , zr )) using the approximate linearity of H ASH T O B INS given by Lemma A.1 (see Appendix A). Writing x′ = x′S + x′[n]d \S , we let
uhead
:= H ASH T O B INS (c
xS , χS , (Hr , zr )) and utail
:= H ASH T O B INS (x\
r
r
[n]d \S , χ[n]d \S , (Hr , zr ))
we apply Lemma 2.9, (1) to the first vector, obtaining
T

−zr Σi head
uh(i) − (x′S )i |] ≤ (2π)d·F · C d ||xS ||1 /B + µ/N 2
EHr ,zr [|G−1
oi (i) ω

(45)

Similarly applying Lemma 2.9, (2) and (3) to the utail , we get
T

−zr Σi tail
uhr (i) − (x′[n]d \S )i |2 ] ≤ (2π)2d·F · C d kx′[n]d \S k22 /B,
EHr ,zr [|G−1
oi (i) ω

which by Jensen’s inequality implies
T

−ar Σi tail
uh(i) − ((x − χ)[n]d \S )i |] ≤ (2π)d·F · C d
EHr ,zr [|G−1
oi (i) ω

≤ (2π)d·F
Putting (45) and (46) together and using Lemma A.1, we get

q

kx[n]d \S k22 /B
p
· C d µ · k/B.

T

−zr Σi
uh(i) − (x − χ)i |] ≤ (2π)d·F · C d (||xS ||1 /B + µ ·
EHr ,zr [|G−1
oi (i) ω

p

k/B).

(46)

(47)

We hence get by Markov’s inequality together with the choice B = (2π)4d·F · k/(ǫα2d ) in E STIMATE VALUES
(see Algorithm 6)
T

−zr Σi
uh(i) − (x − χ)i | >
PrHr ,zr [|G−1
oi (i) ω

1√
ǫα(ν + µ)] ≤ (Cα)d/2 .
2

(48)

The rhs is smaller than 1/10 as long as α is smaller than an absolute constant.
Since wi is obtained by taking the median in real and imaginary components, we get by Lemma 9.4
|wi − x′i | ≤ 2median(|wi1 − x′i |, . . . , |wirmax − x′i |).
By (48) combined with Lemma 9.5 with γ = 1/10 we thus have
√
Pr{Hr ,zr } [|wi − x′i | > ǫα(ν + µ)] < 2−Ω(rmax ) .
This establishes (1). (2) follows similarly by applying the first bound from Lemma 9.5 with γ = 1/2 to
random variables Xr = |wir − xi |, r = 1, . . . , rmax and Y = |wi − xi |. The third claim of the lemma follows
analogously.
The sample and runtime bounds follow by Lemma 9.2 and Lemma 10.1 by the choice of parameters.

9.2 Properties of H ASH TO B INS
Lemma 9.2. H ASH T O B INS(b
x, χ, (H, a)) computes u such that for any i ∈ [n],
X
T
uh(i) = ∆h(i) +
Goi (j) (x − χ)j ω a Σj
j

where G is the filter defined in section 2, and ∆2h(i) ≤ kχk22 /((R∗ )2 N 11 ) is a negligible error term. It takes
O(BF d ) samples, and if kχk0 . B, it takes O(2O(d) · B logd N ) time.
43

Algorithm 7 Hashing using Fourier samples (analyzed in Lemma 9.2)
1: procedure H ASH T O B INS(b
x , χ, (H, a))
2:
G ← filter with B buckets, F = 2d
⊲ H = (π, B, F ), π = (Σq)
′
′
′
′
−Ω(c)
3:
Compute y = Ĝ
χ−χ
b k∞ < N
⊲ c is a large constant
√· PΣ,a,q (x̂ − χ̂ ), for some χ with kb
4:
Compute uj = NF −1 (y ′ )(n/b)·j for j ∈ [b]d
5:
return u
6: end procedure
b so |S| . (2F )d · B and in fact S ⊂ B∞ 1/d (0).
Proof. Let S = supp(G),
F ·B
First, H ASH T O B INS computes

b · PΣ,a,q x\
b · PΣ,a,q x
b · PΣ,a,q χ\
\
y′ = G
− χ′ = G
−χ+G
− χ′ ,

for an approximation χ
b′ to χ
b. This is efficient because one can compute (PΣ,a,q x
b)S with O(|S|) time and
′
′
samples, and PΣ,a,q χ
bS is easily computed from χ
bT for T = {Σ(j − b) : j ∈ S}. Since T is an image of an
ℓ∞ ball under a linear transformation and χ is B-sparse, by Corollary 10.2, an approximation χ
b′√to χ
b can be
d
O(d)
′
−Ω(c)
b 2=
b
N
kGk
computed
in
O(2
·
B
log
N
)
time
such
that
|b
χ
−
χ
b
|
<
N
for
all
i
∈
T
.
Since
k
Gk
≤
i
1
i
√
b
N kGk2 ≤ N kGk∞ ≤ N and G is 0 outside S, this implies that
b · PΣ,a,q (χ\
b 1 max |(PΣ,a,q (χ\
b 1 max |(χ\
kG
− χ′ )k2 ≤ kGk
− χ′ ))i | = kGk
− χ′ )i | ≤ N −Ω(c)
i∈S

i∈T

(49)

√
b = NG
b · PΣ,a,q (χ\
as long as c is larger than an absolute constant. Define ∆ by ∆
− χ′ ). Then H ASH T O B INS
B
computes u ∈ C such that for all i,
√
√
uh(i) = N F −1 (y ′ )(n/b)·h(i) = N F −1 (y)(n/b)·h(i) + ∆(n/b)·h(i) ,
b · PΣ,a,q x
\
for y = G
− χ. This computation takes O(ky ′ k0 + B log B) . B log(N ) time. We have by the
convolution theorem that
√
\
b · PΣ,a,q (x
− χ))(n/b)·h(i) + ∆(n/b)·h(i)
uh(i) = N F −1 (G
\
= (G ∗ F(PΣ,a,q (x
− χ)))(n/b)·h(i) + ∆(n/b)·h(i)
X
\
=
G(n/b)·h(i)−π(j) F(PΣ,a,q (x
− χ))π(j) + ∆(n/b)·h(i)
π(j)∈[N ]

=

X

i∈[N ]

T Σj

Goi (j) (x − χ)j ω a

+ ∆(n/b)·h(i)

where the last step is the definition of oi (j) and Lemma 2.2.
Finally, we note that
√
b 2 = N kG
b · PΣ,a,q (χ\
|∆(n/b)·h(i) | ≤ k∆k2 = k∆k
− χ′ )k2 ≤ N −Ω(c) ,
where we used (49) in the last step. This completes the proof.

9.3 Lemmas on quantiles and the median estimator
In this section we prove several lemmas useful for analyzing the concentration properties of the median estimate.
We will use
44

Theorem 9.3 (Chernoff bound). Let
1 , . . . , Xn be independent 0/1 Bernoulli random variables with
PX
n
µ. Then for any δ > 1 one has Pr[ i=1 Xi > (1 + δ)µ] < e−δµ/3 .

Pn

i=1 E[Xi ]

Lemma 9.4 (Error bounds for the median estimator). Let X1 , . . . , Xn ∈ C be independent random variables.
Let Y := median(X1 , . . . , Xn ), where the median is applied coordinatewise. Then for any a ∈ C one has
|Y − a| ≤2median(|X1 − a|, . . . , |Xn − a|)
p
=2 median(|X1 − a|2 , . . . , |Xn − a|2 ).

Proof. Let i, j ∈ [n] be such that Y = re(Xi ) + i · im(Xj ). Suppose that re(Xi ) ≥ re(a) (the other case is
analogous). Then since re(Xi ) is the median in the list (re(X1 ), . . . , re(Xn )) by definition of Y , we have that
at least half of Xs , s = 1, . . . , n satisfy |re(Xs ) − re(a)| > |re(Xi ) − re(a)|, and hence
|re(Xi ) − re(a)| ≤ median(|re(X1 ) − re(a)|, . . . , |re(Xn ) − re(a)|).

(50)

Since squaring a list of numbers preserves the order, we also have
(re(Xi ) − re(a))2 ≤ median((re(X1 ) − re(a))2 , . . . , (re(Xn ) − re(a))2 ).

(51)

A similar argument holds for the imaginary part. Combining
|Y − a|2 = (re(a) − re(Xi ))2 + (im(a) − im(Xi ))2
with (50) gives
|Y − a|2 ≤median((re(X1 ) − re(a))2 , . . . , (re(Xn ) − re(a))2 )

+ median((im(X1 ) − im(a))2 , . . . , (im(Xn ) − im(a))2 )

Noting that
|Y − a| = ((re(a) − re(Xi ))2 + (im(a) − im(Xi ))2 )1/2 ≤ |re(a) − re(Xi )| + |im(a) − im(Xi )|
and using (51), we also get
|Y − a| ≤median(|re(X1 ) − re(a)|, . . . , |re(Xn ) − re(a)|)

+ median(|im(X1 ) − im(a)|, . . . , |im(Xn ) − im(a)|).

The results of the lemma follow by noting that |re(X) − re(a)| ≤ |X − a| and |im(X) − im(a)| ≤ |X − a|.
Lemma 9.5. Let X1 , . . . , Xn ≥ 0 be independent random variables with E[Xi ] ≤ µ for each i = 1, . . . , n.
Then for any γ ∈ (0, 1) if Y ≤ quantγ (X1 , . . . , Xn ), then
E[|Y − 4µ/γ|+ ] ≤ (µ/γ) · 2−Ω(n)
and
Pr[Y ≥ 4µ/γ] ≤ 2−Ω(n) .
Proof. For any t ≥ 1 by Markov’s inequality Pr[Xi > tµ/γ] ≤ γ/t. Define indicator random variables Zi by
letting Zi = 1 if Xi > tµ/γ and Zi = 0 otherwise. Note that E[Zi ] ≤ γ/t
Pnfor each i. Then since Y is bounded
n
above by the γn-th largest of {Xi }i=1 , we have Pr[Y > tµ/γ] ≤ Pr[ i=1 Zi ≥ γn]. As E[Zi ] ≤ γ/t, this
45

=

P
can only happen if the sum ni=1 Zi exceeds expectation by a factor of at least t. We now apply Theorem 9.3
to the sequence Zi , i = 1, . . . , n. We have
#
" n
X
Zi ≥ γn ≤ e−(t−1)γn/3
(52)
Pr
i=1

by Theorem 9.3 invoked with δ = t − 1. The assumptions of Theorem 9.3 are satisfied as long as t > 2. This
proves the second claim we have t = 4 in that case.
For the first claim we have
Z ∞
tµ · Pr[Y ≥ t · µ/γ]dt
E[Y · 1Y ≥4·µ/γ ] ≤
Z4 ∞
tµe−(t−1)n/3 dt
(by (52))
≤
4
Z ∞
≤ e−n/3
tµe−(t−2)n/3 dt
4
−n/3

= O(µ · e

)

as required.

10 Semi-equispaced Fourier Transform
In this section we give an algorithm for computing the semi-equispaced Fourier transform, prove its correctness
and give runtime bounds.
Algorithm 8 Semi-equispaced Fourier Transform in 2O(d) k logd N time
d

procedure S EMI E QUISPACED FFT(x, c)
⊲ x ∈ C[n] is k-sparse
2:
Let B ≥ 2d k, be a power of 2d , b = B 1/d
c′ ← d-th tensor powers of the flat window functions of [HIKP12a], see below
3:
G, G
n for i ∈ [2b]d .
4:
yi ← √1N (x ∗ G)i· 2b

1:

⊲ FFT on [2b]d

yb ← FFT(y)
6:
x
b′i ← ybi for ||i||∞ ≤ b/2.
7:
return x
b′
8: end procedure

5:

c′ as d-th tensor powers of the flat window functions of [HIKP12a], so that Gi = 0 for
We define filters G, G
all ||i||∞ & c(n/b) log N , kG − G′ k2 ≤ N −c ,

1 if ||i||∞ ≤ b/2
′
c
,
Gi=
0 if ||i||∞ > b

c′ i ∈ [0, 1] everywhere.
and G
The following is similar to results of [DR93, IKP14].

Lemma 10.1. Let n be a power of two, N = nd , c ≥ 2 a constant. Let integer B ≥ 1, be a power of 2d ,
d
b′i for all ||i||∞ ≤ b/2 such that
b = B 1/d . For any x ∈ C[n] Algorithm 8 computes x
in cO(d) ||x||0 logd N + 2O(d) B log B time.

|b
x′i − x
bi | ≤ kxk2 /N c
46

Proof. Define

1
z = √ x ∗ G.
N

bi for all i ∈ [n]d . Furthermore, because subsampling and aliasing are dual under the
We have that zbi = x
bi G
Fourier transform, since yi = zi·(n/2b) , i ∈ [2b]d is a subsampling of z we have for i such that ||i||∞ ≤ b/2 that
x
b′i = ybi =

X

j∈[n/(2b)]d

X

=

j∈[n/(2b)]d

X

=

j∈[n/(2b)]d

=

X

j∈[n/(2b)]d

zbi+2b·j

bi+2b·j
x
bi+2b·j G

c′ i+2b·j +
x
bi+2b·j G

c′ i+2b·j +
x
bi+2b·j G

X

j∈[n/(2b)]d

X

j∈[n/(2b)]d

c′ i+2b·j )
bi+2b·j − G
x
bi+2b·j (G

c′ i+2b·j ).
bi+2b·j − G
x
bi+2b·j (G

For the second term we have using Cauchy-Schwarz
X
c′ ||2 ≤ ||x||2 /N c .
c′ i+2b·j ) ≤ ||x||2 ||G
bi+2b·j − G
b−G
x
bi+2b·j (G
j∈[n/(2b)]d

For the first term we have

X

j∈[n/(2b)]d

c′ i+2b·j = x
c′ i+2b·0 = x
x
bi+2b·j G
bi · G
bi

c′ i+2b·j is larger than b in ℓ∞ norm,
for all i ∈ [2b]d such that ||i||∞ ≤ b, since for any j 6= 0 the argument of G
c′ i+2b·j = 0 for all j 6= 0.
and hence G
Putting these bounds together we get that
c′ k2 ≤ kxk2 N −c
b−G
|b
x′i − x
bi | ≤ kb
xk2 kG

as desired.
The time complexity of computing the FFT of y is 2O(d) B log B. The vector y can be constructed in time
O(d)
c
||x||0 logd N . This is because the support of Gi is localized so that each nonzero coordinate i of x only
contributes to cO(d) logd N entries of y.
We will need the following simple generalization:
Corollary 10.2. Let n be a power of two, N = nd , c ≥ 2 a constant, and Σ ∈ Md×d , q ∈ [n]d . Let integer
d
B ≥ 1 be a power of 2d , b = B 1/d . Let S = {Σ(i − q) : i ∈ Z, ||i||∞ ≤ b/2}. Then for any x ∈ C[n] we can
compute x
b′i for all i ∈ S time such that
|b
x′i − x
bi | ≤ kxk2 /N c

in cO(d) ||x||0 logd N + 2O(d) B log B time.

47

Proof. Define x∗j = ω qj xΣ−T j . Then for all i ∈ [n],
1 X −j T Σ(i−q)
x
bΣ(i−q) = √
ω
xj
N j∈[n]d

1 X −j T Σi j T Σq
ω
ω
xj
=√
N j∈[n]d

1
=√
N
1
=√
N
=

x
b∗i .

X

′ T

′ T

ω −(j ) i ω (j ) q xΣ−T j ′

j ′ =ΣT j∈[n]d

X

′ T

ω −(j ) i x∗j ′

j ′ =ΣT j∈[n]d

We can access x
b∗i with O(d2 ) overhead, so by Lemma 10.1 we can approximate x
bΣ(i−q) = x
b∗i for ||i||∞ ≤ k in
d
O(d)
c
k log N time.

11 Acknowledgements
The author would like to thank Piotr Indyk for many useful discussions at various stages of this work.

References
[AGS03]

A. Akavia, S. Goldwasser, and S. Safra. Proving hard-core predicates using list decoding. FOCS,
44:146–159, 2003.

[Aka10]

A. Akavia. Deterministic sparse Fourier approximation via fooling arithmetic progressions. COLT,
pages 381–393, 2010.

[BCG+ 12] P. Boufounos, V. Cevher, A. C. Gilbert, Y. Li, and M. J. Strauss. What’s the frequency, Kenneth?:
Sublinear Fourier sampling off the grid. RANDOM/APPROX, 2012.
[Bou14]

J. Bourgain. An improved estimate in the restricted isometry problem. GAFA, 2014.

[CCFC02] M. Charikar, K. Chen, and M. Farach-Colton. Finding frequent items in data streams. ICALP,
2002.
[CGV12]

M. Cheraghchi, V. Guruswami, and A. Velingker. Restricted isometry of Fourier matrices and list
decodability of random linear codes. SODA, 2012.

[Cip00]

B. A. Cipra. The Best of the 20th Century: Editors Name Top 10 Algorithms. SIAM News, 33,
2000.

[CP10]

E. Candes and Y. Plan. A probabilistic and ripless theory of compressed sensing. IEEE Transactions on Information Theory, 2010.

[CT06]

E. Candes and T. Tao. Near optimal signal recovery from random projections: Universal encoding
strategies. IEEE Trans. on Info.Theory, 2006.

[DIPW10] K. Do Ba, P. Indyk, E. Price, and D. Woodruff. Lower Bounds for Sparse Recovery. SODA, 2010.
48

[Don06]

D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52(4):1289–1306,
2006.

[DR93]

A. Dutt and V. Rokhlin. Fast fourier transforms for nonequispaced data. SIAM J. Sci. Comput.,
14(6):1368–1393, November 1993.

[GGI+ 02] A. Gilbert, S. Guha, P. Indyk, M. Muthukrishnan, and M. Strauss. Near-optimal sparse Fourier
representations via sampling. STOC, 2002.
[GHI+ 13] B. Ghazi, H. Hassanieh, P. Indyk, D. Katabi, E. Price, and L. Shi. Sample-optimal average-case
sparse Fourier transform in two dimensions. Allerton, 2013.
[GL89]

O. Goldreich and L. Levin. A hard-corepredicate for allone-way functions. STOC, pages 25–32,
1989.

[GLPS10] A. C. Gilbert, Y. Li, E. Porat, and M. J. Strauss. Approximate sparse recovery: optimizing time
and measurements. In STOC, pages 475–484, 2010.
[GMS05]

A. Gilbert, M. Muthukrishnan, and M. Strauss. Improved time bounds for near-optimal space
Fourier representations. SPIE Conference, Wavelets, 2005.

[HAKI12] H. Hassanieh, F. Adib, D. Katabi, and P. Indyk. Faster GPS via the Sparse Fourier Transform.
MOBICOM, 2012.
[HIKP12a] H. Hassanieh, P. Indyk, D. Katabi, and E. Price. Near-optimal algorithm for sparse Fourier transform. STOC, 2012.
[HIKP12b] H. Hassanieh, P. Indyk, D. Katabi, and E. Price. Simple and practical algorithm for sparse Fourier
transform. SODA, 2012.
[HKPV13] S. Heider, S. Kunis, D. Potts, and M. Veit. A sparse Prony FFT. SAMPTA, 2013.
[HR16]

I. Haviv and O. Regev. The restricted isometry property of subsampled fourier matrices. SODA,
2016.

[IK14]

P. Indyk and M. Kapralov. Sample-optimal Fourier sampling in any fixed dimension. FOCS, 2014.

[IKP14]

P. Indyk, M. Kapralov, and E. Price. (Nearly) sample-optimal sparse Fourier transform. SODA,
2014.

[Iwe10]

M. A. Iwen. Combinatorial sublinear-time Fourier algorithms. Foundations of Computational
Mathematics, 10:303–338, 2010.

[Iwe12]

M.A. Iwen. Improved approximation guarantees for sublinear-time Fourier algorithms. Applied
And Computational Harmonic Analysis, 2012.

[KM91]

E. Kushilevitz and Y. Mansour. Learning decision trees using the Fourier spectrum. STOC, 1991.

[LDSP08] M. Lustig, D.L. Donoho, J.M. Santos, and J.M. Pauly. Compressed sensing mri. Signal Processing
Magazine, IEEE, 25(2):72–82, 2008.
[LWC12]

D. Lawlor, Y. Wang, and A. Christlieb.
arXiv:1207.6368, 2012.

[Man92]

Y. Mansour. Randomized interpolation and approximation of sparse polynomials. ICALP, 1992.
49

Adaptive sub-linear time fourier algorithms.

[PR13]

S. Pawar and K. Ramchandran. Computing a k-sparse n-length Discrete Fourier Transform using
at most 4k samples and O(klogk) complexity. ISIT, 2013.

[PS15]

E. Price and Z. Song. A robust sparse Fourier transform in the continuous setting. FOCS, 2015.

[RV08]

M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. CPAM, 61(8):1025–1171, 2008.

[Sid11]

Emil Sidky. What does compressive sensing mean for X-ray CT and comparisons with its MRI
application. In Conference on Mathematics of Medical Imaging, 2011.

A

Omitted proofs

Proof of Lemma 2.11: We start with
t
EΣ,q [|π(S \ {i}) ∩ B∞
(n/b)·h(i) ((n/b) · 2 )|] =

X

j∈S\{i}

t
PrΣ,q [π(j) ∈ B∞
(n/b)·h(i) ((n/b) · 2 )]

(53)

Recall that by definition of h(i) one has ||(n/b) · h(i) − π(i)||∞ ≤ (n/b), so by triangle inequality
||π(j) − π(i)||∞ ≤ ||π(j) − (n/b)h(i)||∞ + ||π(i) − (n/b)h(i)||∞ ,
so
t
EΣ,q [|π(S \ {i}) ∩ B∞
(n/b)·h(i) ((n/b) · 2 )|] ≤

≤

X

j∈S\{i}

X

j∈S\{i}

t
PrΣ,q [π(j) ∈ B∞
π(i) ((n/b) · (2 + 1))]
t+1
PrΣ,q [π(j) ∈ B∞
)]
π(i) ((n/b) · 2

(54)

Since πΣ,q (i) = Σ(i − q) for all i ∈ [n]d , we have
t+1
PrΣ,q [π(j) ∈ B∞
)] = PrΣ,q [||Σ(j − i)||∞ ≤ (n/b) · 2t+1 ] ≤ 2(2t+2 /b)d ,
π(i) ((n/b) · 2

where we used the fact that by Lemma 2.5, for any fixed i, j 6= i and any radius r ≥ 0,
PrΣ [kΣ(i − j)k∞ ≤ r] ≤ 2(2r/n)d

(55)

with r = (n/b) · 2t+1 .
Putting this together with (54), we get
t
t+2
EΣ,q [|π(S \ {i}) ∩ B∞
/b)d ≤ (|S|/B) · 2(t+2)d+1
(n/b)·h(i) ((n/b) · 2 )|] ≤ |S| · 2(2
1
≤ (2π)−d·F · 64−(d+F ) αd 2(t+2)d+1 .
4
Now by Markov’s inequality we have that i fails to be isolated at scale t with probability at most
i 1
h
t
−d·F
−(d+F ) d/2 (t+2)d+t+1
≤ 2−t αd/2 .
((n/b)
·
2
)|
>
(2π)
·
64
α
2
PrΣ,q |π(S \ {i}) ∩ B∞
π(i)
4
Taking the union bound over all t ≥ 0, we get
X1
1
1
PrΣ,q [i is not isolated] ≤
2−t αd/2 ≤ αd/2 ≤ α1/2
4
2
2
t≥0

as required.
Before giving a proof of Lemma 2.9, we state the following lemma, which is immediate from Lemma 9.2:
50

Lemma A.1. Let x, x1 , x2 , χ, χ1 , χ2 ∈ CN , x = x1 + x2 , χ = χ1 + χ2 . Let Σ ∈ Md×d , q, a ∈ [n]d ,
B = bd , b ≥ 2 an integer. Let
u = H ASH T O B INS (x̂, χ, (H, a))
u1 = H ASH T O B INS (c
x1 , χ1 , (H, a))

u2 = H ASH T O B INS (c
x2 , χ2 , (H, a)).

Then for each j ∈ [b]d one has
T Σi

−a
|G−1
oi (i) uj ω

T Σi

1 −a
− (x − χ)i |p . |G−1
oi (i) uj ω

+ N −Ω(c)

T Σi

2 −a
− (x1 − χ1 )i |p + |G−1
oi (i) uj ω

− (x2 − χ2 )i |p

for p ∈ {1, 2}, where O(c) is the word precision of our semi-equispaced Fourier transform computations.
Proof of Lemma 2.9: By Lemma 2.5, for any fixed i and j and any t ≥ 0,
PrΣ [kΣ(i − j)k∞ ≤ t] ≤ 2(2t/n)d .
Per Lemma 9.2, H ASH T O B INS computes the vector u ∈ CB given by
X
T
uh(i) − ∆h(i) =
Goi (j) x′j ω a Σj

(56)

j∈[n]d

for some ∆ with k∆k2∞ ≤ N −Ω(c) . We define the vector v ∈ Cn by vΣj = x′j Goi (j) , so that
uh(i) − ∆h(i) =
so

T Σi

uh(i) − ω a

X

T

ω a j vj =

j∈[n]d

Goi (i) x′i − ∆h(i) =

√

√

N vba

) .
N (v[
{Σi} a

We have by (56) and the fact that (X + Y )2 ≤ 2X 2 + 2Y 2
T Σi

−a
|G−1
oi (i) ω

T Σi

a
uh(i) − x′i |2 = G−2
oi (i) |uh(i) − ω
T Σi

Goi (i) x′i |2

2
Goi (i) x′i − ∆h(i) |2 + 2G−2
oi (i) ∆h(i)
X
T
2
= 2G−2
Goi (j) x′j ω a Σj |2 + 2G−2
oi (i) |
oi (i) ∆h(i)

a
≤ 2G−2
oi (i) |uh(i) − ω

j∈[n]d

By Parseval’s theorem, therefore, we have
T Σi

−a
Ea [|G−1
oi (i) ω

uh(i) − x′i |2 ] ≤ 2G−2
oi (i) Ea [|

X

T Σj

Goi (j) x′j ω a

j∈[n]d

2
2
= 2G−2
oi (i) (kv{Σi} k2 + ∆h(i) )
X
. N −Ω(c) +
|x′j Goi (j) |2
j∈[n]d \{i}

. N −Ω(c) +

X

j∈[n]d \{i}

. N −Ω(c) + µ2Σ,q (i).
51

|x′j Goi (j) |2

|2 ] + 2Ea [∆2h(i) ]

(57)

We now prove (2). Recall that the filter G approximates an ideal filter, which would be 1 inside B∞
0 (n/b)
and 0 everywhere else. We use the bound on Goi (j) = Gπ(i)−π(j) in terms of ||π(i) − π(j)||∞ from Lemma 2.3,
(2). In order to leverage the bound, we partition [n]d = B∞
(n/b)·h(i) (n/2) as
B∞
(n/b)·h(i) (n/2)

=

B∞
(n/b)·h(i) (n/b)

∪

log2 (b/2) 

[

t=1


t
∞
t−1
B∞
((n/b)2
)
\
B
((n/b)2
)
.
(n/b)·h(i)
(n/b)·h(i)

t
∞
t−1 )
For simplicity of notation, let X0 =
and Xt = B∞
(n/b)·h(i) ((n/b) · 2 ) \ B(n/b)·h(i) ((n/b) · 2
for t ≥ 1. For each t ≥ 1 we have by Lemma 2.3, (2)
F

2
.
max
|Goi (l) | ≤
max |Goi (l) | ≤
1 + 2t−1
π(l)∈Xt
π(l)6∈B∞
((n/b)2t−1 )
(n/b)·h(i)

B∞
(n/b)·h(i) (n/b)

Since the rhs is greater than 1 for t ≤ 0, we can use this bound for all t ≤ log2 (b/2). Further, by Lemma 2.5
we have for each j 6= i and t ≥ 0
t
t+1
PrΣ,q [π(j) ∈ Xt ] ≤ PrΣ,q [π(j) ∈ B∞
/b)d .
(n/b)·h(i) ((n/b) · 2 )] ≤ 2(2

Putting these bounds together, we get
EΣ,q [µ2Σ,q (i)] = EΣ,q [

X

j∈[n]d \{i}

≤
≤
≤

log2 (b/2)

X

|x′j |2

X

|x′j |2

j∈[n]d \{i}

X

j∈[n]d \{i}

≤ 2O(d)

X

·

PrΣ,q [π(j) ∈ Xt ] · max |Goi (l) |
π(l)∈Xt

t=0

log2 (b/2)

j∈[n]d \{i}

2F
B

|x′j Goi (j) |2 ]

X

·

(2

t=0

|x′j |2

kx′ k22
B

t+1

+∞
X

d

/b) ·



2
1 + 2t−1

F

2(t+1)d−F (t−1)

t=0

d·F completes the proof of (2).
as long as F ≥ 2d and F = Θ(d). Recalling that G−1
oi (i) ≤ (2π)
The proof of (1) is similar. We have
X
X
T
EΣ,q [ max |
x′j Goi (j) ω a Σj |] ≤ EΣ,q [
|x′j Goi (j) |] + |∆h(i) |
a∈[n]d

j∈[n]d \{i}

j∈[n]d \{i}

≤ |∆h(i) | +
≤ |∆h(i) | +
≤ |∆h(i) | +

log2 (b/2)

X

|x′j |

X

|x′j |

j∈[n]d \{i}

X

j∈[n]d \{i}
′
O(d) kx k1

≤ |∆h(i) | + 2

PrΣ,q [π(j) ∈ Xt ] · max |Goi (l) |
π(l)∈Xt

t=0

log2 (b/2)

j∈[n]d \{i}

2F
B

X

·

B

·

|x′j |

X
t=0

+∞
X

t+1

(2

d

/b) ·



2
1 + 2t−1

F

2(t+1)d−F (t−1)

t=0

,

(58)
52

where
∆h(i) . N −Ω(c) .
d·F and R∗ ≤ ||x|| /µ completes the proof of (1).
Recalling that G−1
∞
oi (i) ≤ (2π)

53

