An Exact Algorithm For Maximum Entropy Sampling

An Exact Algorithm for Maximum Entropy Sampling

Maximum-Entropy Sampling

This monograph presents a comprehensive treatment of the maximum-entropy sampling problem (MESP), which is a fascinating topic at the intersection of mathematical optimization and data science. The text situates MESP in information theory, as the algorithmic problem of calculating a sub-vector of pre-specificed size from a multivariate Gaussian random vector, so as to maximize Shannon's differential entropy. The text collects and expands on state-of-the-art algorithms for MESP, and addresses its application in the field of environmental monitoring. While MESP is a central optimization problem in the theory of statistical designs (particularly in the area of spatial monitoring), this book largely focuses on the unique challenges of its algorithmic side. From the perspective of mathematical-optimization methodology, MESP is rather unique (a 0/1 nonlinear program having a nonseparable objective function), and the algorithmic techniques employed are highly non-standard. In particular, successful techniques come from several disparate areas within the field of mathematical optimization; for example: convex optimization and duality, semidefinite programming, Lagrangian relaxation, dynamic programming, approximation algorithms, 0/1 optimization (e.g., branch-and-bound), extended formulation, and many aspects of matrix theory. The book is mainly aimed at graduate students and researchers in mathematical optimization and data analytics.

Entropy Measures for Environmental Data

This book shows how to successfully adapt entropy measures to the complexity of environmental data. It also provides a unified framework that covers all main entropy and spatial entropy measures in the literature, with suggestions for their potential use in the analysis of environmental data such as biodiversity, land use and other phenomena occurring over space or time, or both. First, recent literature reviews about including spatial information in traditional entropy measures are presented, highlighting the advantages and disadvantages of past approaches and the difference in interpretation of their proposals. A consistent notation applicable to all approaches is introduced, and the authors’ own proposal is presented. Second, the use of entropy in spatial sampling is focused on, and a method with an outstanding performance when data show a negative or complex spatial correlation is proposed. The last part of the book covers estimating entropy and proposes a model-based approach that differs from all existing estimators, working with data presenting any departure from independence: presence of covariates, temporal or spatial correlation, or both. The theoretical parts are supported by environmental examples covering point data about biodiversity and lattice data about land use. Moreover, a practical section is provided for all parts of the book; in particular, the R package SpatEntropy covers not only the authors’ novel proposals, but also all the main entropy and spatial entropy indices available in the literature. R codes are supplemented to reproduce all the examples. This book is a valuable resource for students and researchers in applied sciences where the use of entropy measures is of interest and where data present dependence on space, time or covariates, such as geography, ecology, biology and landscape analysis.