Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach

Details Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach

2012-02-06

arxiv.org/abs/1202.1212v1

Computer Science

Information Theory

20 pages, 1 figure, minor changes in terminology

Scientific paper

This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We show that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We demonstrate that an s-sparse signal in R^n can be accurately estimated from m = O(slog(n/s)) single-bit measurements using a simple convex program. This remains true even if almost half of the measurements are randomly flipped. 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(slog(n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in R^n which is approximately s-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 K 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.

Affiliated with

Also associated with

No associations

Rating

Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-119873