The oldest combinatorial algorithms were developed in the context of group testing [6], [12], [14]. In the group testing problem, we suppose that there are NN total items, of which an unknown subset of KK elements are anomalous and need to be identified. For example, we might wish to identify defective products in an industrial setting, or identify a subset of diseased tissue samples in a medical context. In both of these cases the vector xx indicates which elements are anomalous, i.e., xi≠0xi≠0 for the KK anomalous elements and xi=0xi=0 otherwise. Our goal is to design a collection of tests that allow us to identify the support (and possibly the values of the nonzeros) of xx while also minimizing the number of tests performed. In the simplest practical setting these tests are represented by a binary matrix ΦΦ whose entries φijφij are equal to 1 if and only if the j th j th item is used in the i th i th test. If the output of the test is linear with respect to the inputs, then the problem of recovering the vector xx is essentially the same as the standard sparse recovery problem.

Another application area in which combinatorial algorithms have proven useful is computation on data streams [4], [13]. Suppose that xixi represents the number of packets passing through a network router with destination ii. Simply storing the vector xx is typically infeasible since the total number of possible destinations (represented by a 32-bit IP address) is N=232N=232. Thus, instead of attempting to store xx directly, one can store y=Φxy=Φx where ΦΦ is an M×NM×N matrix with M≪NM≪N. In this context the vector yy is often called a sketch. Note that in this problem yy is computed in a different manner than in the compressive sensing context. Specifically, in the network traffic example we do not ever observe xixi directly; rather, we observe increments to xixi (when a packet with destination ii passes through the router). Thus we construct yy iteratively by adding the i th i th column to yy each time we observe an increment to xixi, which we can do since y=Φxy=Φx is linear. When the network traffic is dominated by traffic to a small number of destinations, the vector xx is compressible, and thus the problem of recovering xx from the sketch ΦxΦx is again essentially the same as the sparse recovery problem.

Several combinatorial algorithms for sparse recovery have been developed in the literature. A non-exhaustive list includes Random Fourier Sampling [9], HHS Pursuit [9], and Sparse Sequential Matching Pursuit [1]. We do not provide a full discussion of each of these algorithms; instead, we describe two simple methods that highlight the flavors of combinatorial sparse recovery — count-min and count-median.

Define HH as the set of all discrete-valued functions h:{1,...,N}→{1,...,m}h:{1,...,N}→{1,...,m}. Note that HH is a finite set of size mNmN. Each function h∈Hh∈H can be specified by a binary characteristic matrix φ(h)φ(h) of size m×Nm×N, with each column being a binary vector with exactly one 1 at the location jj , where j=h(i)j=h(i). To construct the overall sampling matrix ΦΦ, we choose dd functions h1,...,hdh1,...,hd independently from the uniform distribution defined on HH, and vertically concatenate their characteristic matrices. Thus, if M=mdM=md, ΦΦ is a binary matrix of size M×NM×N with each column containing exactly dd ones.

Now given any signal xx, we acquire linear measurements y=Φxy=Φx. It is easy to visualize the measurements via the following two properties. First, the coefficients of the measurement vector yy are naturally grouped according to the “mother” binary functions {h1,...,hd}{h1,...,hd}. Second, consider the ithith coefficient of the measurement vector yy, which corresponds to the mother binary function hh. Then, the expression for yiyi is simply given by:

In other words, for a fixed signal coefficient index jj, each measurement yiyi as expressed above consists of an observation of xjxj corrupted by other signal coefficients mapped to the same ii by the function hh. Signal recovery essentially consists of estimating the signal values from these “corrupted" observations.

The count-min algorithm is useful in the special case where the entries of the original signal are positive. Given measurements yy using the sampling matrix ΦΦ as constructed above, the estimate of the j th j th signal entry is given by:

Intuitively, this means that the estimate of xjxj is formed by simply looking at all measurements that comprise of xjxj corrupted by other signal values, and picking the one with the lowest magnitude. Despite the simplicity of this algorithm, it is accompanied by an arguably powerful instance-optimality guarantee: if d=ClogNd=ClogN and m=4/αKm=4/αK, then with high probability, the recovered signal x^x^ satisfies:

where x*x* represents the best KK-term approximation of xx in the ℓ1ℓ1 sense.

For the general setting when the coefficients of the original signal could be either positive or negative, a similar algorithm known as count-median can be used. Instead of picking the minimum of the measurements, we compute the median of all those measurements that are comprised of a corrupted version of xjxj and declare it as the signal coefficient estimate, i.e.,

The recovery guarantees for count-median are similar to that for count-min, with a different value of the failure probability constant. An important feature of both count-min and count-median is that they require that the measurements be perfectly noiseless, in contrast to optimization/greedy algorithms which can tolerate small amounts of measurement noise.

Although we ultimately wish to recover a sparse signal from a small number of linear measurements in both of these settings, there are some important differences between such settings and the compressive sensing setting studied in this course. First, in these settings it is natural to assume that the designer of the reconstruction algorithm also has full control over ΦΦ, and is thus free to choose ΦΦ in a manner that reduces the amount of computation required to perform recovery. For example, it is often useful to design ΦΦ so that it has few nonzeros, i.e., the sensing matrix itself is also sparse [2], [7], [11]. In general, most methods involve careful construction of the sensing matrix ΦΦ, which is in contrast with the optimization and greedy methods that work with any matrix satisfying a generic condition such as the restricted isometry property. This additional degree of freedom can lead to significantly faster algorithms [3], [5], [8], [10].

Second, note that the computational complexity of all the convex methods and greedy algorithms described above is always at least linear in NN, since in order to recover xx we must at least incur the computational cost of reading out all NN entries of xx. This may be acceptable in many typical compressive sensing applications, but this becomes impractical when NN is extremely large, as in the network monitoring example. In this context, one may seek to develop algorithms whose complexity is linear only in the length of the representation of the signal, i.e., its sparsity KK. In this case the algorithm does not return a complete reconstruction of xx but instead returns only its KK largest elements (and their indices). As surprising as it may seem, such algorithms are indeed possible. See [8], [10] for examples.