期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 59, 期 1, 页码 482-494出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2012.2207945
关键词
Compressed sensing; data compression; parameter estimation; quantization; regression analysis; signal reconstruction
资金
- National Science Foundation (NSF) [1103909, DMS 0918623, 1001829]
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 s-sparse signal in R-n 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 (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 where signals reside. The size is given by the mean width of, a computable quantity whose square serves as a robust extension of the dimension.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据