file.pdf (146.6 kB)
Compressed Regression
journal contribution
posted on 1998-01-01, 00:00 authored by Shuheng Zhou, John Lafferty, Larry WassermanRecent research has studied the role of sparsity in high dimensional regression and
signal reconstruction, establishing theoretical limits for recovering sparse models
from sparse data. In this paper we study a variant of this problem where the
original n input variables are compressed by a random linear transformation to
m<1-regularized compressed
regression to identify the nonzero coefficients in the true model with probability
approaching one, a property called “sparsistence.” In addition, we show that
ℓ1-regularized compressed regression asymptotically predicts as well as an oracle
linear model, a property called “persistence.” Finally, we characterize the
privacy properties of the compression procedure in information-theoretic terms,
establishing upper bounds on the rate of information communicated between the
compressed and uncompressed data that decay to zero.