# Compressible Distributions for High-dimensional Statistics

1 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
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.
Keywords :
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2012, 58 (8), 〈10.1109/TIT.2012.2197174〉
Domaine :
Liste complète des métadonnées

https://hal.inria.fr/inria-00563207
Contributeur : Rémi Gribonval <>
Soumis le : mercredi 25 avril 2012 - 11:52:16
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : jeudi 26 juillet 2012 - 02:27:58

### Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Rémi Gribonval, Volkan Cevher, Mike Davies. Compressible Distributions for High-dimensional Statistics. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2012, 58 (8), 〈10.1109/TIT.2012.2197174〉. 〈inria-00563207v3〉

### Métriques

Consultations de la notice

## 1353

Téléchargements de fichiers