Exploiting Sparsity for Semi-Algebraic Set Volume Computation

Understand

We provide a systematic deterministic numerical scheme to approximate the volume (i.e.

• the Lebesgue measure) of a basic semi-algebraic set whose description follows a sparsity pattern.
• As in previous works (without sparsity), the underlying strategy is to consider an infinite-dimensional linear program on measures whose optimal value is the volume of the set.
• This is a particular instance of a generalized moment problem which in turn can be approximated as closely as desired by solving a hierarchy of semidefinite relaxations of increasing size.