16 to~22 in Algorithm~\ref{alg:estimate-efficient} and lines~25-36 in Algorithm~\ref{alg:main-sublinear}) using two loops. The first loop (over $r$), controls the $\ell_1$ norm of the signal, with the (upper bound on the) norm being reduced by a factor of $4$ in each iteration. This reduction is achieved via a sequence of calls to \textsc{EstimateValues} (in \textsc{Estimate}, Algorithm~\ref{alg:estimate-efficient}) or \textsc{LocateSignal} (in Section~\ref{sec:location}) using a separate collection of  hashings for each $t=1,\ldots, T$. Our correctness analysis for this process proceeds by showing that, with high constant probability over the choice of the hashings $\{\{H_{t, s}\}_{s=1}^{R_t}\}_{t=1}^T$ any set $S$ of size $\approx k$ the hashings induce a partition of $S$ into at most $T$ sets $S_1\cup\ldots\cup S_T$ such that hashings used in the $t$-th round allow the algorithm to make progress on elements in $S_t$. The main result of this section is a formalization of this claim, achieved by  Lemma~\ref{lm:l1b-head}.

\begin{lemma}\label{lm:l1b-head}
For every integer $k\geq 1$, every $S\subseteq {[n]}, |S|\leq k$,  every $\delta\in (0, 1/2)$, if the parameters $B_t, R_t$ are selected to satisfy {\bf (p1)} $R_t=C_1\cdot 2^t$ and {\bf (p2)} $B_t\geq C_2\cdot k/R_t^2$ for every $t\in [0:T]$, where $C_1$ is a sufficiently large constant and $C_2$ is sufficiently large as a function of $C_1$ and $\delta$, then the following conditions hold.  


For every collection of hashings $\{\{H_{t, s}\}_{s=1}^{R_t}\}_{t=1}^T$, if the filters used in hashings $H_{t, s}$ are at $F$-sharp for even $F\geq 6$ for every $t\in [1:T]$, and $S$ admits a $\delta$-isolating partition (as per Definition~\ref{def:isolating-partition}) $S=S_1\cup\ldots\cup S_T$ with respect to $\{H_{t, s}\}$, then for every $x, \chi\in \mathbb{C}^n, x'=x-\chi$, 
for every $t\in [1:T]$  one has 
$||e^{head}_{S_t}(\{H_{t, s}\}_{s\in [1:R_t]}, x')||_1\leq 20 R_t^{-\delta}||x'_S||_1$.
\end{lemma}

\begin{remark}\label{rm:overview}
Note that the result of Lemma~\ref{lm:l1b-head} implies that the cumulative error induced by the entire set $S$ of `heavy' coefficients on $S_t$ is only a $\approx R_t^{-\delta}$ fraction of the $\ell_1$ norm of $x'_S$, despite the fact that when estimating $S_t$ we hash into $B_t\ll k$ buckets, and in general each bucket will contain many elements of $S$. Furthermore, if we choose $R_t$ to increase fast enough so that $\sum_{t\geq 1} R_t^{-\delta}\ll 1$, we get that the cumulative contribution of elements in $S$ to estimation/location error over all $t\geq 1$ is less than $1$, meaning that errors do not accumulate much. This is exactly what we achieve by setting $R_t=C_1 2^t$ for a large constant $C_1>1$ -- see proof of Lemma~\ref{lm:main-estimate-snr-reduction} in Section~\ref{sec:est}.
\end{remark}

In the rest of the section we first introduce relevant notation and in particular define the central notion of an {\em isolating partition} of the set $S$ of head elements (in section~\ref{sec:notation-isolating}), then prove that any fixed set $S$ of size about $k$ admits an isolating partition with at least high constant probability over the choice of hashings $\{\{H_{t, s}\}_{s=1}^{R_t}\}_{t=1}^T$ (section~\ref{sec:partitions-exist}), and show how to construct the partition efficiently (Lemma~\ref{lm:construct-partition-runtime}) if the set $S$ is given explicitly (used in Algorithm~\ref{alg:estimate-efficient}, line~13). Using this result we then give a proof of Lemma~\ref{lm:l1b-head}. 


\subsection{Main definitions}\label{sec:notation-isolating}
Let $S$ be any subset of ${[n]}$ (we will later instantiate $S$ to the set of `large' elements of $x$).  We now define a decomposition of the set $S$ into $T=\frac1{1-\delta}\log_2 \log (k+1)+O(1)$ disjoint sets $S_1,S_2,\ldots, S_T$ with respect to a sequence $1\leq R_0\leq R_1 \leq R_2\leq \ldots\leq R_T$ and hashings $\{\{H_{t, s}\}_{s=1}^{R_t}\}_{t=1}^T$.  We start with several auxiliary definitions.

\begin{definition}[$t$-Collision]
We say that an element $a\in [n]$ participates in a $t$-collision with another element $b\in [n]$ under hashing $H=(\pi, B, F)$ if $a$ hashes within at most $t$ buckets of $b$ under  $H$, i.e. if $|\pi(a)-\pi(b)|\leq \frac{n}{B}(t-1)$.
\end{definition}


\begin{definition}[$\delta$-bad element]\label{def:bad}
For $\delta\in (0, 1)$, for each $t\in [1:T]$, sequence $1\leq R_0\leq R_1\leq\ldots\leq R_T$, where $T\geq 1$ is an integer, 
we say that an element $a$ of $S$ is {\em $\delta$-bad for $S_t$} with respect to a partition $S=S_1\cup S_2\cup\ldots\cup S_T$ and hashings $\{\{H_{t, s}\}_{s=1}^{R_t}\}_{t=1}^T$ if $a$ participates in an $R_t$-collision with at least one element of $S_t$ under more than a $R_t^{-\delta}$ fraction of hashings $H_{t, 1},\ldots, H_{t, R_t}$.
 \end{definition}


 
 \begin{definition}[$\lambda$-crowded element]\label{def:lambda-crowded}
For a hashing $H=(\pi, B, F)$ and a real number $\lambda\in (0, 1)$, an element $a\in {[n]}$ is $\lambda$-crowded at scale $q\geq 0$ by a set $Q\subseteq {[n]}$ if 
$\left|\mathbb{B}\left(\pi(a), \frac{n}{B}\cdot 2^q\right) \cap \pi(Q\setminus \{a\})\right|\geq \lambda 2^{2q}$. We say that an element $a$ is simply $\lambda$-crowded if it is $\lambda$-crowded at least at one scale $q\geq 0$.
\end{definition}
\begin{remark}
The intuition for the definition above is that if the permutation $\pi$ was pairwise independent,  then for every $a\in {[n]}$ the expectation of $\left|\mathbb{B}\left(\pi(a), \frac{n}{B}\cdot 2^q\right) \cap \pi(Q\setminus \{a\})\right|$ would be about $2^{q}$ if $|Q|\leq B$, i.e. about the number of buckets that fall into the interval. We say that an element is $\lambda$-crowded when the number of elements in its vicinity exceeds $\lambda 2^{2q}$ for at least one scale $q$, i.e. exceeds expectation by a $\lambda 2^{q}$ factor. Our choice of $\lambda=R_t^{-3}$ serves the purpose of enforcing that no element of $S_t$ is hashed too close to another element of $S_t$, and no (large) neighborhood of any element of $S_t$ it too crowded. These two parameter regimes have somewhat distinct applications in the proof of Lemma~\ref{lm:l1