License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.61
URN: urn:nbn:de:0030-drops-74887
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7488/
Go to the corresponding LIPIcs Volume Portal

Nakos, Vasileios

On Fast Decoding of High-Dimensional Signals from One-Bit Measurements

pdf-format:
LIPIcs-ICALP-2017-61.pdf (0.5 MB)

Abstract

In the problem of one-bit compressed sensing, the goal is to find a delta-close estimation of a k-sparse vector x in R^n given the signs of the entries of y = Phi x, where Phi is called the measurement matrix. For the one-bit compressed sensing problem, previous work [Plan, 2013][Gopi, 2013] achieved Theta (delta^{-2} k log(n/k)) and O~( 1/delta k log (n/k)) measurements, respectively, but the decoding time was Omega ( n k log (n/k)). In this paper, using tools and techniques developed in the context of two-stage group testing and streaming algorithms, we contribute towards the direction of sub-linear decoding time. We give a variety of schemes for the different versions of one-bit compressed sensing, such as the for-each and for-all versions, and for support recovery; all these have at most a log k overhead in the number of measurements and poly(k, log n) decoding time, which is an exponential improvement over previous work, in terms of the dependence on n.

BibTeX - Entry

@InProceedings{nakos:LIPIcs:2017:7488,
  author =	{Vasileios Nakos},
  title =	{{On Fast Decoding of High-Dimensional Signals from One-Bit Measurements}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7488},
  URN =		{urn:nbn:de:0030-drops-74887},
  doi =		{10.4230/LIPIcs.ICALP.2017.61},
  annote =	{Keywords: one-bit compressed sensing, sparse recovery, heavy hitters, dyadic trick, combinatorial group testing}
}

Keywords: one-bit compressed sensing, sparse recovery, heavy hitters, dyadic trick, combinatorial group testing
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI