Optimization Online


Best Principal Submatrix Selection for the Maximum Entropy Sampling Problem: Scalable Algorithms and Performance Guarantees

Yongchun Li (liyc***at***vt.edu)
Weijun Xie (wxie***at***vt.edu)

Abstract: This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix with a given size out of a covariance matrix from a system. MESP has been widely applied to many areas, including healthcare, power system, manufacturing, data science, etc. Investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation is close to optimality. The results motivate us to propose an efficient sampling algorithm and develop its approximation bound for MESP, which improves the best-known bound in the literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. By developing new mathematical tools for the singular matrices and analyzing the Lagrangian dual of the proposed convex integer program, we investigate the widely-used local search algorithm and prove its first-known approximation bound for MESP. The proof techniques further inspire us to design an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-sized and large-scale instances to near-optimality. Our proposed algorithms are released as an open-source software available online. Finally, we extend the analyses to the A-Optimal MESP (A-MESP), where its objective is to find the smallest trace of the inverse of the selected principal submatrix.

Keywords: Maximum Entropy Sampling Problem; Local Search Algorithm; Sampling Algorithm; A-Optimality.

Category 1: Applications -- Science and Engineering (Data-Mining )

Citation: Submitted

Download: [PDF]

Entry Submitted: 01/23/2020
Entry Accepted: 01/23/2020
Entry Last Modified: 10/01/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society