Technical Note—Masking Anstreicher’s linx Bound for Improved Entropy Bounds

The maximum-entropy sampling problem is the NP-hard problem of maximizing the (log) determinant of an order-s principal submatrix of a given order n covariance matrix C. Exact algorithms are based on a branch-and-bound framework. The problem has wide applicability in spatial statistics and in particular in environmental monitoring. Probably the best upper bound for the maximum empirically is Anstreicher’s scaled “linx” bound. An earlier methodology for potentially improving any upper-bounding method is by masking, that is, applying the bounding method to $C\circ M$, where M is any correlation matrix. We establish that the linx bound can be improved via masking by an amount that is at least linear in n, even when optimal scaling parameters are used. We also extend an earlier result that the linx bound is convex in the logarithm of a scaling parameter, making a full characterization of its behavior and providing an efficient means of calculating its limiting behavior in all cases.

Funding: J. Lee was supported by the Air Force Office of Scientific Research [Grant FA9550-19-1-0175]. M. Fampa was supported by the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grants 303898/2016-0 and 434683/2018-3].