English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper studies a classic maximum entropy sampling problem (MESP), whichaims to select the most informative principal submatrix of a prespecified sizefrom a covariance matrix. MESP has been widely applied to many areas, includinghealthcare, power system, manufacturing and data science. By investigating itsLagrangian dual and primal characterization, we derive a novel convex integerprogram for MESP and show that its continuous relaxation yields a near-optimalsolution. The results motivate us to study an efficient sampling algorithm anddevelop its approximation bound for MESP, which improves the best-known boundin literature. We then provide an efficient deterministic implementation of thesampling algorithm with the same approximation bound. By developing newmathematical tools for the singular matrices and analyzing the Lagrangian dualof the proposed convex integer program, we investigate the widely-used localsearch algorithm and prove its first-known approximation bound for MESP. Theproof techniques further inspire us with an efficient implementation of thelocal search algorithm. Our numerical experiments demonstrate that theseapproximation algorithms can efficiently solve medium-sized and large-scaleinstances to near-optimality. Our proposed algorithms are coded and released asopen-source software. Finally, we extend the analyses to the A-Optimal MESP(A-MESP), where the objective is to minimize the trace of the inverse of theselected principal submatrix.

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