An Exact Algorithm for Maximum Entropy Sampling

Chun-Wa Ko, Jon Lee and Maurice Queyranne
Additional contact information
Chun-Wa Ko: DIMACS, Rutgers University, New Brunswick, New Jersey, USA
Jon Lee: Department of Operations Research, Yale University, New Haven, CT 06520 USA
Maurice Queyranne: Faculty of Commerce and Business Administration, The University of British Columbia, Vancouver, B.C. Canada V6T 1Z2

No 1993006, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: 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.

Date: 1993-02-01
References: Add references at CitEc
Citations:

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1993.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1993006

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().