Exponential Decay of Reconstruction Error from Binary Measurements of Sparse Signals
Abstract
Binary measurements arise naturally in a variety of statistical and engineering applications. They may be inherent to the problem--e.g., in determining the relationship between genetics and the presence or absence of a disease--or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by one-bit compressed sensing, which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, s-sparse signals in Rn can be estimated (up to normalization) from (s log(n=s)) one-bit measurements. Nevertheless, controlling the precise accuracy of the error estimate remains an open challenge. In this paper, we focus on optimizing the decay of the error as a function of the oversampling factor lambda: = m=(s log(n=s)), where m is the number of measurements. It is known that the error in reconstructing sparse signals from standard one-bit measurements is bounded below by (1). Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 2014
- Accession Number
- AD1018381
Entities
People
- Deanna Needell
- Mary Wootters
- Richard G. Baraniuk
- Simon Foucart
- Yaniv Plan
Organizations
- Rice University