An Exact Algorithm for Maximum Entropy Sampling

We study the computational complexity of finding extremal principal minors of a positive definite matrix. In particular, we focus on the NP-hard problem of maximizing the determinant over the set of principal submatrices of a given order. This problem arises in the area of statistical design, where one wishes to select a subset of some correlated Gaussian random variables having maximum entropy. In this case, the input matrix is the covariance matrix of the random variables and the entropy is the logarithm of the determinant. \Ale establish an upper bound for the entropy, based on the eigenvalue interlacing property, and we incorporate this bound in a branch-and-bound algorithm for the exact solution for the problem. We present computational results for estimated covariance matrices corresponding to sets of environmental monitoring stations in the United States.