Approximate Leave-One-Out Cross Validation for Robust Scatter Matrix Estimation

Tyler's $M$-estimator (TME) is an accurate and efficient robust estimator for the scatter matrix when the data are samples from an *elliptical distribution* with heavy-tails and the number of samples $n$ is larger than the number of variables $p$. Unfortunately, when $p > n$, TME is not defined, and various research works have proposed regularized versions of TME using the spirit of Ledoit & Wolf estimator whose performance depends on a carefully chosen *shrinkage coefficient* parameter $\alpha \in (0,1)$. In this paper, we consider the problem of estimating an optimal shrinkage coefficient $\alpha \in (0,1)$ for Regularized TME (RTME). In particular, we propose to estimate an optimal shrinkage coefficient by setting $\alpha$ as the solution to a suitably chosen objective function; namely the leave-one-out cross-validated (LOOCV) log-likelihood loss. Since LOOCV is computationally prohibitive even for moderate values of $n$, we propose a computationally efficient approximation for the LOOCV log-likelihood loss that eliminates the need for invoking the RTME procedure $n$ times for each sample left out during the LOOCV procedure. This approximation yields an $O(n)$ reduction in the running time complexity for the LOOCV procedure, which results in a significant speedup for computing the LOOCV estimate. We demonstrate the efficacy of the proposed approach on synthetic high-dimensional data sampled from heavy-tailed elliptical distributions, as well as on real high-dimensional datasets for object and face recognition. Our experiments show that the proposed method is efficient and consistently more accurate than other methods in the literature for shrinkage coefficient estimation.