1-bit Compressive Sensing

1-bit Compressive Sensing studies how Compressive Sensing interacts with a particularly interesting quantizer. Specifically, it examines the most severe form of scalar quantization, which preserves only the sign of each measurement as one bit of information. I first introduced this line of work in [1] and followed up in [2, 3].

There are several reasons to study the performance of such a system, some of which theoretical, some very practical:

  • The analysis shifts the focus to bits instead of measurements; we discuss rate-distortion properties of CS systems.
  • A 1-bit quantizer is an extremely simple device—just a comparator to zero—that is very cheap and can operate extremely fast.
  • A fast quantizer allows the compressive acquisition system to take many more measurements, providing robustness to measurement noise, while still achieving compressive acquisition.
  • The reconstruction algorithms and the theory are very useful in recovering signals from non-linearly distorted measurements even if the non-linear distortion is not known, as long as the distortion is monotonic (see [4] for details).
  • The theoretical properties of such acquisition have very interesting connections with Johnson-Lindenstrauss embeddings,  locality sensitive hashing (LSH), and the (sparse) logistic regression.

In few words, 1-bit CS acquires a sparse signal x using

y=\mbox{sign}(Ax)

i.e., measures the signals and only preserves the sign of the measurements. It should be clear that from such measurements the signal can only be reconstructed within a scaling factor c>0. All signal scalings produce the same sign pattern since  y=\mbox{sign}(Ax)=\mbox{sign}(Acx).

Geometrically, each measurement vector defines a hyperplane through the origin in the signal space, as shown in the figure on the right. The sign of the measurements determines which sign of the hyperplane the signal lies in.

The goal is to obtain a sufficient number of measurements to accurately reconstruct the signal, using the knowledge that the signal is sparse in some basis. Since we cannot recover the scaling factor c, it suffices to reconstruct any signal in the same direction as the original signal, such as a signal on the unit sphere.

The red area in the figure shows all the signals that could produce the same measurement pattern. The sparsest signal in that area would lie along the seam of the sphere—colored magenta—i.e., would be 2-sparse. The ambiguity is significantly reduced thanks to our sparse signal model.

Since the introduction of this topic, a number of methods, algorithms and theoretical results have appeared. The 1-bit CS page is a very good resource on the progress in this area and includes related papers, code and presentations from a variety of groups.


[1]

P. T. Boufounos and R. G. Baraniuk, “1-Bit Compressive Sensing,” Proc. Conf. Inform. Science and Systems (CISS), Princeton, NJ, March 19-21, 2008.

[preprint] [Bibtex]

@inproceedings{BB_CISS08,
  Address =   {Princeton, NJ},
  Author =   {Boufounos, P. T. and Baraniuk, R. G.},
  Booktitle =   {Proc. Conf. Inform. Science and Systems (CISS)},
  Doi =     {10.1109/CISS.2008.4558487},
  Month =   {March 19-21},
  Pdf =     {http://boufounos.com/Publications/Boufounos_Baraniuk_CISS08.pdf},
  Title =   {1-Bit Compressive Sensing},
  Url =     {http://dx.doi.org/10.1109/CISS.2008.4558487},
  Year =   {2008}
}

[2]

P. T. Boufounos, “Greedy sparse signal reconstruction from sign measurements,” Proc. Asilomar Conf. on Signals Systems and Comput., pp. 1305-1309, Pacific Grove, CA, November 1-4, 2009.

[preprint] [Bibtex]

@inproceedings{B_Asilomar09,
  Address =   {Pacific Grove, CA},
  Author =   {Boufounos, P. T.},
  Booktitle =   {Proc. Asilomar Conf. on Signals Systems and Comput.},
  Doi =     {10.1109/ACSSC.2009.5469926},
  Month =   {November 1-4},
  Organization = {IEEE},
  Pages =   {1305--1309},
  Pdf =     {http://boufounos.com/Publications/Boufounos_Asilomar09.pdf},
  Title =   {Greedy sparse signal reconstruction from sign measurements},
  Url =     {http://dx.doi.org/10.1109/ACSSC.2009.5469926},
  Year =   {2009}
}

[3]

L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk, “Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors,” IEEE Trans. Info. Theory, v. 59, no. 4, April, 2013.

[preprint] [arXiv] [Bibtex]

@article{JLBB_TIT13,
  Arxivurl =   {http://arxiv.org/abs/1104.3160},
  Author =   {Jacques, L. and Laska, J. N. and Boufounos, P. T. and Baraniuk, R. G.},
  Journal =   {IEEE Trans. Info. Theory},
  Pdf =     {http://boufounos.com/Publications/JLBB_BSE.pdf},
  Title =   {Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors},
  Url =     {http://dx.doi.org/10.1109/TIT.2012.2234823},
  Doi =     {10.1109/TIT.2012.2234823},
  volume =   {59},
  number =   {4},
  Month =   {April},
  Year =   {2013}
}

[4]

P. T. Boufounos, “Reconstruction of sparse signals from distorted randomized measurements,” Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Dallas, TX, March 14-19, 2010.

[preprint] [Bibtex]

@inproceedings{B_ICASSP10,
  Address =   {Dallas, TX},
  Author =   {Boufounos, P. T.},
  Booktitle =   {Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP)},
  Doi =     {10.1109/ICASSP.2010.5495766},
  Month =   {March 14-19},
  Organization = {IEEE},
  Pdf =     {http://boufounos.com/Publications/Boufounos_ICASSP2010.pdf},
  Title =   {Reconstruction of sparse signals from distorted randomized measurements},
  Url =     {http://dx.doi.org/10.1109/ICASSP.2010.5495766},
  Year =   {2010}
}