One-bit compressed sensing by linear programming

Details One-bit compressed sensing by linear programming One-bit compressed sensing by linear programming

2011-09-20

arxiv.org/abs/1109.4299v5

Computer Science

Information Theory

15 pages, 1 figure, to appear in CPAM. Small changes based on referee comments

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

One-bit compressed sensing by linear programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with One-bit compressed sensing by linear programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and One-bit compressed sensing by linear programming will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-147230