Compressible Distributions for High-dimensional Statistics

Abstract

We develop a principled way of identifying probability distributions whose independent and identically distributed (iid) realizations are compressible, i.e., can be well-approximated as sparse. We focus on Gaussian random underdetermined linear regression (GULR) problems, 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. A highlight is the Laplace distribution and ${\ell }^1$ regularized estimators such as the Lasso and Basis Pursuit denoising. To establish this result, we identify non-trivial undersampling regions in GULR where the simple least squares solution almost surely outperforms an oracle sparse solution, when the data is generated from the Laplace distribution. We provide simple rules of thumb to characterize classes of compressible (respectively incompressible) distributions based on their second and fourth moments. Generalized Gaussians and generalized Pareto distributions serve as running examples for concreteness.

Was previously entitled "Compressible priors for high-dimensional statistics"; IEEE Transactions on Information Theory (2012)

Cited by in corpus (9)

• Review: Deep Learning in Electron Microscopy
• Near optimal compressed sensing without priors: Parametric SURE Approximate Message Passing
• Cramer Rao-Type Bounds for Sparse Bayesian Learning
• Maximum-A-Posteriori Estimates in Linear Inverse Problems with Log-concave Priors are Proper Bayes Estimators
• Bayesian Estimation for Continuous-Time Sparse Stochastic Processes
• Learning Convex Regularizers for Optimal Bayesian Denoising
• The Stochastic Properties of ${\ell }^1$-Regularized Spherical Gaussian Fields
• Entropic Compressibility of Lévy Processes
• Implicit Compressibility of Overparametrized Neural Networks Trained with Heavy-Tailed SGD