Covariance Estimation for High Dimensional Data Vectors Using the Sparse Matrix Transform

Many problems in statistical pattern recognition and analysis require the classifcation and analysis of high dimensional data vectors. However, covariance estimation for high dimensional vectors is a classically difficult problem because the number of coefficients in the covariance grows as the dimension squared [1, 2, 3]. This problem, sometimes referred to as the curse of dimensionality [4], presents a classic dilemma in statistical pattern analysis and machine learning. In a typical application, one measures M versions of an N dimensional vector. If M \u3c N, then the sample covariance matrix will be singular with N - M eigenvalues equal to zero. Over the years, a variety of techniques have been proposed for computing a nonsingular estimate of the covariance. For example, regularized and shrinkage covariance estimators [5, 6, 7, 8, 9, 10] are examples of such techniques. In this paper, we propose a new approach to covariance estimation, which is based on constrained maximum likelihood (ML) estimation of the covariance. In particular, the covariance is constrained to have an eigen decomposition which can be represented as a sparse matrix transform (SMT) [11]. The SMT is formed by a product of pairwise coordinate rotations known as Givens rotations [12]. Using this framework, the covariance can be efficiently estimated using greedy minimization of the log likelihood function, and the number of Givens rotations can be efficiently computed using a cross-validation procedure. The estimator obtained using this method is always positive definite and well-conditioned even with limited sample size. In order to validate our model, we perform experiments using a standard set of hyperspectral data [13]. Our experiments show that SMT covariance estimation results in consistently better estimates of the covariance for a variety of different classes and sample sizes. Also, we show that the SMT method has a particular advantage over traditional methods when estimating small eigenvalues and their associated eigenvectors