Compressible distributions for high-dimensional statistics
We develop a principled way of identifying probability distributions whose independent and identically distributed realizations are compressible, i.e., can be well approximated as sparse. We focus on Gaussian compressed sensing, an example of underdetermined linear regression, where compressibility is known to ensure the success of estimators exploiting sparse regularization. We prove that many distributions revolving around maximum a posteriori (MAP) interpretation of sparse regularized estimators are in fact incompressible, in the limit of large problem sizes. We especially highlight the Laplace distribution and \ell 1 regularized estimators such as the Lasso and basis pursuit denoising. We rigorously disprove the myth that the success of \ell 1 minimization for compressed sensing image reconstruction is a simple corollary of a Laplace model of images combined with Bayesian MAP estimation, and show that in fact quite the reverse is true. To establish this result, we identify nontrivial undersampling regions where the simple least-squares solution almost surely outperforms an oracle sparse solution, when the data are generated from the Laplace distribution. We also provide simple rules of thumb to characterize classes of compressible and incompressible distributions based on their second and fourth moments. Generalized Gaussian and generalized Pareto distributions serve as running examples. © 1963-2012 IEEE.
CP_main.pdf
openaccess
645.39 KB
Adobe PDF
038b7ab09f3fd230c1d22ad0c41a5af8