2012/02/06 by Yaniv Plan, Plan, Yaniv, Roman Vershynin +1 · 5 citations
Engineering · Computer Science · #Sparse and Compressive Sensing Techniques #Machine Learning and Algorithms #Distributed Sensor Networks and Detection Algorithms
paper · pdf · doi:10.48550/arxiv.1202.1212
This paper develops theoretical results regarding noisy 1-bit compressed\nsensing and sparse binomial regression. We show that a single convex program\ngives an accurate estimate of the signal, or coefficient vector, for both of\nthese models. We demonstrate that an s-sparse signal in Rn can be accurately\nestimated from m = O(slog(n/s)) single-bit measurements using a simple convex\nprogram. This remains true even if each measurement bit is flipped with\nprobability nearly 1/2. Worst-case (adversarial) noise can also be accounted\nfor, and uniform results that hold for all sparse inputs are derived as well.\nIn the terminology of sparse logistic regression, we show that O(slog(n/s))\nBernoulli trials are sufficient to estimate a coefficient vector in Rn which\nis approximately s-sparse. Moreover, the same convex program works for\nvirtually all generalized linear models, in which the link function may be\nunknown. To our knowledge, these are the first results that tie together the\ntheory of sparse logistic regression to 1-bit compressed sensing. Our results\napply to general signal structures aside from sparsity; one only needs to know\nthe size of the set K where signals reside. The size is given by the mean width\nof K, a computable quantity whose square serves as a robust extension of the\ndimension.\n