Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » An Introduction to Compressive Sensing » Combinatorial algorithms

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Combinatorial algorithms

Module by: Mark A. Davenport, Chinmay Hegde. E-mail the authors

Summary: This module introduces the count-min and count-median sketches as representative examples of combinatorial algorithms for sparse recovery.

In addition to convex optimization and greedy pursuit approaches, there is another important class of sparse recovery algorithms that we will refer to as combinatorial algorithms. These algorithms, mostly developed by the theoretical computer science community, in many cases pre-date the compressive sensing literature but are highly relevant to the sparse signal recovery problem.

Setup

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., xi0xi0 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 MNMN. 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.

The count-min sketch

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 hHhH 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:

y i = j : h ( j ) = i x j . y i = j : h ( j ) = i x j .
(1)

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:

x ^ j = min l y i : h l ( j ) = i . x ^ j = min l y i : h l ( j ) = i .
(2)

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:

x - x ^ α / K · x - x * 1 , x - x ^ α / K · x - x * 1 ,
(3)

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

The count-median sketch

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.,

x ^ j = median l y i : h l ( j ) = i . x ^ j = median l y i : h l ( j ) = i .
(4)

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.

Summary

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.

References

  1. Berinde, R. and Indyk, P. (2010). Sequential sparse matching pursuit. In Communication, Control, and Computing, 2009. Allerton 2009. 47th Annual Allerton Conference on. (p. 36–43). IEEE.
  2. Baron, D. and Sarvotham, S. and Baraniuk, R. (2006, Jul.). Sudocodes - Fast Measurement and Reconstruction of Sparse Signals. In Proc. IEEE Int. Symp. Inform. Theory (ISIT). Seattle, WA
  3. Charikar, M. and Chen, K. and Farach-Colton, M. (2002, Jul.). Finding frequent items in data streams. In Proc. Int. Coll. Autom. Lang. Programm. Málaga, Spain
  4. Cormode, G. and Hadjieleftheriou, M. (2009). Finding the frequent items in streams of data. Comm. ACM, 52(10), 97–105.
  5. Cormode, G. and Muthukrishnan, S. (2005). Improved data stream summaries: The count-min sketch and its applications. J. Algorithms, 55(1), 58–75.
  6. Erlich, Y. and Shental, N. and Amir, A. and Zuk, O. (2009, Sept.). Compressed sensing approach for high throughput carrier screen. In Proc. Allerton Conf. Communication, Control, and Computing. Monticello, IL
  7. Gilbert, A. and Indyk, P. (2010). Sparse recovery using sparse matrices. Proc. IEEE, 98(6), 937–947.
  8. Gilbert, A. and Li, Y. and Porat, E. and Strauss, M. (2010, Jun.). Approximate sparse recovery: Optimizaing time and measurements. In Proc. ACM Symp. Theory of Comput. Cambridge, MA
  9. Gilbert, AC and Strauss, MJ and Tropp, JA and Vershynin, R. (2007). One sketch for all: fast algorithms for compressed sensing. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. (p. 237–246). ACM.
  10. Gilbert, A. and Strauss, M. and Tropp, J. and Vershynin, R. (2007, Jun.). One sketch for all: Fast algorithms for compressed sensing. In Proc. ACM Symp. Theory of Comput. San Diego, CA
  11. Jafarpour, S. and Xu, W. and Hassibi, B. and Calderbank, R. (2009, Sep.). Efficient and robust compressed sensing using optimized expander graphs. IEEE Trans. Inform. Theory, 55, 4299–4308.
  12. Kainkaryam, R. and Breux, A. and Gilbert, A. and Woolf, P. and Schiefelbein, J. (2010). poolMC: Smart pooling of mRNA samples in microarray experiments. BMC Bioinformatics, 11(1), 299.
  13. Muthukrishnan, S. (2005). Found. Trends in Theoretical Comput. Science: Vol. 1. Data Streams: Algorithms and Applications. (). Boston, MA: Now Publishers.
  14. Shental, N. and Amir, A. and Zuk, O. (2009). Identification of rare alleles and their carriers using compressed se(que)nsing. Nucleic Acids Research, 38(19), e179.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks