Graph Recovery from Incomplete Moment Information

We investigate a class of moment problems, namely recovering a measure supported on the graph of a function from partial knowledge of its moments, as, for instance, in some problems of optimal transport or density estimation. We show that the sole knowledge of first degree moments of the function, namely linear measurements, is sufficient to obtain asymptotically all the other moments by solving a hierarchy of semidefinite relaxations (viewed as moment matrix completion problems) with a specific sparsity-inducing criterion related to a weighted l(1)-norm of the moment sequence of the measure. The resulting sequence of optimal solutions converges to the whole moment sequence of the measure which is shown to be the unique optimal solution of a certain infinite-dimensional linear optimization problem (LP). Then one may recover the function by a recent extraction algorithm based on the Christoffel-Darboux kernel associated with the measure. Finally, the support of such a measure supported on a graph is a meager, very thin (hence sparse) set. Therefore, the LP on measures with this sparsity-inducing criterion can be interpreted as an analogue for infinite-dimensional signals of the LP in super-resolution for (sparse) atomic signals.

Automated summary

This study investigates a class of moment problems and proposes a method based on linear measurements, namely the first degree moments, to recover the complete information of a measure supported on the graph of a function. The results show that by solving a series of semidefinite relaxations, all the moments can be obtained. The function can be recovered using the optimal solution sequence.