The estimation of a covariance matrix from an insufficient amount of data is one of the most common problems in fields as diverse as multivariate statistics, wireless communications, signal processing, biology, learning theory and finance. In , a new approach to handle rank deficient covariance matrices was suggested. The main idea was to use dimensionality reduction in conjunction with an average over the Stiefel manifold. In this paper we further continue in this direction and consider a few innovative methods that show considerable improvements with respect to more traditional ones such as diagonal loading. One of the methods is called the Ewens estimator and uses a randomization of the sample covariance matrix over all the permutation matrices with respect to the Ewens measure. The techniques used to attack this problem are broad and run from random matrix theory to combinatorics.