AN EXACT ALGORITHM FOR MAXIMUM-ENTROPY SAMPLING

We study the experimental design problem of selecting a most informati ve subset, having prespecified size, from a set of correlated random v ariables. The problem arises in many applied domains, such as meteorol ogy, environmental statistics, and statistical geology. In these appli cations, observations can be collected at different locations, and pos sibly, at different times. Information is measured by ''entropy.'' In the Gaussian case, the problem is recast as that of maximizing the det erminant of the covariance matrix of the chosen subset. We demonstrate that this problem is NP-hard. We establish an upper bound for the ent ropy, based on the eigenvalue interlacing property, and we incorporate this bound in a branch-and-bound algorithm for the exact solution of the problem. We present computational results for estimated covariance matrices that correspond to sets of environmental monitoring stations in the United States.