Optimal rates of convergence for sparse covariance matrix estimation

Abstract

This paper considers estimation of sparse covariance matrices and establishes the optimal rate of convergence under a range of matrix operator norm and Bregman divergence losses. A major focus is on the derivation of a rate sharp minimax lower bound. The problem exhibits new features that are significantly different from those that occur in the conventional nonparametric function estimation problems. Standard techniques fail to yield good results, and new tools are thus needed. We first develop a lower bound technique that is particularly well suited for treating "two-directional" problems such as estimating sparse covariance matrices. The result can be viewed as a generalization of Le Cam's method in one direction and Assouad's Lemma in another. This lower bound technique is of independent interest and can be used for other matrix estimation problems. We then establish a rate sharp minimax lower bound for estimating sparse covariance matrices under the spectral norm by applying the general lower bound technique. A thresholding estimator is shown to attain the optimal rate of convergence under the spectral norm. The results are then extended to the general matrix ${\ell }_w$ operator norms for $1\le w\le \infty$. In addition, we give a unified result on the minimax rate of convergence for sparse covariance matrix estimation under a class of Bregman divergence losses.

Published in at http://dx.doi.org/10.1214/12-AOS998 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (5)

• Regularized estimation of large covariance matrices
• Covariance regularization by thresholding
• Sparsistency and rates of convergence in large covariance matrix estimation
• Optimal rates of convergence for covariance matrix estimation
• Operator norm consistent estimation of large-dimensional sparse covariance matrices

Cited by in corpus (23)

• Sparse PCA: Optimal rates and adaptive estimation
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Asymptotic normality and optimalities in estimation of large Gaussian graphical models
• Covariance and precision matrix estimation for high-dimensional time series
• Law of Log Determinant of Sample Covariance Matrix and Optimal Estimation of Differential Entropy for High-Dimensional Gaussian Distributions
• Gaussian and bootstrap approximations for high-dimensional U-statistics and their applications
• Optimal sparse volatility matrix estimation for high-dimensional Itô processes with measurement errors
• Posterior contraction in sparse Bayesian factor models for massive covariance matrices
• Asymptotically minimax empirical Bayes estimation of a sparse normal mean vector
• Finite sample change point inference and identification for high-dimensional mean vectors
• Inference for High-dimensional Differential Correlation Matrices
• Adaptive estimation of the copula correlation matrix for semiparametric elliptical copulas
• Optimal large-scale quantum state tomography with Pauli measurements
• Robust Sparse Covariance Estimation by Thresholding Tyler's M-Estimator
• Estimation of Large Covariance and Precision Matrices from Temporally Dependent Observations
• Fixed support positive-definite modification of covariance matrix estimators via linear shrinkage
• Optimal covariance matrix estimation for high-dimensional noise in high-frequency data
• Non-Asymptotic Analysis of Ensemble Kalman Updates: Effective Dimension and Localization
• Central limit theorems for functionals of large sample covariance matrix and mean vector in matrix-variate location mixture of normal distributions
• Tyler's and Maronna's M-estimators: Non-Asymptotic Concentration Results
• Covariance Operator Estimation via Adaptive Thresholding
• Nonparametric Estimation of Large Spot Volatility Matrices for High-Frequency Financial Data
• The Generalized Elastic Net for least squares regression with network-aligned signal and correlated design