Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach

By Yaniv Plan, Roman Vershynin. IEEE Transactions on Information Theory, 2012

478 citations recorded by the source corpus.

This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We demonstrate that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We show that an -sparse signal in can be accurately estimated from m = O(s log(n/s)) single-bit measurements using a simple convex program. This remains true even if each measurement bit is flipped with probability nearly 1/2. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O (s log (2n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in which is approximately -sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/1a8e11d93160148031b9aad6306ca9fbd4c66fec

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

1-Bit Matrix Completion (2012, background): “A similar theory is available for the closely related problem of sparse binomial regression, which considers more classical statistical models [2, 11, 34, 46, 48, 52, 54, 65] and allows non-Gaussian measurements.”
Deep Neural Networks with Random Gaussian Weights: A Universal Classification Strategy? (2015, background): “As random projection is a universal sampling strategy for any low dimensional data [7], [25], [26], deep networks with random weights are a universal system that separates any data (belonging to a low dimensional model) according to the angles between its points, where the general assumption is that”
Distributionally Robust Logistic Regression (2015, background): “Indeed, it is well documented that minimizing the average logloss function leads to overfitting and weak class ification performance [2, 3].”
Learning Two Layer Rectified Neural Networks in Polynomial Time (2018, methodology): “The following follows immediately from Plan and Vershynin (2013).”
Least squares estimation in the monotone single index model (2016, methodology): “Other estimation methods can be found in the compressed sensing literature (some of them are designed for the case of binary response variables), see e.g. Plan and Vershynin (2013); Plan et al. (2016).”
Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, unknown): “If we ignore the structure in x and choose f as the 0 or 1 norms, then the mean widths are ωK = O(k log(d/k)) [56] and ωC 2(k log(d/k)) [54] respectively.”
Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors (2011, unknown): “Furthermore, the results of [32] and [33]”
Post-Selection Inference for Generalized Linear Models With Many Controls (2013, methodology): “considered in [27] and connections with robust 1-bit recovery were derived in [24].”