Technical Program

Paper Detail

Paper Title One-Bit ExpanderSketch for One-Bit Compressed Sensing
Paper IdentifierFR3.R4.3
Authors Vasileios Nakos, Harvard University, United States
Session Compressed Sensing II
Location Odéon, Level 3
Session Time Friday, 12 July, 14:30 - 16:10
Presentation Time Friday, 12 July, 15:10 - 15:30
Manuscript  Click here to download the manuscript
Abstract Is it possible to obliviously construct a set of hyperplanes H, such that you can approximate a unit vector x in R^n when you are given the side on which the vector lies with respect to every h in H? In the sparse recovery literature, where x is approximately k-sparse, this problem is called one-bit compressed sensing and has received a fair amount of attention the last decade. In this paper we obtain the first scheme that achieves nearly optimal measurements and sublinear decoding time for one-bit compressed sensing in the non-uniform case. For a large range of parameters, we improve the state of the art in both the number of measurements and the decoding time.