\section{Overview of Techniques and Comparison with Previous Work}\label{sec:tech}


We first note that it is easy to \emph{augment} a disjunct matrix to provide
sublinear time recovery at cost of a logarithmic factor increase in the number
of tests. This can be done via a simple \emph{bit-masking} scheme, as 
for example used in \cite{ref:CR19b,lee2019saffron,ref:BCSYZ19} (a similar
method has been used in the context of compressed sensing and heavy hitters in 
\cite{ref:GSTV06, ref:BGIKS08, ref:CI17}).

That is, via the best known explicit constructions, to obtain a disjunct matrix with $O(k^2 \log^2 n)$ rows and similar decoding time, and a list-disjunct matrix with $O(k \log^2(n/k))$ rows and similar decoding time. 

On the other hand, much effort in the sparse recovery literature have been dedicated to simultaneously obtaining the ``ultimate goal'' of optimal number of measurements and near-linear decoding time \cite{ch09,gi10,indyk2010efficiently, icalp11, bi11,glps12, gnprs13, lnnt16, nakos2017deterministic_heavy_hitters,glps17,cai2017efficient,lee2019saffron,bondorf2019sublinear}, including work on the related Sparse Fourier Transform problem \cite{hikp12a,hikp12b,ik14,k16,k17,cksz17,kvz19}. In general, attaining the ultimate goal requires novel approaches and sophisticated techniques.

The approach of \cite{ch2009noise} lies in connecting disjunct and list-disjunct matrices (and related objects that suffice for the group testing problem) to randomness extractors and bipartite expanders, and then using the nice list-decoding properties of specific instantiations of those objects. The approach of \cite{indyk2010efficiently} is again closely related to list-recoverable codes. In a nutshell, the authors consider a variant of code concatenation, where the inner code is a random code that gives a list-disjunct matrix, and the outer code is a Reed-Solomon code. The concatenated code enables list-recovery, returning a list of size $O(k^2)$, which can then be filtered out using Lemma~\ref{lem:point_query_list_disjunct}. One of the crucial observations of that work is that it is sufficient to use an inner code which forms a list-disjunct matrix instead of a disjunct matrix, an approach that would require $\Omega(k^3 \log n/ \log k)$ rows. 

The first approach of \cite{icalp11} for list-disjunct is again a reduction to list-recoverable codes, making use of the list-decoding view of Parvaresh-Vardy codes. The second approach is to apply recursively the trivial list-recoverable code of block size $2$. In particular, they group together coordinates that agree in the first $(\log n)/2$ bits, and use a list-disjunct matrix in this instance to obtain a list $L_1$. Second, they group together coordinates that agree in the second $(\log n)/2$ bits and obtain a list $L_2$ using, again, a list-disjunct matrix. Thus, they can guarantee that the set of defective items lies in the set $L_1 \times L_2$, which is much smaller than $n$. Applying the same idea recursively and observing that the universe shrinks by a square root factor in each recursive call, yields in total a running time of $O(k^2 \poly(\log n))$ and a slight sub-optimality in the number of rows. This technique has also found use in subsequent works, such as \cite{ps12,gnprs13,nakos2017deterministic_heavy_hitters,inan2019optimality}. Instead of the trivial list-recoverable code, a slightly more efficient one based on the Loomis-Whitney inequality~\cite{gnprs13,nprr18} can be used, but this leads to a much less clean trade-off between the number of rows and the decoding time, and the total scheme is still sub-optimal in both measurement and time complexity.

There are many other papers that (possibly with minor modifications) implicit or explicitly construct efficiently decodable list-disjunct matrices, \cite{cai2013grotesque,cai2017efficient,lee2019saffron,bondorf2019sublinear} to name a few. However, all of those approaches fall short of bypassing the barriers mentioned in the first paragraph of this section and thus obtaining the ``ultimate goal'' of group testing.

Our approach departs from previous work and is inspired by the solution for the case $k=1$. First of all, we observe that it suffices to solve a slightly weaker-- but as it turns out crucially easier-- problem: find a list of size $O(k \log (n/k))$ that contains all defective items, or in other words construct a $(k, O(k \log(n/k)))$-list disjunct matrix, the decoding routine of which appears to be linear in the number of rows, as we show below. In particular, for every $\ell \in \{\log k,\ldots, \log n\}$, we group every coordinate which agrees in the first $\ell$ bits into a single coordinate, and then hash the single coordinate to $O(k)$ buckets. This yields in total $O(k \log (n/k))$ samples. Our algorithm then starts from $\ell = \log k$ and processes prefixes in increasing length $\ell$, trying to gradually find the prefixes of all the defective items, by discarding prefixes that do not participate in a positive test. Our proof roughly proceeds by showing that the number of possible trajectories of the non-defective items can be upper-bounded by the Catalan number of order $\Theta(k \log (n/k))$. The hashing scheme then allows for a union-bound over all possible supports and all possible trajectories. This immediately gives that the output list might contain up to $O(k \log (n/k))$ coordinates, which completes the proof. Our argument can facilitate up to $O(k)$ false positives, or even up to $O(k \log (n/k))$ if they are not ``very'' adversarially chosen; the latter guarantee (more than) suffices for our application to the heavy hitters problem. 

For the error-correcting schemes and the $\ell_2/\ell_2$ weak system, we need delicate twists in the hashing scheme and more involved analyses which make use of the generalized Catalan numbers to bound the running time. Unfortunately for $\ell_2/\ell_2$ compressed sensing the argument is not as clean (though the algorithm is still quite compact), but happens to be quite subtle on the technical level, mostly because one needs to handle dependent events carefully. Our approach is distinct from every previous work on the topic in several ways. Lastly, we also provide a novel reduction from near-linear decodable error-correcting disjunct matrices to ``less'' efficiently decodable error-correcting list-disjunct matrices, which does not require list-recoverability as the reductions in \cite{ch09,indyk2010efficiently}. 

From a coding theoretic perspective, one can view that the key to our progress is bypassing the ``for-all'' demand of list-recoverable codes: list-recovery ensures that for all choices of lists corresponding to symbols of the codeword, some ``desirable'' condition holds, namely that the set of possible codewords agreeing with all symbol-lists is small. In our case, we show that this is not needed, since the lists not only depend on the hidden set of defective items, but also are formed in a serial fashion, while one learns the bits of the defective items in chunks of appropriate size. 


\vspace{-4mm}
\paragraph{Connection to Tree Codes.} The above discussion might bear similarities to the constructions of tree codes \cite{treecodes91}. For alphabets $\Sigma, \Gamma$ and parameters $s,\delta$, a (truncated) tree code is a function $T\colon \bigcup_{r=1}^s \Sigma^r \rightarrow \bigcup_{r=1}^s \Gamma^r$ such that the Hamming distance of $T(x,x')$ for every two $x,x' \in \bigcup_{j=1}^s \Sigma^j$ is at least  $\delta \cdot (s- \mathrm{split}(x,x'))$, where $\mathrm{split}(x,x')$ is the largest index $i$ for which $x_j = x_j'$ for all $j \leq i$. In our case, one could imagine setting $s=\log n, \Sigma = \{0,1\}$ and $\Gamma = \{0,1\}^{\log k + O(1)}$ to pass to an efficiently decodable $k$-disjunct matrix. However, it turns out that the structural condition demanded by tree codes is too strong (and rather inflexible when trying to perform a disjunct or list-disjunct matrix construction) for group testing applications, as tree codes demand a worst-case Hamming distance bound between any two strings $x,x'$. On the other hand, what our approach requires is a Hamming distance bound that holds \emph{on~average}.
\vspace{-4mm}
\paragraph{Sublinear-Time Sparse Recovery Frameworks.}

In the sparse recovery literature, there are in principle two available frameworks for sublinear-time decoding. The first includes, as mentioned in the first paragraph of this section, bit-masking with an error-correcting code. This approach is particularly effective in compressed sensing tasks (such as $\ell_2/\ell_2$) where it is not necessary to detect every heavy coordinate of the vector $x\in \mathbb{R}^n$. In that case, one can recover a constant fraction of the coordinates and then exploit the linearity of the sketch in order to set up a clean-up process. This can be achieved by subtracting from $x$ the detected coordinates~\cite{bi11,glps12,hikp12a,hikp12b,gnprs13,k16,k17,lnw17,cksz17,ref:CI17}, in order to recover a heavy enough subset of the top $k$ coordinates rather than all of them. This bit-masking plus clean-up process is less effective for heavy hitters because one desires to recover \emph{all~of~them} rather than a constant fraction. It is not applicable to group testing, for subtraction is not possible in that model. Moreover, bit-masking always results in measurement-\emph{sub-optimal} schemes in the ``for-all'' case in every variation of the sparse recovery problem. 


The other available framework is based on list-recoverable codes and related techniques \cite{ch2009noise,indyk2010efficiently,icalp11,gnprs13,lnnt16,glps17,nakos2017deterministic_heavy_hitters}. This type of machinery is more powerful in the ``for-all'' model, yielding better bounds in terms of measurement complexity, but it usually comes with a  polynomial in $k$ decoding time and complicated algorithms.


Our approach adds one more framework to the sparse recovery toolkit, and we demonstrate its power by obtaining a sequence of new and essentially optimal results that were not possible using previous arguments. We believe that further progress in the field could stem from hybrid approaches that combine more than one framework.
{"config": "arxiv", "file": "2006.08420/techniques.tex"}