论文标题
从不完整的力矩信息中恢复图
Graph Recovery From Incomplete Moment Information
论文作者
论文摘要
我们研究了一类时刻问题，即从部分知识中恢复了函数图上支持的度量，例如在某些最佳传输或密度估计的问题中。我们表明，唯一了解该功能的一级矩，即线性测量值，足以通过求解与特定的稀疏性标准相关的特定的稀疏标准，以求解半稀疏标准的半稀疏标准，从而逐渐获得所有其他力矩。最佳解决方案的最终序列收敛到该度量的整个力矩序列，该序列被证明是特定无限二维线性优化问题（LP）的独特最佳解决方案。然后，人们可以根据与该度量相关的ChristOffel-Darboux内核来恢复函数。最后，在图上支持的这种度量的支持是微薄，非常薄（因此稀疏）集。因此，通过这种稀疏性诱导标准的度量的LP可以解释为在（稀疏）原子信号的超分辨率中LP的无限维信号的类似物。在数据科学中，它通常与信号的处理矩而不是信号本身有关。对于复杂的有价值信号，矩是傅立叶系数，并且许多过滤操作都以矩序列有效地进行。在数值近似算法中，在其Chebyshev系数的顺序中更有效地实现了许多对实际有价值信号的操作[19]。在瞬间层次结构方法中，许多非线性非凸问题进行了重新制定并在时刻顺序上解决。参见[13，12]及其中的参考。一旦计算出矩或大概的矩，就会面临从其矩时重建信号的反面问题。最近的工作[15]描述了一种基于Christoffel-Darboux内核的算法，以从知识时刻恢复功能的图。它的新颖性（和区分特征）是用半牙布函数（即多项式平方的最小化）近似函数（而不是函数本身）的图表，并具有L 1的平方函数，并具有较高的输入矩的尖锐收敛保证。在
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 relax-ations (viewed as moment matrix completion problems) with a specific sparsity inducing criterion related to a weighted 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. In data science, it is often relevant to process moments of a signal instead of the signal itself. For complex valued signals, the moments are Fourier coefficients, and many filtering operations are efficiently carried out in the sequence of moments. In numerical approximation algorithms, many operations on real valued signals are more efficiently implemented in their sequence of Chebyshev coefficients [19]. In the moment-SOS hierarchy approach, many nonlinear nonconvex problems are reformulated and solved approximately in the sequence of moments; see [13, 12] and references therein. Once moments or approximate moments have been computed, one is faced with the inverse problem of reconstructing the signal from its moments. The recent work [15] describes an algorithm based on the Christoffel-Darboux kernel, to recover the graph of a function from knowledge of its moments. Its novelty (and distinguishing feature) is to approximate the graph of the function (rather than the function itself) with a semialgebraic function (namely a minimizer of a sum of squares of polynomials) with L 1 and pointwise convergence guarantees for an increasing number of input moments. In
