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 $\ell_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.



View Graph Recovery From Incomplete Moment Information