Robust Estimation of Covariance Matrices: Adversarial Contamination and Beyond

Abstract

We consider the problem of estimating the covariance structure of a random vector $Y\in {\mathbb{R}}^d$ from a sample $Y_1,\dots ,Y_n$. We are interested in the situation when $d$ is large compared to $n$ but the covariance matrix $\Sigma$ of interest has (exactly or approximately) low rank. We assume that the given sample is (a) $\epsilon$-adversarially corrupted, meaning that $\epsilon$ fraction of the observations could have been replaced by arbitrary vectors, or that (b) the sample is i.i.d. but the underlying distribution is heavy-tailed, meaning that the norm of $Y$ possesses only finite fourth moments. We propose an estimator that is adaptive to the potential low-rank structure of the covariance matrix as well as to the proportion of contaminated data, and admits tight deviation guarantees despite rather weak assumptions on the underlying distribution. Finally, we discuss the algorithms that allow to approximate the proposed estimator in a numerically efficient way.

References in corpus (13)

• Optimal Distributed Online Prediction using Mini-Batches
• Recent Advances in Algorithmic High-Dimensional Robust Statistics
• Being Robust (in High Dimensions) Can Be Practical
• Operator Lipschitz Functions
• An ${\ell }_{\infty }$ Eigenvector Perturbation Bound and Its Application to Robust Covariance Estimation
• A Unified Approach to Robust Mean Estimation
• Robust Covariance and Scatter Matrix Estimation under Huber's Contamination Model
• Faster Algorithms for High-Dimensional Robust Covariance Estimation
• Robust Modifications of U-statistics and Applications to Covariance Estimation Problems
• User-Friendly Covariance Estimation for Heavy-Tailed Distributions
• Updating Singular Value Decomposition for Rank One Matrix Perturbation
• Covariance Estimation: Optimal Dimension-free Guarantees for Adversarial Corruption and Heavy Tails
• Improved covariance estimation: optimal robustness and sub-Gaussian guarantees under heavy tails

Cited by in corpus (1)

• Tyler's and Maronna's M-estimators: Non-Asymptotic Concentration Results