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, TME is not defined when p > n, 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 alpha \in (0,1).

In this paper, we consider the problem of estimating an optimal shrinkage coefficient alpha 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. LOOCV, however, is computationally prohibitive even for moderate values of n. To this end, 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 demonstrate that the proposed method is efficient and consistently more accurate than other methods in the literature for shrinkage coefficient estimation.