Sparsity and the truncated ℓ2-norm

Research output: Contribution to journalConference article

1 Scopus citations

Abstract

Sparsity is a fundamental topic in high-dimensional data analysis. Perhaps the most common measures of sparsity are the ℓp-norms, for 0 ≤ p < 2. In this paper, we study an alternative measure of sparsity the truncated ℓ2-norm, which is related to other ℓp-norms, but appears to have some unique and useful properties. Focusing on the n-dimensional Gaussian location model, we derive exact asymptotic minimax results for estimation over truncated ℓ2-balls, which complement existing results for ℓp-balls. We then propose simple new adaptive thresholding estimators that are inspired by the truncated ℓ2-norm and are adaptive asymptotic minimax over ℓp-balls (0 ≤ p < 2), as well as truncated ℓ2-balls. Finally, we derive lower bounds on the Bayes risk of an estimator, in terms of the parameter's truncated ℓ2-norm. These bounds provide necessary conditions for Bayes risk consistency in certain problems that are relevant for high-dimensional Bayesian modeling.

Original languageEnglish (US)
Pages (from-to)159-166
Number of pages8
JournalJournal of Machine Learning Research
Volume33
StatePublished - Jan 1 2014
Event17th International Conference on Artificial Intelligence and Statistics, AISTATS 2014 - Reykjavik, Iceland
Duration: Apr 22 2014Apr 25 2014

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Statistics and Probability
  • Artificial Intelligence

Cite this