Maximal entropy in the moment body

A moment body is a linear projection of the spectraplex, the convex set of trace-one positive semidefinite matrices.

Determining whether a given point lies within a given moment body is a problem with numerous applications in quantum state estimation and polynomial optimization.

This moment body membership oracle can be addressed with semidefinite programming, for which several off-the-shelf interior-point solvers are available.

In this paper, inspired by techniques from quantum information theory, we argue analytically and geometrically that a much more efficient approach consists of minimizing globally a smooth strictly convex log-partition function, dual to a maximum entropy problem.

We analyze the curvature properties of this function, showing that conditioning is governed by the distance of the point to the boundary of the moment body, and we describe a neat geometric preconditioning algorithm that exploits this analysis.

Basic numerical experiments, comparing against interior-point and first-order semidefinite solvers, reveal a cubic dependence on the matrix size, similar to a few eigenstructure computations.

They also illustrate the two regimes of the oracle: dense projections are handled efficiently up to sizes of several hundred, while sparse instances such as matrix completion scale to matrices of size several thousand in minutes on a standard laptop.

In both cases the main bottleneck in this approach to large-scale semidefinite programming is moved almost entirely to efficient gradient storage and manipulation.