최대 엔트로피 샘플링을 위한 정확한 알고리즘

우리는 상관관계가 있는 랜덤 변수 집합에서 미리 지정된 크기를 가진 가장 정보가 풍부한 부분집합을 선택하는 실험 설계 문제를 연구한다. 이 문제는 기상학, 환경 통계학 및 통계 지질학과 같은 여러 응용 분야에서 발생한다. 이러한 응용에서 관측치는 서로 다른 위치와 가능하면 서로 다른 시간에 수집될 수 있다. 정보는 '엔트로피'로 측정된다. 가우시안 경우에서 이 문제는 선택된 부분집합의 공분산 행렬의 결정식을 최대화하는 문제로 재정의된다. 우리는 이 문제가 NP-hard하다는 것을 입증한다. 우리는 고유값의 교차 성질을 기반으로 엔트로피에 대한 상한을 설정하고, 이 상한을 문제의 정확한 해결을 위한 분기 한정 알고리즘에 통합한다. 우리는 미국의 환경 모니터링 스테이션 집합에 해당하는 추정된 공분산 행렬에 대한 계산 결과를 제시한다.