Sparsity and the truncated l^2-norm


Lee Dicker ;
Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, PMLR 33:159-166, 2014.


Sparsity is a fundamental topic in high-dimensional data analysis. Perhaps the most common measures of sparsity are the l^p-norms, for p < 2. In this paper, we study an alternative measure of sparsity, the truncated l^2-norm, which is related to other l^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 l^2-balls, which complement existing results for l^p-balls. We then propose simple new adaptive thresholding estimators that are inspired by the truncated l^2-norm and are adaptive asymptotic minimax over l^p-balls (p < 2), as well as truncated l^2-balls. Finally, we derive lower bounds on the Bayes risk of an estimator, in terms of the parameter’s truncated l^2-norm. These bounds provide necessary conditions for Bayes risk consistency in certain problems that are relevant for high-dimensional Bayesian modeling.

Related Material