An exact algorithm for maximum entropy sampling

An exact algorithm for maximum entropy sampling

0.00 Avg rating0 Votes
Article ID: iaor19982517
Country: United States
Volume: 43
Issue: 4
Start Page Number: 684
End Page Number: 691
Publication Date: Jul 1995
Journal: Operations Research
Authors: , ,
Keywords: programming: nonlinear, geography & environment, location
Abstract:

We study the experimental design problem of selecting a most informative subset, having prespecified size, from a set of correlated random variables. The problem arises in many applied domains, such as meteorology, environmental statistics, and statistical geology. In these applications, observations can be collected at different locations, and possibly, at different times. Information is measured by ‘entropy’. In the Gaussian case, the problem is recast as that of maximizing the determinant of the covariance matrix of the chosen subset. We demonstrate that this problem is NP-hard. We 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 of the problem. We present computational results for estimated covariance matrices that correspond to sets of environmental monitoring stations in the United States.

Reviews

Required fields are marked *. Your email address will not be published.