Elementary Estimators for Sparse Covariance Matrices and other Structured Moments

We consider the problem of estimating expecta-tions of vector-valued feature functions; a spe-cial case of which includes estimating the co-variance matrix of a random vector. We are in-terested in recovery under high-dimensional set-tings, where the number of features p is poten-tially larger than the number of samples n, and where we need to impose structural constraints. In a natural distributional setting for this prob-lem, the feature functions comprise the sufficient statistics of an exponential family, so that the problem would entail estimating structured mo-ments of exponential family distributions. For instance, in the special case of covariance esti-mation, the natural distributional setting would correspond to the multivariate Gaussian distribu-tion. Unlike the inverse covariance estimation case, we show that the regularized MLEs for co-variance estimation, as well as natural Dantzig variants, are non-convex, even when the regular-ization functions themselves are convex; with the same holding for the general structured moment case. We propose a class of elementary con-vex estimators, that in many cases are available in closed-form, for estimating general structured moments. We then provide a unified statistical analysis of our class of estimators. Finally, we demonstrate the applicability of our class of es-timators via simulation and on real-world clima-tology and biology datasets