Exponential Decay of Reconstruction Error From Binary Measurements of Sparse Signals
Academic Article

 Overview

 Research

 Identity

 Additional Document Info

 View All

Overview
abstract

© 2017 IEEE. Binary measurements arise naturally in a variety of statistics and engineering applications. They may be inherent to the problem  for example, 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 onebit 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 onebit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, ssparse signals in Rn can be estimated (up to normalization) from Ω (s log (n/s)) onebit 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 λ := m/(s log (n/s)), where m is the number of measurements. It is known that the error in reconstructing sparse signals from standard onebit measurements is bounded below by Ω (λ1). Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible. However, we show that an adaptive choice of the thresholds used for quantization can lower the error rate to eΩ(λ). This improves upon guarantees for other methods of adaptive thresholding, such as sigmadelta quantization. We develop a general recursive strategy to achieve this exponential decay and two specific polynomialtime algorithms, which fall into this framework, one based on convex programming and one on hard thresholding. Our work bridges the onebit compressed sensing model, in which the engineer controls the measurement procedure, to sigmadelta and successive approximation quantization. Moreover, the principle is extendable to signal reconstruction problems in a variety of binary statistical models as well as statistical estimation problems like logistic regression.
author list (cited authors)

Baraniuk, R. G., Foucart, S., Needell, D., Plan, Y., & Wootters, M.
citation count
publication date
publisher
published in
Research
keywords

Binary Regression

Compressed Sensing

Convex Optimization

Iterative Thresholding

Onebit Compressed Sensing

Quantization
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue