The \(\mathcal A\)-truncated \(K\)-moment problem (Q486690): Difference between revisions

Given a finite subset \(\mathcal{A}\subseteq \mathbb{N}^n\), a semialgebraic set \(K\) in \(\mathbb{R}^n\) and a sequence \(y=(y_{\alpha})\) of real vectors in \(\mathbb{R}^n\) indexed by the elements of \(\mathcal{A}\), the \(\mathcal{A}\)-truncated \(K\)-moment problem (\(\mathcal{A}\)-TKMP) addresses the question of whether or not \(y\) admits a \(K\)-representing measure \(\mu\), i.e., \(\mu\) is a nonnegative Borel measure whose support is contained in \(K\) s.t. \(y_\alpha=\int_Kx^\alpha \mu(dx)\) for any \(\alpha\in\mathcal{A}\). The standard TKMP of degree \(d\) is the special instance of \(\mathcal{A}\)-TKMP obtained for \(\mathcal{A}=\{(\alpha_1,\dots,\alpha_n)\in\mathbb{N}^n: \alpha_1+\dots+\alpha_n\leq d\}\). Finding a solution of the \(\mathcal{A}\)-TKMP for \(y\) is equivalent to finding a flat extension of \(y\). Moreover, if \(y\) admits a flat extension, then there exists a finitely atomic \(K\)-representing measure for \(y\). The author presents a numerical algorithm for solving the \(\mathcal{A}\)-TKMP based on the solution of a hierarchy of semi-definite relaxations \(\{(SDR)_k\}_{k=1}^\infty\) for a moment optimization problem whose objective is a Riesz functional of a polynomial \(R\) generated in a certain randomized way (in computations, \(R\) is usually constructed via a random square matrix obeying to a Gaussian distribution). In particular, if \(y\) admits no \(K\)-representing measure and \(\mathbb{R}[x]_{\mathcal{A}}:=span\{x^\alpha: \alpha\in\mathcal{A}\}\) is \(K\)-full (i.e., \(\exists\, p\in\mathbb{R}[x]_{\mathcal{A}}\) positive on \(K\)), then \((SDR)_k\) is infeasible for all \(k\) big enough, which provides a certificate for the nonexistence of representing measures for \(y\). If \(y\) admits a \(K\)-representing measure, then with probability one (i.e., for almost all generated \(R\)) the algorithm produces a flat extension of \(y\) and so an \(r\)-atomic \(K\)-representing measure with \(r \leq |\mathcal{A}|\), either asymptotically or in finitely many steps. The obtained \(r\) may not be minimal, but some heuristic ideas about how to employ the algorithm to get an \(r\) close to the minimal one are shortly presented. Note that the finite convergence occurs in all the numerical experiments presented in the paper. Furthermore, the paper contains some applications of this algorithm to some hard computational problems that can be stated as special instances of the \(\mathcal{A}\)-TKMP, such as the decomposition problems for completely positive matrices and for sums of even powers of real linear forms.