One-Bit Compressed Sensing by Linear Programming
Skip to main content
eScholarship
Open Access Publications from the University of California

One-Bit Compressed Sensing by Linear Programming

  • Author(s): Plan, Yaniv
  • Vershynin, Roman
  • et al.

Published Web Location

https://doi.org/10.1002/cpa.21442Creative Commons 'BY' version 4.0 license
Abstract

We give the first computationally tractable and almost optimal solution to the problem of one-bit compressed sensing, showing how to accurately recover an s-sparse vector x in R^n from the signs of O(s log^2(n/s)) random linear measurements of x. The recovery is achieved by a simple linear program. This result extends to approximately sparse vectors x. Our result is universal in the sense that with high probability, one measurement scheme will successfully recover all sparse vectors simultaneously. The argument is based on solving an equivalent geometric problem on random hyperplane tessellations.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View