Compressible Distributions for High-Dimensional Statistics

DOI10.1109/TIT.2012.2197174MaRDI QIDQ2989816zbMATH OpenOpenAlexFDO

Authors Volkan Cevher, Rémi Gribonval, M. E. Davies

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.1249

Mathematics Subject Classification ID

Linear regression; mixed models (62J05) Ridge regression; shrinkage estimators (Lasso) (62J07) Applications of mathematical programming (90C90) Sampling theory in information and communication theory (94A20)

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 $el{l}^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.

Cited in

(11)

• The BRS-inequality and its applications
• Sparse regression Chebyshev polynomial interval method for nonlinear dynamic systems under uncertainty
• The stochastic properties of \(\ell^1\)-regularized spherical Gaussian fields
• On Bayesian estimation and proximity operators
• Compressibility analysis of asymptotically mean stationary processes
• Wavelet statistics of sparse and self-similar images
• Wasserstein loss for image synthesis and restoration
• Compression of Multivariate Discrete Measures and Applications
• Average best \(m\)-term approximation
• Compressed and Quantized Correlation Estimators
• On the continuity of characteristic functionals and sparse stochastic modeling

This page was built for publication: Compressible Distributions for High-Dimensional Statistics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989816)