Among the historically oldest of all sparse recovery algorithms were developed in the context of combinatorial group testing [2], [3], [5]. In this problem we suppose that there are NN total items and KK anomalous elements that we wish to find. 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 in compressive sensing.

Another application area in which ideas related to compressive sensing have proven useful is computation on data streams [1], [4]. As an example of a typical data streaming problem, 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 in compressive sensing.