Convex relaxation for the generalized maximum-entropy sampling problem

Abstract The generalized maximum-entropy sampling problem (GMESP) is to select an order- s principal submatrix from an order- n covariance matrix, to maximize the product of its t greatest eigenvalues, $$0&lt;t\le s &lt;n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>0</mml:mn> <mml:mo>&lt;</mml:mo> <mml:mi>t</mml:mi> <mml:mo>≤</mml:mo> <mml:mi>s</mml:mi> <mml:mo>&lt;</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> . Introduced more than 25 years ago, GMESP is a natural generalization of two fundamental problems in statistical design theory: (i) maximum-entropy sampling problem (MESP); (ii) binary D-optimality (D-Opt). In the general case, it can be motivated by a selection problem in the context of principal component analysis (PCA). We introduce the first convex-optimization based relaxation for GMESP, study its behavior, compare it to an earlier spectral bound, and demonstrate its use in a branch-and-bound scheme. We find that such an approach is practical when $$s-t$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>s</mml:mi> <mml:mo>-</mml:mo> <mml:mi>t</mml:mi> </mml:mrow> </mml:math> is very small.