AN EXACT ALGORITHM FOR MAXIMUM-ENTROPY SAMPLING
成果类型：
Article
署名作者：
KO, CW; LEE, J; QUEYRANNE, M
署名单位：
Rutgers University System; Rutgers University New Brunswick; University of British Columbia
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.4.684
发表日期：
1995
页码：
684-691
关键词：
摘要：
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.