# The Effective Countable Generalized Moment Problem

Lucas Gamertsfelder, Bernard Mourrain

► To cite this version:

Lucas Gamertsfelder, Bernard Mourrain. The Effective Countable Generalized Moment Problem. 2025. hal-04885482v4

HAL Id: hal-04885482

https://hal.science/hal-04885482v4

Preprint submitted on 1 Sep 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# THE EFFECTIVE COUNTABLE GENERALIZED MOMENT PROBLEM*

LUCAS GAMERTSFELDER† AND BERNARD MOURRAIN‡

**Abstract.** We establish new convergence rates for the Moment-Sum-of-Squares (Moment-SoS) relaxations for the Generalized Moment Problem (GMP) with countable moment constraints on vectors of measures, under dual optimum attainment, S-fullness and Archimedean conditions. These bounds, which adapt to the geometry of the underlying semi-algebraic set, apply to both the convergence of optima, and to the convergence in Hausdorff distance between the relaxation feasibility set and the GMP feasibility set. We show that under the previous conditions, the sequence of optimizers of the relaxations converge to the optimizer of the GMP for the weak* topology, provided this optimal measure is unique. This research provides quantitative geometry-adaptive rates for GMPs cast as linear programs on measures. It complements earlier analyses of specific GMP instances (e.g., polynomial optimization) as well as recent methodological frameworks that have been applied to volume computation and optimal control. We apply the convergence rate analysis to symmetric tensor decomposition problems, providing new effective error bounds for the convergence of the Moment-SoS hierarchies for tensor decomposition.

**Key words.** Generalized moment problems, Moment-SoS relaxations, Positivstellensatz, convergence rates, symmetric tensor decomposition

**MSC codes.** 44A60, 90C22, 15A69, 14P10

The Generalized Moment Problem (GMP) extends classical moment problems into the framework of conic linear programming over positive Borel measures. Building on moment problems such as those of Hamburger, Stieltjes, and Hausdorff, the GMP incorporates an optimization: finding measures that both satisfy moment constraints and minimize a given linear functional. With applications in numerous fields including control, signal processing, and statistics (see e.g. [26]), moment problems remain an active area of research since their introduction in the 19th century (see [1, 22, 40] for a historical overview).

Moment-Sum-of-Squares (SoS) relaxations provide a systematic approach to solving the GMP [24, 26]. The method proceeds in two steps: first relaxing the cone of positive Borel measures to non-negative linear functionals over an infinite-dimensional quadratic module; a relaxation that is exact under the Archimedean condition via Putinar's Positivstellensatz [34]. Second, truncating the quadratic module's degree to yield a hierarchy of semi-definite programs (SDPs), with accuracy improving as the truncation degree increases. This approach has been successfully applied to Polynomial Optimization Problems (POP), which are a special class of moment problems. While the convergence of Moment-SoS relaxations for POP was proven (under an Archimedean condition) in [24], only recent contributions provide polynomial convergence rates [14, 28, 4, 7, 6].

For the GMP, Moment-SoS relaxations were first investigated in [25], where qualitative convergence of the optimal values was established under Archimedean and strict positivity conditions. The analysis of Moment-SoS hierarchies for GMPs on a

<footnote>*Submitted to the editors 29/08/2025.</footnote>

<footnote>**Funding:** This research was carried out as part of the AROMATH team at the Centre Inria of Université Côte d'Azur.</footnote>

<footnote>†Centre Inria of Université Côte d'Azur, 2004 Route des Lucioles, 06902 Valbonne, France (Lucas.Gamertsfelder@inria.fr).</footnote>

<footnote>‡Centre Inria of Université Côte d'Azur, 2004 Route des Lucioles, 06902 Valbonne, France (Bernard.Mourrain@inria.fr).</footnote>
single positive measure was further investigated e.g. in [12, 13] for the solution of GMP via flat truncation, in [30, 18] regarding the uniqueness of the maximizer and the exactness of the relaxation under feasibility and regularity conditions, or in [27] via sparse flat extension properties. For an extended overview on moment problems and positive polynomials, we refer to [40].

The study of convergence rates for the Moment-SoS hierarchy in the GMP context has also advanced. For specific applications, such as Polynomial Optimization Problems (where there is a single moment equality constraint) [42, 32, 19, 14, 28, 4, 7], optimal control problems (with moment equality constraints on a single occupational measure) [21], and volume computation (exploiting Stokes equations for moment constraints) [44], convergence rates have been analyzed. More recently, [39] introduced a methodological framework to compute bounds on convergence rates of the optima for GMPs involving vectors of measures with moment equality constraints, leveraging an Effective Putinar's Positivstellensatz [4]. This framework was applied to derive polynomial convergence rates for applications including optimal control and volume computation. However, explicit rates for general cases of GMPs were not established.

In this paper, we establish convergence rates for both the optima and feasibility sets for GMPs with countable moment constraints on vectors of measures. We define a linear program on measures as one where the unknown is a vector $\mu = [\mu_1, \dots, \mu_m]$ of positive measures $\mu_i$ supported on compact sets $S_i \subset \mathbb{R}^{n_i}$. Where $J$ is a countable index set, the constraints are of the form $t - \langle \mu, h \rangle \in K$ where $K$ is a cone in $\mathbb{R}^J$, $t \in \mathbb{R}^J$, $h = (h_{i,j}) \in (\prod_{i=1}^m C_i)^J$ is a matrix of continuous functions $h_{i,j} \in C_i$ on $S_i$ and $\langle \mu, h \rangle = [\sum_{i=1}^m \int_{S_i} h_{i,j} d\mu_i, j \in J]$. The objective function is of the form $\langle \mu, f \rangle = \sum_{i=1}^m \int_{S_i} f_i d\mu_i$ where $f = (f_1, \dots, f_m) \in \prod_{i=1}^m C_i$. This linear program on measures is approximated by a hierarchy of Moment-SoS convex relaxations (also known as Lasserre's relaxation).

We establish the convergence of these hierarchies under dual optimum attainment, $S$-fullness and Archimedean conditions, and provide polynomial convergence rates that adapt to the underlying semi-algebraic set geometry. Our results apply both to the convergence of optima and to the convergence of the moment feasibility sets. Our main results are the following.

**Theorem A.** (See Corollary 2.5) *Under Assumption 1.3, Assumption 1.9 and Assumption 2.1,*

$$0 \le \mathfrak{p} - \mathfrak{p}_{\ell} \le \mathfrak{d} - \mathfrak{d}_{\ell} \le \kappa \ell^{-\theta}$$

where $\mathfrak{p}, \mathfrak{d}$ (resp. $\mathfrak{p}_{\ell}, \mathfrak{d}_{\ell}$) are the optima of the (resp. relaxation of the) primal and dual Generalized Moment Problem (1.2) and (1.3) (resp. at order $\ell \in \mathbb{N}$), and $\kappa, \theta$ are constants depending explicitly on the input data of the GMP.

**Theorem B.** (See Theorem 2.11) *Under Assumption 1.3, Assumption 1.9 and Assumption 2.1, for $\ell \ge k$,*

$$\rho_H(\mathcal{F}^{(k)}, L_{\ell}^{(k)}) \le \kappa' \ell^{-\theta},$$

where $\mathcal{F}^{(k)}, L_{\ell}^{(k)}$ are respectively the cones of moment sequences truncated at order $k$ of positive measures and truncated linear functionals positive on the degree $\ell$ truncated quadratic module, and $\rho_H$ is the Hausdorff distance.

These results establish polynomial rates of convergence for GMPs, building on the recent progress on the Effective Positivstellensatz (see Theorem 2.3).

As a consequence, we deduce (see Theorem 2.13) that under Assumptions 1.3, 1.9 and 2.1, the sequence of optimizers of the relaxations converge to the optimizer of the
GMP, provided there is a unique optimal measure of the GMP.

We apply this analysis to minimal symmetric tensor decomposition (Section 3). Symmetric tensors play important roles in independent component analysis, telecommunications, and psychometrics; see [20, 10] for overviews. Additive decompositions of a tensor provide a convenient representation, and minimal decompositions are particularly valuable [29]. Current algorithms can recover symmetric decompositions [10], and minimal forms for low-rank tensors [29]. However, high-rank tensor decompositions remain challenging. We propose an optimization approach to this problem, formulating the minimal decomposition as a GMP. Our approach leverages the homogeneous polynomial representation of symmetric tensors, and the apolar product. A homogeneous polynomial admits a Waring decomposition when its dual linear functional with respect to the apolar product can be represented as a finite sum of weighted Dirac measures. The GMP formulation is based upon finding such a minimal representation. We prove that these GMP problems have no duality gap, and we provide new results of attainment of optima and new convergence rates (Theorem 3.2, Theorem 3.7).

The paper is structured as follows. In Section 1, we formally introduce the GMP and its dual formulation. We present the S-fullness condition, which ensures both strong duality between the primal and dual formulations, and compactness in the primal. Additionally, we verify that the S-fullness condition holds in the case of the POP. In Section 2, we introduce the Moment-Sum-of-Squares (SoS) relaxations of the GMP and analyze their rate of convergence under the S-fullness condition and Archimedean condition. We prove our first main result, Corollary 2.5, providing bounds on the difference in value between the GMP and its Moment-SoS relaxation. We also prove the second main result, Theorem 2.11, providing bounds on the Hausdorff distance between the GMP cone and the relaxed cones. Finally, in Section 3, we investigate symmetric tensor decomposition problems and formulate them as GMPs. We verify that the S-fullness condition holds and state the convergence rates of the moment relaxations using the main results. We provide examples illustrating the numerical behavior of the approach.

**1. The Generalized Moment Problem.** Let $S \subset \mathbb{R}^n$ be a compact subset of $\mathbb{R}^n$. We denote by $C(S)$ the set of continuous functions on $S$. It is a Banach space when endowed with the sup-norm: for $q \in C(S)$, $\|q\|_{\infty} = \max_{x \in S} |q(x)|$. We denote by $C_+(S)$ the convex cone of continuous functions $f \in C(S)$ which are positive on $S$: $\forall x \in S, f(x) \ge 0$.

We denote by $M(S) = C(S)^*$ the space of continuous linear functionals on $C(S)$, equipped with the weak* topology and the operator norm: for $\lambda \in M(S)$, $\|\lambda\|_{\infty} = \max_{\|q\|_{\infty} \le 1} \langle \lambda, q \rangle$. In the weak* topology, a sequence $\{\lambda_n\} \subset M(S)$ converges to $\lambda \in M(S)$ if and only if

$$ (1.1) \qquad \forall q \in C(S), \quad \langle \lambda_n, q \rangle \to \langle \lambda, q \rangle. $$

By [3, Theorem 4.3.13], $M(S)$ is the set of finite signed Borel measures on $S$, so that $\forall \mu \in M(S), \int_S q d\mu \stackrel{\text{def}}{=} \langle \mu, q \rangle$.

Note that when the space of measures $M(S)$ is endowed with the norm of total variation (equivalently the operator norm on the linear functional representation [3, p. 186]) it is a Banach space.

Let $M_+(S)$ be its positive cone, i.e., the space of positive Borel measures on $S$. By Riesz-Haviland Theorem (see [37, Theorem 2.14]), for any $\mu \in M(S)$, $\mu \in M_+(S)$ if and only if $\forall p \in C_+(S), \langle \mu, p \rangle \ge 0$.
Let $m$ be a non-zero natural number. For $i = 1, \dots, m$, let $S_i \subset \mathbb{R}^{n_i}$ be a compact subset of $\mathbb{R}^{n_i}$ for $n_i \in \mathbb{N}$. Where $\mathcal{C}(S_i)$, $\mathcal{M}(S_i)$, $\mathcal{M}_+(S_i)$, $\mathcal{C}_+(S_i)$ are as above, define $\mathcal{C} = \prod_{i=1}^m \mathcal{C}(S_i)$, $\mathcal{M} = \prod_{i=1}^m \mathcal{M}(S_i)$, $\mathcal{M}_+ = \prod_{i=1}^m \mathcal{M}_+(S_i)$, $\mathcal{C}_+ = \prod_{i=1}^m \mathcal{C}_+(S_i)$.

Let $f \in \mathcal{C}$ and $J$ be a countable index set. For $j \in J$, let $t_j \in \mathbb{R}$ and $h_j \in \mathcal{C}$. Set $t = (t_j)_{j \in J}$, $h = (h_j)_{j \in J} = (h_{i,j})_{1 \le i \le m, j \in J} \in \mathcal{C}^J$ and $K \subset \mathbb{R}_+^J$ a closed convex cone in the positive orthant of $\mathbb{R}^J$, the space of real sequences indexed by $J$ endowed with the product topology. We equip $\mathcal{C}$ and $\mathcal{M}$ with the product topologies: sequences in the former sets converge if and only if each component converges independently. We consider the $m$-dimensional Generalized Moment Problem (m-GMP): For $f \in \mathcal{C}$, $h_j \in \mathcal{C}$ for all $j \in J$,

$$ (1.2) \qquad \mathfrak{p}^* \stackrel{\text{def}}{=} \inf_{\mu} \langle \mu, f \rangle \qquad \begin{array}{ll} \text{s.t.} & t - \langle \mu, h \rangle \in K \\ & \mu \in \mathcal{M}_+ \end{array} $$

where

$$ \langle \mu, f \rangle \stackrel{\text{def}}{=} \sum_{i=1}^{m} \langle \mu_i, f_i \rangle, \quad \text{and} \quad \langle \mu, h \rangle \stackrel{\text{def}}{=} \left( \sum_{i=1}^{m} \langle \mu_i, h_{i,j} \rangle \right)_{j \in J} $$

The feasible set of $\mathfrak{p}^*$ has the form

$$ \Omega \stackrel{\text{def}}{=} \{ \mu \in \mathcal{M}_+ | t - \langle \mu, h \rangle \in K \}. $$

We consider also the $m$-dimensional Dual Generalized Moment Problem (m-DGMP):

$$ (1.3) \qquad \begin{array}{ll} \mathfrak{d}^* = \sup & t \cdot v \\ \text{s.t.} & f - h \cdot v \in \mathcal{C}_+, \\ & v \in -K^*. \end{array} $$

where $h \cdot v = \sum_{j \in J} h_j v_j$ and $K^*$ is the dual cone of $K$, defined as $K^* = \{v \in \mathbb{R}_0^J : \forall u \in K, u \cdot v \ge 0\}$, with $\mathbb{R}_0^J$ being the space of sequences of finite support.

**Example 1.1.** When $m = 1$, $N = 1$, $h = 1 \in \mathcal{C}(S)$, $t = 1 \in \mathbb{R}$ and $K = \{0\}$, we recover the classical polynomial optimization problem

$$ (1.4) \qquad \begin{array}{lll} f_{\min} = \inf_{x \in S} f(x) = & \inf & \langle \mu, f \rangle \\ & \text{s.t.} & 1 - \langle \mu, 1 \rangle = 0 \\ & & \mu \in \mathcal{M}_+ \end{array} \qquad \begin{array}{ll} = & \sup \\ \text{s.t.} & f - v \in \mathcal{C}_+(S) \\ & v \in \mathbb{R}. \end{array} $$

The following standard assumption (see e.g. [25, Lemma 1]), which ensures the existence of at least one measure satisfying all moment constraints *holds throughout this paper*.

**Assumption 1.2.** The problem (1.2) admits a feasible solution.

**1.1. Slater's condition and compactness.** To guarantee the existence of solutions to the Generalized Moment Problem, we make the following assumption:

**Assumption 1.3 (S-fullness).** The S-fullness condition is said to be satisfied for problem (1.2) when there exists $b = h \cdot w$, $w \in K^*$, such that $b_i > 0$ on $S_i$ for $i = 1, \dots, m$.
Note that S-fullness holds trivially in the case Ω describes a product of probability measures: order the matrix h so that $(h_{i,j})_{1≤i,j≤m} = \text{Id}$ and set $w = (\overbrace{1, \dots, 1}^{m}, 0, 0, \dots)$.

Then, $b = (\overbrace{1, \dots, 1}^{m})$ and $b_i = 1 > 0$ for all $i = 1, \dots, m$.

Observe that the problem being S-full implies that Ω is bounded:

**LEMMA 1.4.** *Under Assumption 1.3, the set Ω is weak*\* *compact in the product topology. Furthermore, the value of p\* is attained.*

*Proof.* See Appendix A.

We consider an interior point criterion for strong duality between problems p\* and d\*:

*Condition 1.5* (Slater's Condition). Let $X, Z$ be Banach spaces, and $Y = X^*$ and $V = Z^*$ their respective duals. Let $A: X \to Z$ be a continuous linear operator. Define $P$ as a positive cone in $X$, and $Q$ a positive cone in $Z$. Let $b \in Z$ and $c \in Y$. A problem of the form

$$ (1.5) \qquad \begin{array}{ll} \inf & \langle x, c \rangle \\ \text{s.t.} & Ax - b \in Q, \\ & x \in P, \end{array} $$

is said to satisfy Slater's Condition when it has a finite infimum, and $\exists x_0 \in P$ such that $Ax_0 - b$ is in the interior of $Q$.

The importance of Slater's Condition lies in its establishment of strong duality between problem (1.5) and its dual, given by:

$$ (1.6) \qquad \begin{array}{ll} \sup & \langle b, w \rangle \\ \text{s.t.} & c - A^*w \in P^*, \\ & w \in Q^*. \end{array} $$

**THEOREM 1.6** ([2, Theorem 10]). *If Slater's Condition is satisfied for (1.5), then strong duality holds between the problems (1.5) and (1.6).*

*Remark 1.7.* In [2, Theorem 10], the hypothesis requires an element from the Mackey interior. Since we work in Banach spaces, which are locally convex, the Mackey topology coincides with the norm topology on convex sets [8, Proposition 4, Chapter IV]. Therefore, we only consider points in the interiors with respect to the norm induced by our Banach spaces.

**PROPOSITION 1.8.** *Under Assumption 1.3, strong duality holds between d\* and p\*.*

*Proof.* See Appendix A. □

While strong duality $p^* = d^*$ and attainment of $p^*$ hold under Assumption 1.3, for the subsequent analysis of convergence rates, we require also that the dual optimum is attained:

*Assumption 1.9.* The problem (1.3) attains its supremum at $v^*$.

The satisfaction of this assumption depends on the specific structure of the GMP considered. It holds naturally for some GMPs such as in the polynomial optimization setting, and in the symmetric tensor decomposition setting (see Proposition 3.1 and
**Proposition 3.6).** For the so-called A-truncated S-moment problem, a condition of strict S-positivity is used to show the existence of a maximizer [30, Proposition 3.6]. In the optimal control setting, Assumption 1.9 is guaranteed by controllability conditions [17, Equation (3.7)], [16, Proposition 8(ii)]).

**2. Moment-SoS relaxations of the Generalized Moment Problem.** In the following sections, the usage of $i$ refers to an arbitrary element from the sequence $\{1, \dots, m\}$, where $m$ is the dimension of the generalized moment problem. Let $\mathcal{R}_i$ be the ring of polynomials in $n_i$ variables. We view $\mathcal{R}_i$ as a subspace of $\mathcal{C}(S_i)$, the space of continuous functions on the compact set $S_i$. By the Stone-Weierstrass theorem, $\mathcal{R}_i$ is a dense subspace of $\mathcal{C}(S_i)$ with respect to the sup-norm $\| \cdot \|_{\infty}$. Any measure $\mu_i \in \mathcal{M}(S_i)$ defines a linear functional $L_{\mu_i}$ on $\mathcal{R}_i$ via integration:

$$L_{\mu_i}(p) = \int_{S_i} p(x) d\mu_i(x) \quad \text{for all } p \in \mathcal{R}_i.$$

The functional $L_{\mu_i}$ is an element of $\mathcal{D}_i \stackrel{\text{def}}{=} \mathcal{R}_i^*$, the algebraic dual of $\mathcal{R}_i$. We equip $\mathcal{D}_i$ with the weak* topology, where a sequence of functionals converges if it converges pointwise for every polynomial in $\mathcal{R}_i$. The Riesz-Haviland theorem gives a necessary and sufficient condition for a linear functional $L \in \mathcal{D}_i$ to be representable by a positive measure on $S_i$. Specifically, such a representing measure $\mu_i \in \mathcal{M}_+(S_i)$ exists if and only if $L(p) \ge 0$ for all polynomials $p \in \mathcal{R}_i$ that are non-negative on $S_i$. This allows us to work directly with linear functionals on polynomials instead of measures.

Hereafter, we assume that the compact sets $S_i$ are defined as

$$(2.1) \qquad S_i = \{x \in \mathbb{R}^{n_i}, g_{i,1}(x) \ge 0, \dots, g_{i,r_i}(x) \ge 0\}$$

for some polynomial vectors $g_i = (g_{i,1}, \dots, g_{i,r_i}) \in \mathcal{R}_i^{r_i}$, where $\mathcal{R}_i^{r_i}$ is the $r_i$-fold product space. We denote by $\mathcal{P}os(S_i)$ the convex cone of polynomials $p \in \mathcal{R}_i$ such that $\forall x \in S_i, p(x) \ge 0$. Hereafter, we consider $S_i$ to be a set of the form $S_i = g_i^{-1}(\mathbb{R}_+^{r_i})$ with $g_i \in \mathcal{R}_i^{r_i}$. Let $\Sigma_i^2 = \{q_1^2 + \dots + q_s^2 \mid s \in \mathbb{N}, q_k \in \mathcal{R}_i\} \subset \mathcal{R}_i$ be the convex cone of Sums of Squares (SoS). The quadratic module generated by the polynomials $g_i \in \mathcal{R}_i^{r_i}$ is

$$Q(g_i) \stackrel{\text{def}}{=} \Sigma_i^2 + \sum_{j=1}^{r_i} \Sigma_i^2 \cdot g_{i,j}.$$

Hereafter, we will make the following assumption:

**Assumption 2.1 (Archimedean quadratic module).** For all $i = 1, \dots, m$, the quadratic module $Q(g_i)$ contains a polynomial of the form $R_i^2 - (X_1^2 + \dots + X_{n_i}^2)$, where $R_i \in \mathbb{R}_+$.

This assumption is easy to satisfy when $S_i$ is bounded, that is, included in a ball of some radius $R_i$ centered at the origin, since we can add the sign constraint $R_i^2 - (X_1^2 + \dots + X_{n_i}^2) \ge 0$ to $g_i$ without changing $S_i$.

We define the dual cones: $\mathcal{L}(g_i) = \mathcal{Q}(g_i)^* = \{\lambda \in \mathcal{D}_i \mid \forall q \in \mathcal{R}_i, \langle \lambda, g_{i,j}q^2 \rangle \ge 0, \langle \lambda, q^2 \rangle \ge 0, \forall j = 1, \dots, r_i\}$ and $\mathcal{L} = \prod_{i=1}^m \mathcal{L}(g_i)$, $\mathcal{Q} = \prod_{i=1}^m \mathcal{Q}(g_i)$. Define also the product spaces $\mathcal{D} \stackrel{\text{def}}{=} \prod_{i=1}^m \mathcal{D}_i$ and $\mathcal{R} \stackrel{\text{def}}{=} \prod_{i=1}^m \mathcal{R}_i$.

Under Assumption 2.1, it is readily verified by Putinar's Positivstellensatz that $\mathcal{L}(g_i) = \mathcal{M}_+(S_i)$. Therefore, given a cost function $f \in \mathcal{R}$ and $h_{i,j} \in \mathcal{R}_i$ for $j \in J$, the
primal relaxation of (1.2) translates as

$$
\begin{equation} \tag{2.2}
\begin{aligned}
\mathfrak{p}^* &= \inf \langle \lambda, f \rangle \\
\text{s.t.} \quad &t - \langle \lambda, h \rangle \in K, \\
&\lambda \in \mathcal{L},
\end{aligned}
\end{equation}
$$

whose feasible set is denoted

$$
(2.3) \qquad \mathcal{F} = \{\lambda \in \mathcal{L} \mid t - \langle \lambda, h \rangle \in K\}.
$$

We consider also the dual SoS relaxation

$$
\begin{equation} \tag{2.4}
\begin{aligned}
\mathcal{v}^* &= \sup v \cdot t \\
\text{s.t.} \quad &f - h \cdot v \in \mathcal{Q} \\
&v \in -K^*
\end{aligned}
\end{equation}
$$

whose feasible set is

$$
(2.5) \qquad E = \{v \in -K^* : f - h \cdot v \in \mathcal{Q}\}.
$$

It is readily verified under Assumption 2.1 that $\mathcal{P}$os = $\overline{\mathcal{Q}}$, where the closure of $\mathcal{Q}$ is taken in the weak* topology ($p_n \xrightarrow{w} p$ in $\mathcal{R}$ iff $\forall \lambda \in \mathcal{D}$, $\langle \lambda, p_n \rangle \to \langle \lambda, p \rangle$, which is equivalent to point-wise convergence). We deduce from the previous section the following result:

LEMMA 2.2. Under Assumption 1.3 and Assumption 2.1, F is weak* compact and p* = v*. Furthermore, the value of p* is attained.

**2.1. Convergence of the optima.** We now introduce the Moment-SoS hierar-
chies, which consist of a sequence of convex optimization problems indexed by degree
$l \in \mathbb{N}$. For a vector $f = [f_1, \dots, f_m] \in \mathbb{R}$, let $\deg(f) = \max_{i=1,\dots,m} \deg(f_i)$. For
$l \in \mathbb{N}$, let $\Sigma_{i,l}^2 = \{q_1^2 + \dots + q_s^2 \mid s \in \mathbb{N}, q_k \in \mathcal{R}_{i,\lfloor l/2 \rfloor} \} \subset \mathcal{R}_{i,l}$ be the convex finite-
dimensional cone of Sums of Squares (SoS) of degree $\le l$. The truncated quadratic
module generated by the polynomials $g_i \in \mathcal{R}_i^{r_i}$ in degree $\le l$ is

$$
Q_{\ell}(g_i) \stackrel{\text{def}}{=} \Sigma_{i,\ell}^2 + \sum_{j=1}^{r_i} \Sigma_{i,\ell-\deg(g_{i,j})}^2 \cdot g_{i,j}.
$$

Let $Q_\ell = \prod_{i=1}^m Q_\ell(g_i)$, $\mathcal{L}_\ell(g_i) = Q_\ell(g_i)^* = \{\lambda \in \mathcal{D}_i \mid \forall q \in Q_\ell(g_i), \langle \lambda, q \rangle \ge 0\}$, and
$\mathcal{L}_\ell = \prod_{i=1}^m \mathcal{L}_\ell(g_i)$.

Henceforth, we specify $f$ and $h_j$ to be elements of $\mathcal{R}$. Define

$$
J_{\ell} = \{j \in J \mid \text{ for all } i \in \{1, \dots, m\}, \deg(h_{i,j}) \le \ell\}
$$

and let $h^\ell \stackrel{\text{def}}{=} (h_{i,j})_{1\le i\le m, j\in J_\ell}$, $t^\ell \stackrel{\text{def}}{=} (t_j)_{j\in J_\ell}$ and $K^\ell \stackrel{\text{def}}{=} \{u^\ell \in \mathbb{R}^{J_\ell} \mid \exists u \in K \text{ such that} \\ u_j = u_j^\ell \text{ for all } j \in J_\ell\}$. We then define the corresponding dual cone $(K^\ell)^* \subseteq \mathbb{R}_0^{J_\ell}$ as

$$
(K^{\ell})^{*} = \{v^{\ell} \in \mathbb{R}_{0}^{J_{\ell}} \mid \forall u^{\ell} \in K^{\ell}, \sum_{j \in J_{\ell}} u_{j}^{\ell} v_{j}^{\ell} \geq 0\}.
$$

The cone $K^\ell$ is the projection of the original cone $K \subseteq \mathbb{R}_+^J$ onto the coordinates indexed by $J_\ell$. We consider the following hierarchy of truncated primal relaxations

$$
\begin{equation} \tag{2.6}
\begin{aligned}
\mathfrak{p}_{\ell}^{*} &= \inf \langle \lambda, f \rangle \\
\text{s.t.} \quad & t^{\ell} - \langle \lambda, h^{\ell} \rangle \in K^{\ell}, \\
& \lambda \in \mathcal{L}_{\ell},
\end{aligned}
\end{equation}
$$
along with the corresponding dual $\ell$-degree SoS relaxations:

$$ (2.7) \qquad \begin{aligned} \mathfrak{d}_{\ell}^{*} &= \sup v \cdot t^{\ell} \\ \text{s.t.} \quad &f - h^{\ell} \cdot v \in \mathcal{Q}_{\ell}, \\ &v \in -(K^{\ell})^{*}. \end{aligned} $$

It is readily verified that weak duality holds: $\mathfrak{d}_{\ell}^{*} \le \mathfrak{p}_{\ell}^{*}$ and that $\mathfrak{d}_{\ell}^{*} \le \mathfrak{d}_{\ell+1}^{*} \le \mathfrak{d}^{*}$, $\mathfrak{p}_{\ell}^{*} \le \mathfrak{p}_{\ell+1}^{*} \le \mathfrak{p}^{*}$.

To analyze the convergence of the hierarchy, we will use the following Positivstellensätze, which hold under Assumption 2.1:

**THEOREM 2.3 (Effective Positivstellensätze).** For $n \ge 2$, $g \subset \mathbb{R}$ finite such that $\mathcal{Q}(g)$ satisfies Assumption 2.1, $S = \{x \in \mathbb{R}^n | \forall p \in g, p(x) \ge 0\}$ and $p$ strictly positive on $S$, one has that $p \in \mathcal{Q}_{\ell}(g)$ for

$$ \ell \ge \max\{\gamma \left( \frac{p_{\max}}{p_{\min}} \right)^{\frac{1}{\theta}}, \ell_0\}. $$

where $\theta > 0$, and $\gamma$, $\ell_0$ are constants depending on $n$, $g$ and $\deg(p)$, and $p_{\min} \stackrel{\text{def}}{=} \min_{x \in S} p(x)$, $p_{\max} \stackrel{\text{def}}{=} \max_{x \in S} p(x)$. We have

* $\theta = \frac{1}{2.5nL}$, $\gamma = \gamma'(n, g) \deg(p)^{-3.5nL}$ and $\ell_0 = 0$, where $\gamma'(n, g)$ is a constant depending on $n$ and $g$, $L$ is the exponent in the Łojasiewicz inequality between the semi-algebraic distance defined from the polynomials $g$ and the Euclidean distance to $S$ (see [4, Theorem 1.7]),

* $\theta = 1$, $\gamma$ depends polynomially on $\deg(p)$ for $n$ fixed and $\ell_0 = \pi n \sqrt{2n} \deg(p)$, when $S$ is the box $S = [-\rho, \rho]^n$ and $g = \{\rho^2 - x_i^2, i = 1, \dots, n\}$ (see [7, Theorem 11]),

* $\theta = 2$, $\gamma$ depends polynomially on $\deg(p)$ for $n$ fixed and $\ell_0 = \pi n \sqrt{2n} \deg(p)$, when $S$ is the box $S = [-1, 1]^n$ and $g = \{\prod_{i=1}^n (1-x_i^2)^{e_i}$, for $e = [e_1, \dots, e_n] \in \{0, 1\}^n\}$ (see [28, Corollary 3]),

* $\theta = 2$, $\gamma$ depends polynomially on $\deg(p)$ for $n$ fixed and $\ell_0 = 2n \deg(p)^{\frac{3}{2}}$, when $S = \{x \in \mathbb{R}^n | 1 - \|x\|^2 \ge 0\}$ is the unit ball (see [43, Theorem 3]).

The main result of the section is as follows:

**THEOREM 2.4.** Let Assumption 1.3, Assumption 1.9 and Assumption 2.1 be satisfied. Let $\mathfrak{d}^*$ be as in (1.3) and $\mathfrak{d}_{\ell}^*$ be as in (2.7). For

$$ (2.8) \qquad \ell \ge \max \left( \max_{i=1, \dots, m} \ell_{i,0}, \max_{j \in \text{supp}(v^*) \cup \text{supp}(w)} \deg(h_j) \right), $$

we have

$$ 0 \le \mathfrak{d}^* - \mathfrak{d}_{\ell}^* \le \kappa \ell^{-\theta} $$

where

$$ (2.9) \qquad \begin{aligned} \kappa &= \max_{i=1, \dots, m} \frac{t \cdot w}{(h_i \cdot w)_{\min}} \gamma_i^{\theta_i} (2f_{i, \max} + \|v^*\|_1 h_{i, \max}^*) \\ \theta &= \min_{i=1, \dots, m} \theta_i \end{aligned} $$

with

* $f_{i, \max} \stackrel{\text{def}}{=} \max_{x \in S_i} f_i(x)$

* $h_{i, \max}^* \stackrel{\text{def}}{=} \max_{j \in \text{supp}(v^*)} \max_{x \in S_i} |h_{i, j}(x)|$
• $\gamma_i$, $\theta_i$ as in Theorem 2.3 for $S_i$,

• $w$ as in Assumption 1.3,

• $v^*$ the vector achieving the supremum in $\mathfrak{d}^*$.

*Proof.* By Assumption 1.9, the dual optimizer $v^*$ of (1.3) exists. For any $\epsilon > 0$, define the perturbed vector $v_\epsilon$ by

$$ (2.10) \qquad v_{\epsilon} = v^{*} - \epsilon w, $$

where $w$ is as in Assumption 1.3. Accompanying $v_\epsilon$, we have the strictly positive polynomial sequence $q = (q_i)_{i=1}^m \in \mathcal{C}$ defined as follows:

$$ q \stackrel{\text{def}}{=} f - h \cdot v_{\epsilon} = f - h \cdot v^{*} + \epsilon h \cdot w > 0, $$

by the feasibility of $v^*$ in (1.3), and since $h \cdot w > 0$ by Assumption 1.3. Note that the premise for Theorem 2.3 holds for this $q \in \mathcal{P}os$. We have

$$ \ell \ge \max_{i=1,...,m} \max \left( \gamma_i \left( \frac{q_{i,\max}}{q_{i,\min}} \right)^{\frac{1}{\theta_i}}, \ell_{i,0} \right) \implies q \in \mathcal{Q}_{\ell}. $$

For each $i = 1, \dots, m$, by the feasibility of $v^*$ in (1.3),

$$ (2.11) \qquad q_{i,\min} \ge (f_i - h_i \cdot v^*)_{\min} + (\epsilon h_i \cdot w)_{\min} \ge \epsilon (h_i \cdot w)_{\min} > 0, $$

where $(h_i \cdot w)_{\min} > 0$ by Assumption 1.3. Letting

$$ h_{i,\max}^* = \max_{j \in \text{supp}(v^*)} \max_{x \in S_i} |h_{i,j}(x)|, $$

we have

$$ (2.12) \qquad \begin{aligned} q_{i,\max} &= (f_i - h_i \cdot v_\epsilon)_{\max} \le f_{i,\max} + (-h_i \cdot v^*)_{\max} + \epsilon (h_i \cdot w)_{\max}, \\ &\le f_{i,\max} + \|v^*\|_1 h_{i,\max}^* + \epsilon (h_i \cdot w)_{\max}, \\ &\le 2 f_{i,\max} + \|v^*\|_1 h_{i,\max}^*, \end{aligned} $$

where the final inequality follows by choosing $\epsilon \le f_{i,\max}/(h_i \cdot w)_{\max}$. By (2.11) and (2.12), $q \in \mathcal{Q}_\ell$ for

$$ (2.13) \qquad \ell \ge \max_{i=1,...,m} \max \left( \gamma_i \left( \frac{2f_{i,\max} + \|v^*\|_1 h_{i,\max}^*}{\epsilon(h_i \cdot w)_{\min}} \right)^{\frac{1}{\theta_i}}, \ell_{i,0} \right). \quad \square $$

By the optimality of $v^*$, we have that $\mathfrak{d}^* - t \cdot v^* = 0$. By (2.10), we have that $t \cdot v^* - \epsilon t \cdot w - t \cdot v_\epsilon = 0$. Therefore,

$$ 0 \le \mathfrak{d}^* - \mathfrak{d}_\ell^* = \mathfrak{d}^* - (t \cdot v^* - \epsilon t \cdot w - t \cdot v_\epsilon) - \mathfrak{d}_\ell^* = t \cdot v_\epsilon - \mathfrak{d}_\ell^* + \epsilon t \cdot w, $$

By (2.8), $\text{supp}(v_\epsilon) \subseteq J_\ell$, implying that

$$ f - h \cdot v_\epsilon = f - h^\ell \cdot v_\epsilon \in \mathcal{Q}_\ell $$

and

$$ \sum_{j \in J_\ell} v_{\epsilon,j} u_j^\ell \le 0 $$
for all $u^\ell \in K^\ell$, since $v_\epsilon \in -K^*$. That is, $v_\epsilon$ is feasible in $\mathcal{D}_\ell^*$, and $t \cdot v_\epsilon - \mathcal{D}_\ell^* \le 0$. Thus

$$0 \le \mathcal{D}^* - \mathcal{D}_\ell^* \le \epsilon(t \cdot w).$$

Note that $t \cdot w > 0$ (see (A.1) in the proof of Lemma 1.4). Rearranging (2.13) for $\epsilon$ and substituting into the above gives the result for $\ell \ge \max(\max_{i=1,...,m} \ell_{i,0}, \max_{j \in \text{supp}(v^*) \cup \text{supp}(w)} \text{deg}(h_j))$:

$$0 \le \mathcal{D}^* - \mathcal{D}_\ell^* \le \max_{i=1,...,m} \left( \frac{t \cdot w}{(h_i \cdot w)_{\min}} \left( \frac{\gamma_i}{\ell} \right)^{\theta_i} (2f_{i,\max} + \|v^*\|_1 h_{i,\max}) \right) \le \kappa \ell^{-\theta}.$$

with $\kappa$ and $\theta$ as in (2.9).

**COROLLARY 2.5.** *Under Assumption 1.3, Assumption 1.9 and Assumption 2.1,*

$$0 \le \mathfrak{p}^* - \mathfrak{p}_\ell^* \le \mathcal{D}^* - \mathcal{D}_\ell^* \le \kappa \ell^{-\theta}$$

with $\kappa, \theta$ as in Theorem 2.4.

*Proof.* Follows from strong duality in the generalized moment problem (Proposition 1.8), weak duality in the Moment-SoS hierarchy and Theorem 2.4. □

**2.2. Convergence of the moment feasibility sets.** In this section, we establish the convergence between the GMP feasibility set (2.3) and the feasibility set of the relaxations.

Recall that $\mathcal{R}_{i,k}$ is the space of polynomials in $\mathcal{R}_i$ of degree at most $k$. For $k \in \mathbb{N}$ and $\lambda \in \mathcal{D}_i$, let $\lambda^{(k)} \in \mathcal{D}_i$ such that $\lambda^{(k)}_{|\mathcal{R}_{i,k}} = \lambda_{|\mathcal{R}_{i,k}}$ and $\langle \lambda^{(k)}, \mathbf{x}_i^\alpha \rangle = 0$ if $|\alpha| > k$. Here, $\lambda^{(k)}$ is the k-truncation of the linear functional $\lambda$, meaning its moments agree with $\lambda$ up to degree $k$ and are zero for degrees greater than $k$.

Let $\mathcal{D}_i^{(k)} = \{\lambda^{(k)} | \lambda \in \mathcal{D}_i\}$ and $\mathcal{D}^{(k)} = \prod_{i=1}^m \mathcal{D}_i^{(k)}$. To study the distance between spaces of linear functionals, we equip $\mathcal{D}_i$ with the weighted norm $\|\cdot\|_i$ defined such that for $\mathbf{x}_i = (\mathbf{x}_{i,1}, \dots, \mathbf{x}_{i,n_i})$,

$$\|\lambda\|_i \stackrel{\text{def}}{=} \sup_{\alpha \in \mathbb{N}^{n_i}} \frac{|\langle \lambda, \mathbf{x}_i^\alpha \rangle|}{\alpha!}.$$

This norm was applied in [23] to ensure continuity of linear functionals over closed (not necessarily compact) semi-algebraic sets. We denote $\mathcal{D}_i^\flat = \{\lambda \in \mathcal{D}_i | \|\lambda\|_i < \infty\}$ and $\mathcal{D}^\flat = \prod_{i=1}^m \mathcal{D}_i^\flat$ equipped with the product norm, which we denote with $\|\cdot\|$. The following lemma establishes that the space of measures on $S_i$ can be embedded into the normed space $\mathcal{D}_i^\flat$.

**LEMMA 2.6.** *Every finite signed Borel measure $\mu$ on the compact set $S_i$ has a finite weighted norm, namely $\|\mu\|_i \le \sup_{\alpha} \frac{R_i^{\alpha}}{\alpha!} \mu(S_i)$ for $R_i > 0$ such that $S_i \subset B_{R_i}(\mathbb{R}^{n_i})$. That is,*

$$\mathcal{M}(S_i) \subset \mathcal{D}_i^\flat.$$

*Proof.* By the Jordan decomposition, any signed measure $\mu \in \mathcal{M}(S_i)$ can be written as $\mu = \mu_+ - \mu_-$ where $\mu_+, \mu_- \in \mathcal{M}_+(S_i)$. By the triangle inequality for the norm, if we can show that $\mathcal{M}_+(S_i) \subset \mathcal{D}_i^\flat$, the result will follow. Let $\mu \in \mathcal{M}_+(S_i)$. Since $S_i$ is compact, $\forall x \in S_i$, $|x^\alpha| \le R^{|\alpha|}$ for some $R > 0$, implying $|\mu(\mathbf{x}_i^\alpha)| \le R^{|\alpha|}\mu(S_i)$, where $|\alpha| \stackrel{\text{def}}{=} \sum_{i=1}^{n_i} \alpha_i$. Then $\|\mu\|_i = \sup_\alpha |\mu(\mathbf{x}_i^\alpha)|/\alpha! \le \sup_\alpha R^{|\alpha|}\mu(S_i)/\alpha! < \infty$, so $\mu \in \mathcal{D}_i^\flat$. □
Let the norm of the dual space $(\mathcal{D}_i^b)^*$ be given by the standard operator norm

$$ \|f\|_i^* \stackrel{\text{def}}{=} \sup\{|f(\lambda)|/\|\lambda\|_i : \lambda \in \mathcal{D}_i^b, \lambda \neq 0\}. $$

We present now a characterization of the dual space $(\mathcal{D}_i^b)^*$ that we will need hereafter. Let $A$ be the space of real-analytic functions $f = \sum_{\alpha \in \mathbb{N}^{n_i}} f_\alpha x^\alpha$ equipped with the norm $\|f\|_A \stackrel{\text{def}}{=} \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f_\alpha|$. Define the mapping $\varphi : (\mathcal{D}_i^b)^* \to A$ by

$$ \varphi(f)(\boldsymbol{x}) \stackrel{\text{def}}{=} \sum_{\alpha \in \mathbb{N}^{n_i}} f(\delta_\alpha) \boldsymbol{x}^\alpha. $$

The following classical lemma establishes that the mapping $\varphi$ is an isometric isomorphism:

**LEMMA 2.7.** The space $(\mathcal{D}_i^b)^*$ equipped with the norm $\|\cdot\|_i^*$ is isometrically isomorphic to the space of real-analytic functions $A$ with norm $\|f\|_A \stackrel{\text{def}}{=} \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f_\alpha|$. For the sake of completeness, we provide its proof in Appendix B.

The isometric isomorphism $\varphi : (\mathcal{D}_i^b)^* \to A$ established above allows us to identify elements in the two spaces. Consequently, we will use $f$ interchangeably to denote both a functional in $(\mathcal{D}_i^b)^*$ and its corresponding analytic function in $A$, noting that the isometry implies their norms are equal, i.e., $\|f\|_A^* = \|f\|_A$.

We define the convex cones $\mathcal{L}_\ell^b(g_i) = \mathcal{L}_\ell(g_i) \cap \mathcal{D}_i^b$, $\mathcal{L}_\ell^b = \prod_{i=1}^m \mathcal{L}_\ell^b(g_i)$ and the corresponding relaxation:

$$ \begin{array}{ll} \mathfrak{p}_\ell^b = & \inf \quad \langle \lambda, f \rangle \\ & \text{s.t.} \quad t^\ell - \langle \lambda, h^\ell \rangle \in K^\ell \\ & \lambda \in \mathcal{L}_\ell^b. \end{array} $$

The feasible set of the primal problem is denoted $L_\ell^b = \{\lambda \in \mathcal{L}_\ell^b | t^\ell - \langle \lambda, h^\ell \rangle \in K^\ell\}$.

**LEMMA 2.8.** For $\ell \ge \text{deg}(f)$, $\mathfrak{p}_\ell^b = \mathfrak{p}_\ell^*$.

*Proof.* Clearly $\mathfrak{p}_\ell^* \le \mathfrak{p}_\ell^b$. Let $(\lambda_k)_{k \in \mathbb{N}}$ be a minimizing sequence in $\mathfrak{p}_\ell^*$ converging to $\lambda^*$. As $\ell \ge \text{deg}(f)$, we have that $\langle \lambda_k^{(\ell)}, f \rangle = \langle \lambda_k, f \rangle$ and, by definition of $h^\ell$, $t - \langle \lambda_k^{(\ell)}, h^\ell \rangle = t - \langle \lambda_k, h^\ell \rangle$ for all $k$. That is, the sequence $\lambda_k^{(\ell)}$ is feasible in $\mathfrak{p}_\ell^b$, belongs to $\mathcal{L}_\ell^b$ and achieves the same infimum $\mathfrak{p}_\ell^*$. Thus $\mathfrak{p}_\ell^b \le \mathfrak{p}_\ell^* \le \mathfrak{p}_\ell^b$, as required. $\square$

**Remark 2.9.** For any optimizer $\lambda_\ell^*$ of $\mathfrak{p}_\ell^*$, its $\ell$-truncation $\lambda_\ell^{*}(\ell)$ is also optimal in $\mathfrak{p}_\ell^*$. We thus refer to such optimizers satisfying $\lambda_\ell^* = \lambda_\ell^{*}(\ell)$ as *canonical*.

Denoting the distance associated to the product norm $\|\cdot\|$ as $\rho$, we can define the “distance” $\rho(\mu, \Gamma)$ between $\mu \in \mathcal{D}^b$ and $\Gamma \subset \mathcal{D}^b$ and the Hausdorff distance $\rho_H(\Gamma_1, \Gamma_2)$ between $\Gamma_1 \subset \mathcal{D}^b$ and $\Gamma_2 \subset \mathcal{D}^b$ as follows:

$$ (2.14) \quad \rho(\mu, \Gamma) \stackrel{\text{def}}{=} \inf_{\mu' \in \Gamma} \rho(\mu, \mu'), \quad \rho_H(\Gamma_1, \Gamma_2) \stackrel{\text{def}}{=} \max\{\sup_{\mu \in \Gamma_1} \rho(\mu, \Gamma_2), \sup_{\mu \in \Gamma_2} \rho(\mu, \Gamma_1)\}. $$

**LEMMA 2.10.** Assume the value of $\mathfrak{p}_\ell^*$ is attained for any $f \in \mathcal{R}$. Let $k \in \mathbb{N}$. For any $c \ge 0$ and any $\ell \ge k$, the following equivalence holds:

$$ (\forall f \in \mathcal{R}_k \text{ with } \|f\|_A = 1, 0 \le \mathfrak{p}^* - \mathfrak{p}_\ell^* \le c) \iff \rho_H(\mathcal{F}^{(k)}, L_\ell^{(k)}) \le c, $$

where $\mathcal{F}^{(k)} \stackrel{\text{def}}{=} \{\lambda^{(k)} | \lambda \in \mathcal{F}\}$ and $L_\ell^{(k)} \stackrel{\text{def}}{=} \{\lambda^{(k)} | \lambda \in L_\ell^b\}$ are the sets of moment sequences truncated to degree $k$.
Proof. We first prove the backward direction (=$\Leftarrow$). Assume $\rho_H(\mathcal{F}^{(k)}, L_\ell^{(k)}) \le c$ for some $\ell \ge k$. Let $f \in \mathcal{R}_k$ with $\|f\|_A = 1$. Since $\mathcal{F} \subseteq L_\ell^b$, it follows that $\mathcal{F}^{(k)} \subseteq L_\ell^{(k)}$ and that $\mathfrak{p}_\ell^* \le \mathfrak{p}^*$. Let $\lambda_\ell^*$ be an optimizer for $\mathfrak{p}_\ell^*$, which exists by assumption. Its truncation $\lambda_\ell^{*(k)}$ lies in $L_\ell^{(k)}$. The fact $\rho_H(\mathcal{F}^{(k)}, L_\ell^{(k)}) \le c$ implies the existence of a $\lambda \in \mathcal{F}$ such that its truncation $\lambda^{(k)}$ satisfies $\|\lambda_\ell^{*(k)} - \lambda^{(k)}\| \le c$. Since $\deg(f) = k$, we have $\langle f, \mu \rangle = \langle f, \mu^{(k)} \rangle$ for any measure $\mu$. We can write

$$ \begin{aligned} \mathfrak{p}_\ell^* &= \langle f, \lambda_\ell^* \rangle = \langle f, \lambda_\ell^{*(k)} \rangle = \langle f, \lambda^{(k)} \rangle + \langle f, \lambda_\ell^{*(k)} - \lambda^{(k)} \rangle \\ &= \langle f, \lambda \rangle + \langle f, \lambda_\ell^{*(k)} - \lambda^{(k)} \rangle. \end{aligned} $$

By definition, $\langle f, \lambda \rangle \ge \mathfrak{p}^*$. The second term is bounded using the dual norm. Let $f$ also denote the linear functional in $(\mathcal{D}^b)^*$ corresponding to the polynomial $f \in A$. By the isometry in Lemma 2.7, $\|f\|^* = \|f\|_A$, implying

$$ \langle f, \lambda_\ell^{*(k)} - \lambda^{(k)} \rangle \ge - \left| \langle f, \lambda_\ell^{*(k)} - \lambda^{(k)} \rangle \right| \ge - \|f\|^* \cdot \| \lambda_\ell^{*(k)} - \lambda^{(k)} \| \ge -c. $$

Combining the equations gives $\mathfrak{p}_\ell^* \ge \mathfrak{p}^* - c$, which implies $\mathfrak{p}^* - \mathfrak{p}_\ell^* \le c$, as required. We now prove the forward direction ($\Rightarrow$) by contradiction. Assume that for any $f \in \mathcal{R}_k$ with $\|f\|_A = 1$, we have $0 \le \mathfrak{p}^* - \mathfrak{p}_\ell^* \le c$ for any $\ell \ge k$. Suppose, for the sake of contradiction, that $\rho_H(\mathcal{F}^{(k)}, L_\ell^{(k)}) > c$. This implies that there exists a $\lambda_0' \in L_\ell^b$ whose truncation $\lambda_0'^{(k)}$ is not in the set $\mathcal{F}^{(k)} + B_c(\mathcal{D}^{(k)})$, where $\mathcal{D}^{(k)}$ is the space of moment sequences up to degree $k$, and $B_c(\mathcal{D}^{(k)})$ the closed ball of radius $c$ in $\mathcal{D}^{(k)}$. The sets $\{\lambda_0'^{(k)}\}$ and $\mathcal{F}^{(k)} + B_c(\mathcal{D}^{(k)})$ are disjoint, compact and convex. Thus, they can be strictly separated by the separation theorem (see, e.g., [38, p. 59]). There exists an element $q$ from the dual space of $\mathcal{D}^{(k)}$, such that

$$ \min_{\lambda \in \mathcal{F}^{(k)} + B_c(\mathcal{D}^{(k)})} \langle \lambda, q \rangle - \langle \lambda_0'^{(k)}, q \rangle = \beta > 0. $$

As a dual element to the space of truncated moment sequences, $q$ can be identified with a polynomial in $\mathcal{R}_k$. Note that

$$ \begin{aligned} \min_{\lambda \in \mathcal{F}^{(k)} + B_c(\mathcal{D}^{(k)})} \langle \lambda, q \rangle &= \min_{\lambda' \in \mathcal{F}^{(k)}} \langle \lambda', q \rangle + \min_{\lambda'' \in B_c(\mathcal{D}^{(k)})} \langle \lambda'', q \rangle. \\ &= \min_{\lambda' \in \mathcal{F}^{(k)}} \langle \lambda', q \rangle - c \max_{\|\lambda''\|=1} \langle \lambda'', q \rangle. \\ &= \min_{\lambda' \in \mathcal{F}^{(k)}} \langle \lambda', q \rangle - c \|q\|^*. \end{aligned} $$

Considering the problems $\mathfrak{p}^*$ and $\mathfrak{p}_\ell^*$ with objective $f = q/\|q\|_A$. We obtain

$$ \mathfrak{p}^* - c > \mathfrak{p}_\ell^*, $$

that is

$$ \mathfrak{p}^* - \mathfrak{p}_\ell^* > c, $$

a contradiction. $\square$

THEOREM 2.11. Under Assumption 1.3, Assumption 1.9 and Assumption 2.1, for any fixed degree $k \in \mathbb{N}$, with $\ell \ge k$ and $\ell$ satisfying (2.8),

$$ \rho_H(\mathcal{F}^{(k)}, L_\ell^{(k)}) \le \kappa' \ell^{-\theta} $$
where

$$ \kappa' = \max_{i=1,...,m} \left( \frac{t \cdot w}{(h_i \cdot w)_{\min}} \gamma_i^{\theta_i} (2C_{S_i} + \|v^*\|_1 h_{i,\max}) \right), $$

and $C_{S_i} = \sup_{\alpha \in \mathbb{N}^{n_i}} (\max_{x \in S_i} |x^\alpha|)/\alpha!$ is a constant depending on the set $S_i$. The other constants $\theta, \gamma_i, L_i, w, v^*, h_{i,\max}$ are as in Theorem 2.4.

*Proof.* Take an objective function $f \in \mathcal{R}_k$ such that $\|f\|_A = 1$. To apply Theorem 2.4, we need a uniform bound on $f_{i,\max}$. By triangle inequality and re-arranging terms, we have:

$$ \begin{aligned} f_{i,\max} \le \|f_i\|_{\infty} &\le \sum_{\alpha} |f_{i,\alpha}| (\max_{x \in S_i} |x^\alpha|) \\ &= \sum_{\alpha} (\alpha! |f_{i,\alpha}|) \frac{\max_{x \in S_i} |x^\alpha|}{\alpha!} \\ &\le \left( \sum_{\alpha} \alpha! |f_{i,\alpha}| \right) \sup_{\beta \in \mathbb{N}^{n_i}} \left( \frac{\max_{x \in S_i} |x^\beta|}{\beta!} \right) = C_{S_i} \|f_i\|_A. \end{aligned} $$

Since the total norm is $\|f\|_A = \sum_{j=1}^m \|f_j\|_A = 1$, the individual norms $\|f_i\|_A$ are at most 1. This gives the uniform bound $f_{i,\max} \le C_{S_i}$. Substituting this bound into the result of Theorem 2.4, we obtain

$$ 0 \le \mathbf{p}^* - \mathbf{p}_\ell^* \le \kappa' \ell^{-\theta} $$

which, by Lemma 2.10, implies the result

<figure><img src="image_2.png" /></figure>

The above result demonstrates that the cone of pseudo-moments $L_\ell^{(k)}$ converges to the cone of truncated moments of measures $\mathcal{F}^{(k)}$ with the same rate of convergence, $\theta$, as the optima, as $\ell \to \infty$ with $k$ is fixed. That is, the pseudo-moments up to order $k$ of an optimum solution of the GMP $\mathbf{p}_\ell^*$ are close to the moments of a measure for large enough $\ell$.

We lastly establish the convergence of the optimizers of $\mathbf{p}_\ell^*$ to the optimizer of $\mathbf{p}^*$. Under the assumption that $\mathbf{p}^*$ has a unique minimizer $\mu^*$, we show that sequences of canonical optimizers $(\lambda_\ell^*)$ (see Remark 2.9) converges to $\mu^*$ in the weak* topology. We require the following boundedness lemma.

**LEMMA 2.12.** Let Assumptions 1.3 and 2.1 be satisfied. Let $(\lambda_\ell^*)$ be a sequence of canonical optimizers for the truncated problems $(\mathbf{p}_\ell^*)$. The sequence is uniformly bounded. That is, there exists a constant $\rho > 0$ such that $\|\lambda_\ell^*\| \le \rho$ for all $\ell$.

*Proof.* Let us first prove that $\mathcal{F} \subset B_\rho(\mathcal{D}^b)$ for some $\rho > 0$. Let $\mu \in \mathcal{F}$. By Lemma 2.6 and (A.2) in the proof of Lemma 1.4, and with $R$ such that $S_i \subset B_R(\mathbb{R}^{n_i})$, we have

$$ \|\mu\| \le \sup_{\alpha!} \frac{R^{|\alpha|}}{\alpha!} \sum_i \langle \mu_i, 1 \rangle = \sup_{\alpha!} \frac{R^{|\alpha|}}{\alpha!} \frac{t \cdot \omega}{b_{\min}} \stackrel{\text{def}}{=} \rho'. $$

Consider now its $k$-truncation, $\mu^{(k)}$. By definition,

$$ (2.15) \qquad \|\mu^{(k)}\| = \sup_{\alpha} \frac{|\langle \mu^{(k)}, \mathbf{x}^\alpha \rangle|}{\alpha!} \le \sup_{\alpha} \frac{|\langle \mu, \mathbf{x}^\alpha \rangle|}{\alpha!} = \|\mu\| \le \rho'. $$

Thus, for any $k \in \mathbb{N}$, the set $\mathcal{F}^{(k)}$ is also contained in the same ball $B_{\rho'}(\mathcal{D}^b)$.
Let $\bar{\ell}$ be the minimum $\ell$ such that Theorem 2.11 holds. By Theorem 2.11 with $k = \ell \ge \bar{\ell}$, we have

$$ \rho_H(\mathcal{F}^{(\ell)}, L_{\ell}^{(\ell)}) \le \kappa' \ell^{-\theta}. $$

By definition of the Hausdorff distance,

$$ \min_{\mu \in \mathcal{F}^{(\ell)}} \|\lambda_{\ell}^* - \mu\| \le \kappa' \ell^{-\theta}. $$

By the weak* compactness of $\mathcal{F}$ and the continuity of its truncation to $\mathcal{F}^{(k)}$, there exists an element $\mu_{\ell} \in \mathcal{F}^{(\ell)}$ such that $\|\lambda_{\ell}^* - \mu_{\ell}\| \le \kappa' \ell^{-\theta}$. By (2.15) and triangle inequality, we have

$$ \|\lambda_{\ell}^*\| \le \|\lambda_{\ell}^* - \mu_{\ell}\| + \|\mu_{\ell}\| \le \kappa' \ell^{-\theta} + \rho' \le \bar{\ell}^{-\theta} + \rho' \stackrel{\text{def}}{=} \rho''. $$

since the term $\ell^{-\theta}$ is decreasing with $\ell > 0$. Thus, the entire sequence of optimizers $(\lambda_{\ell}^*)_\ell$ is contained in $B_\rho(\mathcal{D}^\nu)$ where $\rho = \max\{\|\lambda_1^*\|, \|\lambda_2^*\|, \dots, \|\lambda_{\ell-1}^*\|, \rho''\}$. $\square$

We can now prove the optimizer convergence theorem.

**THEOREM 2.13.** Let Assumptions 1.3, 1.9, and 2.1 be satisfied. Assume that problem $\mathbf{p}^*$ has a unique minimizer $\mu^* \in \mathcal{F}$. Let $(\lambda_{\ell}^*)$ be a sequence of canonical optimizers for the truncated problems $(\mathbf{p}_{\ell}^*)$. Then, the sequence $(\lambda_{\ell}^*)$ converges to $\mu^*$ in the weak* topology.

*Proof.* The proof is in three parts.

1. Existence of a convergent subsequence of $(\lambda_{\ell}^*)$. By Lemma 2.12 and the Banach-Alaoglu theorem, the sequence of optimizers $(\lambda_{\ell}^*)$ is contained within a weak* compact ball $B_\rho(\mathcal{D}^\nu)$. Therefore, there exists a subsequence, which we re-index as $(\lambda_{\ell}^*)$, and a limit point $\tilde{\mu} \in B_\rho(\mathcal{D}^\nu)$ such that $\lambda_{\ell}^* \xrightarrow{w^*} \tilde{\mu}$.

2. Feasibility and optimality of $\lambda_{\ell}^*$ in (2.2). To show $\tilde{\mu} \in \mathcal{L}$, let $q \in \mathcal{Q}(g_i)$. For $\ell \ge \text{deg}(q)$, the feasibility of $\lambda_{\ell,i}^*$ implies $\langle \lambda_{\ell,i}^*, q \rangle \ge 0$. By weak* convergence, the limit is non-negative:

$$ \lim_{\ell \to \infty} \langle \lambda_{\ell,i}^*, q \rangle = \langle \tilde{\mu}_i, q \rangle \ge 0. $$

Since $q$ was arbitrary, we have $\tilde{\mu}_i \in \mathcal{L}(g_i)$, and thus $\tilde{\mu} \in \mathcal{L}$.

To show $t - \langle \tilde{\mu}, h \rangle \in K$, note that the feasibility $\lambda_{\ell}^*$ implies that $t^\ell - \langle \lambda_{\ell}^*, h^\ell \rangle \in K^\ell$. By definition of $K^\ell$, there exists $z_\ell \in K$ such that $z_{\ell,j} = t_j - \langle \lambda_{\ell}^*, h_j \rangle$ for all $j \in J_\ell$. For a fixed $j \in J$ we have by the weak* convergence of $\lambda_{\ell}^*$ that

$$ \lim_{\ell \to \infty} z_{\ell,j} = \lim_{\ell \to \infty} t_j - \langle \lambda_{\ell}^*, h_j \rangle = t_j - \langle \tilde{\mu}, h_j \rangle $$

Since this holds for any $j \in J$, $(z_\ell)$ converges to $t - \langle \tilde{\mu}, h \rangle$ in the product topology. The result follows by the closure property of $K$.

Finally, to show optimality, note that from Corollary 2.5, we have $\lim_{\ell \to \infty} \mathbf{p}_{\ell}^* = \mathbf{p}^*$. By definition, $\mathbf{p}_{\ell}^* = \langle \lambda_{\ell}^*, f \rangle$. Taking the limit along a convergent subsequence, we have

$$ \langle \tilde{\mu}, f \rangle = \lim_{\ell \to \infty} \langle \lambda_{\ell}^*, f \rangle = \lim_{\ell \to \infty} \mathbf{p}_{\ell}^* = \mathbf{p}^*. $$

Since $\tilde{\mu}$ is feasible and attains the minimum, it is optimal.

3. **Convergence of the full sequence.** We have shown that the sequence $(\lambda_{\ell}^*)$ lies in a compact set and that any of its limits must be a minimizer of $\mathbf{p}^*$. The minimizer is unique by assumption, so the sequence has only one limit point: $\mu^*$. Therefore, the entire sequence $(\lambda_{\ell}^*)$ converges to $\mu^*$. $\square$
**3. Application to symmetric tensor decomposition.** The tensor decomposition problem consists in decomposing a tensor of order $d$ into a weighted sum of a minimal number of tensor products of $d$ vectors. When the tensor is symmetric (i.e. invariant by permutation of the indices), the symmetric decomposition is the weighted sum of a minimal number of tensor products of the same vector. This can be cast into a generalized moment problem on polynomials as follows.

We identify symmetric tensors $F \in S^d(\mathbb{R}^{n+1})$ of order $d$, with polynomials of degree $\le d$ in $n$ variables: $F(x_1, \dots, x_n) = F(\mathbf{x}) = \sum_{|\alpha| \le d} F_\alpha \mathbf{x}^\alpha$ where $F_\alpha$ are the coefficients of the symmetric tensor $F$ in the basis $(e_0^{d-|\alpha|} e_1^{\alpha_1} \cdots e_n^{\alpha_n})_{|\alpha| \le d}$ of $S^d(\mathbb{R}^{n+1})$ and $(e_0, e_1, \dots, e_n)$ is the canonical basis of $\mathbb{R}^{n+1}$.

Decomposing the symmetric tensor $F$ consists in writing $F(\mathbf{x})$ as a weighted sum of a minimal number $r$ of $d^{\text{th}}$ power of degree-1 polynomials:

$$F(\mathbf{x}) = \sum_{i=1}^{r} \omega_i (\xi_{i,0} + \xi_{i,1}x_1 + \cdots + \xi_{i,n}x_n)^d$$

with $\omega_i, \xi_{i,j} \in \mathbb{R}$. Hereafter, we are considering decompositions with $\xi_{i,0} \ne 0$ (which we can achieve by a generic change of coordinates in $\mathbb{R}^{n+1}$). By scaling, we can then assume that $\xi_{i,0} = 1$ and the decomposition we are considering is of the form

$$(3.1) \qquad F(\mathbf{x}) = \sum_{i=1}^{r} \omega_i (1 + \langle \xi_i, \mathbf{x} \rangle)^d$$

with $\omega_i \in \mathbb{R}$, $\xi_i = (\xi_{i,1}, \dots, \xi_{i,n}) \in \mathbb{R}^n$. Since the points $\xi_i$ of such a decomposition are inherently bounded, we, without loss of generality, rescale the problem so that they lie on the unit ball: $S = \{x \in \mathbb{R}^n | 1 - \|x\|^2 \ge 0\}$.

To transform the tensor decomposition problem into a moment problem, we introduce the apolar product: $\forall f = \sum_{|\alpha| \le d} f_\alpha \mathbf{x}^\alpha, g = \sum_{|\alpha| \le d} g_\alpha \mathbf{x}^\alpha \in \mathcal{R}_{\le d}$,

$$\langle f, g \rangle_d = \sum_{|\alpha| \le d} \binom{d}{\alpha}^{-1} f_\alpha g_\alpha$$

with $\binom{d}{\alpha} = \frac{d!}{(d-|\alpha|)!\alpha_1!\cdots\alpha_n!}$. We directly verify that $\forall g \in \mathcal{R}_{\le d}, \forall \xi \in \mathbb{R}^n$,

$$(3.2) \qquad \langle (1 + \langle \xi, \mathbf{x} \rangle)^d, g \rangle_d = \langle \delta_\xi, g \rangle = g(\xi)$$

where $\delta_\xi \in \mathcal{M}(S)$ is the Dirac measure at $\xi \in S$.

Therefore, $F$ has a decomposition of the form (3.1) if and only if $\Lambda_F : p \in \mathcal{R}_{\le d} \mapsto \langle F, p \rangle_d \in \mathbb{R}$ coincides with $\mu = \sum_{i=1}^r \omega_i \delta_{\xi_i}$ on $\mathcal{R}_{\le d}$.

**3.1. Positive symmetric tensor decomposition.** We consider first the case where $F$ admits a positive decomposition of the form

$$(3.3) \qquad F(\mathbf{x}) = \sum_{i=1}^{r} \omega_i (1 + \langle \xi_i, \mathbf{x} \rangle)^d \quad \text{with } \omega_i \in \mathbb{R}_+ \text{ and } \xi_i \in S \subset \mathbb{R}^n.$$

Here, we are searching for a positive measure $\mu = \sum_{i=1}^r \omega_i \delta_{\xi_i} \in \mathcal{M}_+(S)$, which satisfies

$$\langle \mu, \mathbf{x}^\alpha \rangle = \langle F, \mathbf{x}^\alpha \rangle_d = \binom{d}{\alpha}^{-1} F_\alpha \quad \text{for } |\alpha| \le d,$$
where $\binom{d}{\alpha} = \frac{d!}{(d-|\alpha|)!|\alpha_1|!\cdots|\alpha_n|}$. This yields a positive decomposition of $F$, which can be reformulated into the following.

**Generalized Moment Problem for Positive Symmetric Tensor Decomposition:** For $F = \sum_{|\alpha| \le d} F_\alpha x^\alpha$, solve the optimization problem

$$ \begin{array}{ll} \text{argmin} & \sharp(\mu) \\ \text{s.t.} & \langle \mu, x^\alpha \rangle = \binom{d}{\alpha}^{-1} F_\alpha \quad \text{for } |\alpha| \le d, \\ & \mu \in \mathcal{M}_+(S) \end{array} \tag{3.4} $$

where $\sharp(\mu)$ is the number of points in the support of $\mu$. Since this objective function is hard to compute, we relax it into a linear cost function $\langle \mu, \Psi \rangle$ where $\Psi \in \Sigma_{2d'}^2$ with $2d' > d$, which aims to encourage solutions where the underlying measure has small total mass, heuristically encouraging a low-rank decomposition. If we take $\Psi = \sum_{|\alpha| \le d'} x^{2\alpha}$, we can check that $\langle \lambda, \Psi \rangle$ is the nuclear norm (or sum of the singular values, or trace) of the semi-definite moment matrix $H_\lambda^{d',d'}$ of $\lambda$ in degree $(d', d')$. The nuclear norm is a well-known heuristic objective in the matrix rank minimization community [15]. It has been observed to produce low-rank solutions in practice, and induce an exact relaxation under the restricted isometry property [35].

The resulting primal generalized moment problem reads

$$ \begin{array}{ll} \min & \langle \lambda, \Psi \rangle \\ \text{s.t.} & \langle \lambda, x^\alpha \rangle = \binom{d}{\alpha}^{-1} F_\alpha \quad \text{for } |\alpha| \le d, \\ & \lambda \in \mathcal{M}_+(S). \end{array} \tag{3.5} $$

This program will be relaxed into a hierarchy of finite-dimensional pseudo-moment convex optimization programs denoted $(3.5)_\ell$, replacing the constraint $\lambda \in \mathcal{M}_+(S)$ by $\lambda \in \mathcal{L}_\ell(S)$ for $\ell \ge 2d'$. The existence of a solution of the GMP is guaranteed by the existence of the decomposition (3.3).

The dual problem of (3.5) is written in terms of polynomials as

$$ \begin{array}{ll} \sup & \langle F, V \rangle_d \\ \text{s.t.} & V \in \mathcal{R}_{\le d}, \\ & \Psi - V \in \mathcal{P}\text{os}(S) \end{array} \tag{3.6} $$

where $V = \sum_{|\alpha| \le d} v_\alpha x^\alpha$ is the polynomial associated with the dual variables $v_\alpha$ and $\mathcal{P}\text{os}(S)$ is the cone of polynomials, which are non-negative on $S$. By the property (3.2) of the apolar product, we have $\langle F, V \rangle_d = \sum_{i=1}^r \omega_i V(\xi_i)$.

**PROPOSITION 3.1.** Let $I_\xi = \{p \in \mathcal{R} \mid p(\xi_i) = 0 \text{ for } i = 1, \dots, r\}$ be the vanishing ideal of the points $\xi_i$ of the decomposition (3.3). Assume that $\mathcal{R}_{\le d}$ contains a basis $B$ of $\mathcal{R}/I_\xi$. Then Assumption 1.3 (S-fullness) and Assumption 1.9 ((3.6) attains its supremum) are satisfied.

*Proof.* The S-fullness Assumption 1.3 is satisfied since $1 = x^0 > 0$ on $S$. By Lemma 1.4 and Proposition 1.8, the values of (3.5) and (3.6) are equal. We consider the subproblem

$$ \begin{array}{ll} \sup & \langle F, V \rangle_d \\ \text{s.t.} & V \in \langle B \rangle, \Psi - V \in \mathcal{P}\text{os}(S) \end{array} \tag{3.7} $$
which is bounded by $\mathfrak{d}^*$. Assume, for contradiction, that an optimizing sequence $(V_k)$ for this subproblem is not bounded, i.e., $\|V_k\| \to \infty$ (where $\|\cdot\|$ is the apolar norm). Let $\tilde{V}_k = V_k/\|V_k\|$, so $\|\tilde{V}_k\| = 1$. By the Bolzano-Weierstrass theorem, there exists a convergent subsequence (re-indexed as $\tilde{V}_k$) such that $\tilde{V}_k \to \tilde{V}$ with $\|\tilde{V}\| = 1$. Since $\Psi/\|V_k\| - \tilde{V}_k \ge 0$ on $S$ and $\|V_k\| \to \infty$, we have

$$ -\tilde{V} \ge 0 \text{ on } S, \text{ and } \langle F, \tilde{V} \rangle_d = \sum_{i=1}^{r} \omega_i \tilde{V}(\xi_i) = 0. $$

This implies that $\tilde{V}(\xi_i) = 0$ for $i = 1, \dots, r$ and $\tilde{V} \in I_\xi$. As $B$ is a basis of $\mathcal{R}/I_\xi$ and $\tilde{V} \in \langle B \rangle$, we deduce that $\tilde{V} = 0$, contradicting $\|\tilde{V}\| = 1$. Thus, the optimizing sequence $(V_k)$ must be bounded and has a convergent subsequence to $V^*$, which is a maximizer of (3.7).

Then it is also a maximizer of (3.6) since $\mathcal{R}_{\le d} = \langle B \rangle \oplus (I_\xi \cap \mathcal{R}_{\le d})$ and $\forall p \in (I_\xi \cap \mathcal{R}_{\le d}), \langle F, p \rangle_d = \sum_{i=1}^r \omega_i p(\xi_i) = 0$. Consequently, (3.6) attains its supremum at $V^*$. This concludes the proof. $\square$

We deduce the following corollary:

**THEOREM 3.2.** If $S = \{x \in \mathbb{R}^n \mid 1 - \|x\|^2 \ge 0\}$, $F = \sum_{i=1}^r \omega_i(1 + (\xi_i, x))^d$ with $\omega_i \in \mathbb{R}_+$ and $\xi_i \in S$ and the quotient algebra $\Lambda_\xi = \mathcal{R}/I_\xi$ by the vanishing ideal of the points $\xi$ admits a basis in degree $\le d$, then the optima $\mathfrak{p}^*$ (resp. $\mathfrak{p}_\ell^*$) of (3.5) (resp. $(3.5)_\ell$) and the optima $\mathfrak{d}^*$ (resp. $\mathfrak{d}_\ell^*$) of the dual problem (3.6) (resp. $(3.6)_\ell$) are reached, $\mathfrak{p}^* = \mathfrak{d}^*$ and we have, for $\ell$ sufficiently large,

$$ 0 \le \mathfrak{p}^* - \mathfrak{p}_\ell^* \le \mathfrak{d}^* - \mathfrak{d}_\ell^* \le \kappa \ell^{-2}, $$

with

$$ \kappa \le \gamma (2\Psi_{\max} + \|V^*\|_1), $$

$\gamma$ given in Theorem 2.3, Item 4, $V^* = \sum_{|\alpha| \le d} v_\alpha^* x^\alpha$ a maximizer of $\mathfrak{d}^*$, $\|V^*\|_1 = \sum_{|\alpha| \le d} |v_\alpha^*|$ and $\Psi_{\max} = \max_{x \in S} \Psi(x)$.

*Proof.* Since the unit ball $S$ is defined by $1 - \|x\|^2 \ge 0$, the problem satisfies the Archimedean Assumption 2.1 trivially. By Proposition 3.1, Assumption 1.9 and Assumption 1.3 are satisfied. We thus apply Theorem 2.4 with the exponent $\theta = 2$ taken from Theorem 2.3, and the relation $\max_{x \in S} |x^\alpha| \le 1$ for $|\alpha| \le d$ to conclude the proof. $\square$

*Remark 3.3.* In [30, Proposition 3.6], a condition of strict $S$-positivity is used to show the existence of a maximizer of (3.6). It corresponds to the case where the basis $B$ contains the set of all monomials of degree $d$. The condition in Proposition 3.1 is less restrictive, and allows more general decompositions of the form (3.3).

*Remark 3.4.* In the case $\Psi \in \Sigma_{2d'}^2$ is generic (i.e. $\Psi \in \Sigma_{2d'}^2 \setminus \Theta$, for a subset $\Theta \subseteq \Sigma_{2d'}^2$ having zero Lebesgue measure) with $2d' = \ell$, it is possible to prove that there is a unique degree $2d'$ truncated minimizer $(\lambda^*)^{(2d')}$ for $\lambda^* \in \mathcal{L}_\ell(S)$ any minimizer of $(3.5)_\ell$. We use the fact that the set of singular normal vectors of a convex body has a zero Lebesgue measure ([41, Theorem 2.2.11]). See also [30, Proposition 5.2, (i)] for the uniqueness of the optimum for moment sequences of measures truncated in degree $2d'$.

*Example 3.5* ($n = 2, d = 4, r = 4$). We consider the tensor of dimension $n+1 = 3$ and order $d = 4$, corresponding to the derivative with respect to the first variable $x_0$.
of the first example in [10], divided by 5:

$$
\begin{aligned}
F(\mathbf{x}) = & 88518 x_2^4 - 309888 x_1 x_2^3 + 483408 x_1^2 x_2^2 - 165888 x_1^3 x_2 + 166368 x_1^4 \\
& - 23664 x_0 x_2^3 + 66528 x_0 x_1 x_2^2 - 88992 x_0 x_1^2 x_2 - 13824 x_0 x_1^3 \\
& + 4932 x_0^2 x_2^2 - 3456 x_0^2 x_1 x_2 + 7632 x_0^2 x_1^2 \\
& + 144 x_0^3 x_2 - 96 x_0^3 x_1 + 38 x_0^4.
\end{aligned}
$$

We dehomogenize $F$ by substituting $x_0 = 1$ to obtain a polynomial in variables $\mathbf{x} = (x_1, x_2)$. To transform the search space to the unit ball, we take a rescaling factor of 20. We then solve the SDP relaxation $(3.5)_{\ell}$ for the rescaled problem. We set the relaxation order to $\ell = 12$ and use the nuclear norm heuristic as the objective, with $\Psi(\mathbf{x}) = \sum_{|\alpha| \le 6} \mathbf{x}^{2\alpha}$. The problem is solved using the Julia package MomentPolynomialOpt.jl. The solver returns a moment sequence, from which we extract the weights

$$ \omega = \begin{bmatrix} 5.000000920403701 \\ 3.000000015538793 \\ 15.000004556660205 \\ 14.999994501024343 \end{bmatrix} $$

along with the scaled support points $\Xi$:

$$ \Xi = \begin{bmatrix} 1.0 & 1.0 & 1.0 & 1.0 \\ -0.6 & 0.6 & -0.1 & 0.1 \\ -0.15 & -0.65 & 0.15 & 0.15 \end{bmatrix}. $$

By the appropriate re-scaling — multiplication of second and third row of $\Xi$ by 20, and division of $\omega$ by 5 — we observe the same decomposition as in [10, Example 1]. This example also shows that the hierarchy of relaxations (3.5) is (numerically) exact, i.e. it achieves the optimum at a finite order ($\ell = 12$ here) of relaxation. This phenomenon has been observed for polynomial optimization problems, for which regularity or generality assumptions imply the SoS and moment exactness of the relaxation [5, 31, 30]. This example also shows that the polynomial bounds on the rate of convergence of Theorem 2.4 can be pessimistic.

**3.2. Real symmetric tensor decomposition.** Let us consider now the case where $F$ admits a decomposition of the form

$$ (3.8) \qquad F(\mathbf{x}) = \sum_{i=1}^{r} \omega_i (1 + \langle \xi_i, \mathbf{x} \rangle)^d \quad \text{with } \omega_i \in \mathbb{R} \text{ and } \xi_i \in S \subset \mathbb{R}^n. $$

We write $\mu = \mu_+ - \mu_-$ where $\mu_+ = \sum_{\omega_i > 0} \omega_i \delta_{\xi_i} \in \mathcal{M}_+(S)$ and $\mu_- = \sum_{\omega_i < 0} -\omega_i \delta_{\xi_i} \in \mathcal{M}_-(S)$. We obtain the following reformulation of the symmetric tensor decomposition for points in $S = \{x \in \mathbb{R}^n | 1 - \|x\|^2 \ge 0\}$.

**Generalized Moment Problem for Symmetric Tensor Decomposition:** For $F = \sum_{|\alpha| \le d} F_{\alpha} \mathbf{x}^{\alpha}$, solve the optimization problem

$$
\begin{array}{ll}
\underset{\mu_+ + \mu_-}{\operatorname{argmin}} & \#(\mu_+ + \mu_-) \\
(3.9) \qquad \text{s.t.} & \langle [\mu_+, \mu_-], [\mathbf{x}^\alpha, -\mathbf{x}^\alpha] \rangle = \begin{pmatrix} d \\ \alpha \end{pmatrix}^{-1} F_\alpha \quad \text{for } |\alpha| \le d, \\
& [\mu_+, \mu_-] \in \mathcal{M}_+(S)^2.
\end{array}
$$
We replace the objective function by the proxy $\langle \lambda_+, \Psi_+ \rangle + \langle \lambda_-, \Psi_- \rangle$, where $\Psi_+, \Psi_- \in \Sigma_{2d'}^2$ with $2d' > d$. Note that Assumption 1.3 cannot be satisfied, since both $\mathbf{x}^\alpha$ and $-\mathbf{x}^\alpha$ appear as columns in the matrix $h$. To circumvent this, we constrain the total variation:

$$ \langle \lambda_+, 1 \rangle + \langle \lambda_-, 1 \rangle \le L, \quad L \ge 0. $$

This constraint corresponds to having a finite-weight decomposition. We further impose that $L$ satisfies

$$ (3.10) \qquad L > \sum_{i=1}^{r} |\omega_i| > 0 $$

to ensure the feasibility of the underlying measure from (3.8). The resulting primal generalized moment problem reads

$$ \begin{array}{ll} \min & \langle \lambda_+, \Psi_+ \rangle + \langle \lambda_-, \Psi_- \rangle \\ \text{s.t.} & \langle \lambda_+, \mathbf{x}^\alpha \rangle - \langle \lambda_-, \mathbf{x}^\alpha \rangle = \left(\begin{array}{c} d \\ \alpha \end{array}\right)^{-1} F_\alpha \quad \text{for } |\alpha| \le d, \\ & \langle \lambda_+, 1 \rangle + \langle \lambda_-, 1 \rangle \le L, \\ & \lambda_+, \lambda_- \in \mathcal{M}_+(S). \end{array} \tag{3.11} $$

This program will be relaxed into a hierarchy of finite-dimensional convex optimization programs, denoted by $(3.11)_\ell$, by replacing the constraint $\lambda_+, \lambda_- \in \mathcal{M}_+(S)$ by $\lambda_+, \lambda_- \in \mathcal{L}_\ell(S)$ for $\ell \ge 2d'$. The dual problem to (3.11) is written as

$$ \begin{array}{ll} \sup & \langle F, V \rangle_d - Lu \\ \text{s.t.} & \Psi_+ - V + u \in \mathcal{P}\text{os}(S), \\ & \Psi_- + V + u \in \mathcal{P}\text{os}(S), \\ & V \in \mathcal{R}_{\le d}, u \in \mathbb{R}_+. \end{array} \tag{3.12} $$

**PROPOSITION 3.6.** *The supremum in (3.12) is attained.*

*Proof.* We prove this proposition in two steps:

1. **For fixed $u \in \mathbb{R}_+$, the supremum over $V \in \mathcal{R}_{\le d}$ is attained.** Let $u \ge 0$ be fixed, and assume for contradiction that an optimizing sequence $(V_k)$ for the resulting problem is not bounded, that is, $\|V_k\| \to \infty$. Let $\tilde{V}_k = V_k/\|V_k\|$, so $\|\tilde{V}_k\| = 1$. By the Bolzano-Weierstrass theorem, there exists a convergent subsequence (re-indexed as $\tilde{V}_k$) such that $\tilde{V}_k \to \tilde{V}$ with $\|\tilde{V}\| = 1$. The feasibility of $V_k$ implies that the following inequalities hold on $S$:

$$ \Psi_+ - V_k + u \ge 0 \quad \text{and} \quad \Psi_- + V_k + u \ge 0. $$

Dividing by $\|V_k\|$ and letting $k \to \infty$, we obtain

$$ 0 \ge \tilde{V} \ge 0 \quad \text{on } S, $$

since $\Psi_+/\|V_k\| \to 0$ and $\Psi_-/\|V_k\| \to 0$, and $u$ is fixed. Thus, the polynomial $\tilde{V}$ is identically zero on $S$. Since $S$ has a non-empty interior, $\tilde{V}$ must be the zero polynomial. In particular, $\|\tilde{V}\| = 0$, which is in contradiction with $\|\tilde{V}\| = 1$. Therefore, the
optimizing sequence ($V_k$) must be bounded. Consequently, it has a convergent subsequence whose limit is a polynomial $V_u \in \mathbb{R}_{\le d}$ which attains the supremum (3.12) for any fixed $u \in \mathbb{R}_+$.

**2. The optimizing sequence for $u \in \mathbb{R}_+$ is bounded.** Assume for contradiction that an optimizing sequence ($u_k$) $> 0$ is not bounded, that is, $u_k \to \infty$. The feasibility of each pair ($u_k, V_{u_k}$) implies that the following inequalities hold on $S$:

$$ \Psi_+ - V_{u_k} + u_k \ge 0 \quad \text{and} \quad \Psi_- + V_{u_k} + u_k \ge 0. $$

Dividing by $u_k$, we obtain

$$ \Psi_+/u_k + 1 \ge \tilde{V}_k \ge -\Psi_-/u_k - 1, $$

where $\tilde{V}_k = V_{u_k}/u_k$. This shows that $\|\tilde{V}_k\|$ is a bounded sequence with respect to $k$. By the Bolzano-Weierstrass theorem, $(\tilde{V}_k)$ has a convergent subsequence, whose limit is denoted by $\tilde{V}$. Taking $k \to \infty$ along this subsequence, we have

$$ (3.13) \qquad 1 \ge \tilde{V}(x) \ge -1 \quad \forall x \in S. $$

Dividing by $u_k$ and taking $k \to \infty$ in the objective function, we obtain

$$ \langle F, \tilde{V} \rangle_d - L = 0. $$

By properties of the apolar product (3.2), this can also be written as

$$ (3.14) \qquad \sum_{i=1}^{r^+} \omega_i^+ \tilde{V}(\xi_i^+) - \sum_{j=1}^{r_-} \omega_j^- \tilde{V}(\xi_i^-) - L = 0, $$

where $r^+$ and $r^-$ are the number of points $\{\xi_i^+\}_{i=1}^{r^+}$ (resp. $\{\xi_i^-\}_{j=1}^{r^-}$) in the decomposition (3.8) such that $\omega_i = \omega_i^+ > 0$ (resp. $\omega_i = -\omega_i^- < 0$). Combining (3.13) and (3.14), we have

$$ \sum_{i=1}^{r^+} \omega_i^+ + \sum_{j=1}^{r_-} \omega_j^- \ge L. $$

The above is in contradiction with (3.10), thus, the optimizing sequence ($u_k$) must be bounded. Since the boundedness of $u \in \mathbb{R}_+$ enforces the boundedness of $V \in \mathbb{R}_{\le d}$ via the feasibility constraints, the supremum of (3.12) is attained. $\square$

**THEOREM 3.7.** If $S = \{x \in \mathbb{R}^n \mid 1 - \|x\|^2 \ge 0\}$, $F = \sum_{i=1}^r \omega_i(1 + (\xi_i, x))^d$ with $\omega_i \in \mathbb{R}$ and $\xi_i \in S$ and $L > \sum_i |\omega_i|$, then the optima $\mathbf{p}^*$ (resp. $\mathbf{p}^*_\ell$) of (3.11) (resp. (3.11)$_\ell$) and the optima $\mathbf{\delta}^*$ (resp. $\mathbf{\delta}^*_\ell$) of the dual problems (3.12) (resp. (3.12)$_\ell$) are reached, $\mathbf{p}^* = \mathbf{\delta}^*$ and we have, for $\ell$ sufficiently large,

$$ 0 \le \mathbf{p}^* - \mathbf{p}^*_\ell \le \mathbf{\delta}^* - \mathbf{\delta}^*_\ell \le \kappa \ell^{-2}, $$

with

$$ \kappa \le \gamma L (2\Psi_{\max} + \|V^*\|_1 + u^*), $$

$\gamma$ given in Theorem 2.3, Item 4, ($V^*, u^*$) a maximizer of $\mathbf{\delta}^*$, $\Psi_{\max} = \max_{x \in S}\{\Psi_+(x), \Psi_-(x)\}$.
**Proof.** The feasible set of the truncated moment problem is a nonempty (due to (3.8)), compact and convex set. Since $S$ is the unit ball, the problem satisfies the Archimedean condition Assumption 2.1 trivially. Assumption 1.3 ($S$-fullness) is satisfied due to the total variation constraint: choose vector $w$ that is non-zero only on the entry corresponding to this constraint. Assumption 1.9 is satisfied by Proposition 3.6. We thus apply Theorem 2.4 with the exponent $\theta = 2$ taken from Theorem 2.3, and Corollary 2.5 and use the relation $\max_{x \in S} |x^\alpha| \le 1$ for $|\alpha| \le d$ to conclude the proof. □

**Remark 3.8.** One can prove the uniqueness of the truncation $[(\lambda_+^*)(2d'), (\lambda_-^*)(2d')]$ in degree $2d'$ for a minimizer $[\lambda_+^*, \lambda_-^*]$ of (3.11)$_\ell$ for $\Psi_+$, $\Psi_-$ generic in $\Sigma_{2d'}^2$, using that the set of singular normal vectors of the feasibility set of (3.11)$_\ell$ has a zero Lebesgue measure (see [41, Theorem 2.2.11] and Remark 3.4).

**Example 3.9** ($n = 3$, $d = 4$, $r = 7$). In this example, we consider the following symmetric tensor given by

$$ 
\begin{aligned}
F(\mathbf{x}) = & -0.2489979301598193 x_3^4 - 0.5714471586952264 x_2x_3^3 - 0.5050309495726817 x_2^2x_3^2 \\
& + 0.20686591014734546 x_2^3x_3 + 0.35848687448905797 x_2^4 + 0.6290084096294283 x_1x_3^3 \\
& + 1.5863914541246662 x_1x_2x_3^2 + 0.09102584099156069 x_1x_2^2x_3 - 0.7995202943157504 x_1x_2^3 \\
& - 1.000984626080145 x_1^2x_3^2 - 0.7330971731383541 x_1^2x_2x_3 + 0.48952697145340573 x_1^2x_2^2 \\
& + 0.3654972483140739 x_1^3x_3 + 0.04180994666887122 x_1^3x_2 - 0.06496525932745015 x_1^4 \\
& + 0.8614765507794534 x_0x_3^3 + 2.518149761933887 x_0x_2x_3^2 + 0.11198414551091718 x_0x_2^2x_3 \\
& - 1.2824172455614082 x_0x_2^3 - 3.198429373199247 x_0x_1x_2^3 - 2.280206948221652 x_0x_1x_2x_3 \\
& + 1.51085249826687 x_0x_1x_2^2 + 1.8431809395581764 x_0x_1^2x_3 + 0.38190508335832307 x_0x_1^2x_2 \\
& - 0.6712764568310912 x_0x_1^3 - 2.2452396434195863 x_0^2x_3^2 - 1.3839699114386361 x_0^2x_2x_3 \\
& + 1.4125957148603887 x_0^2x_2^2 + 1.4670698710382422 x_0^2x_1x_3 - 0.015953647647009017 x_0^2x_1x_2 \\
& - 0.361365758387135 x_0^2x_1^2 + 1.253344034777953 x_0^3x_3 + 0.11846876725173883 x_0^3x_2 \\
& - 2.1207614308184404 x_0^3x_1 + 0.6141543193928954 x_0^4
\end{aligned}
$$

We dehomogenize $F$ by substituting $x_0 = 1$ to obtain a polynomial in variables $\mathbf{x} = (x_1, x_2, x_3)$. To transform the search space to the unit ball, we take a rescaling factor of 2. We then solve the SDP relaxation (3.5)$_\ell$ for the rescaled problem. We set the relaxation order to $\ell = 12$ and use the nuclear norm heuristic as the objective, with $\Psi(\mathbf{x}) = \sum_{|\alpha| \le 6} \mathbf{x}^{2\alpha}$. Solving the relaxation yields a moment matrix corresponding to a rank-16 decomposition.

However, by the Alexander-Hirschowitz Theorem (see e.g. [11]), tensors of dimension $n+1=4$ and order $d=4$ have a generic rank 9. In fact, this tensor has a rank 7 decomposition, and we locate it exactly by solving (3.5)$_\ell$ augmented with auxiliary constraints, which are introduced presently.

The degree 2 by degree 2 Hankel matrix $H^{2,2}$ also known as (2,2)-catalecticant of $F$ [33], fully determined by the coefficients of the tensor, is

<table><thead><tr><th></th><th>1</th><th>x<sub>3</sub></th><th>x<sub>2</sub></th><th>x<sub>1</sub></th><th>x<sub>1</sub><sup>2</sup></th><th>x<sub>3</sub>x<sub>2</sub></th><th>x<sub>2</sub><sup>2</sup></th><th>x<sub>3</sub>x<sub>1</sub></th><th>x<sub>2</sub>x<sub>1</sub></th><th>x<sub>1</sub><sup>2</sup></th></tr></thead><tbody><tr><th>x<sub>3</sub></th><td>0.614154</td><td>0.313336</td><td>0.0296172</td><td>-0.53019</td><td>-0.374207</td><td>-0.115331</td><td>0.235433</td><td>0.122256</td><td>-0.00132947</td><td>-0.0602276</td></tr><tr><th>x<sub>2</sub></th><td>0.313336</td><td>-0.374207</td><td>-0.115331</td><td>0.122256</td><td>0.215369</td><td>0.209846</td><td>0.00933201</td><td>-0.266536</td><td>-0.0950086</td><td>0.153598</td></tr><tr><th>x<sub>1</sub></th><td>0.0296172</td><td>-0.115331</td><td>0.235433</td><td>-0.00132947</td><td>0.209846</td><td>0.00933201</td><td>-0.320604</td><td>-0.0950086</td><td>0.125904</td><td>0.0318254</td></tr><tr><th>x<sub>1</sub><sup>2</sup></th><td>-0.53019</td><td>0.122256</td><td>-0.00132947</td><td>-0.0602276</td><td>-0.266536</td><td>-0.0950086</td><td>0.125904</td><td>0.153598</td><td>0.0318254</td><td>-0.167819</td></tr><tr><th>x<sub>3</sub>x<sub>2</sub></th><td>-0.374207</td><td>0.215369</td><td>0.209846</td><td>-0.266536</td><td>-0.248998</td><td>-0.142862</td><td>-0.0841718</td><td>0.157252</td><td>0.132199</td><td>-0.166831</td></tr><tr><th>x<sub>2</sub><sup>2</sup></th><td>-0.115331</td><td>0.209846</td><td>0.00933201</td><td>-0.0950086</td><td>-0.142862</td><td>-0.0841718</td><td>0.0517165</td><td>0.132199</td><td>0.00758549</td><td>-0.0610914</td></tr><tr><th>x<sub>3</sub>x<sub>1</sub></th><td>0.235433</td><td>0.00933201</td><td>-0.320604</td><td>0.125904</td><td>-0.0841718</td><td>0.0517165</td><td>0.358487</td><td>0.00758549</td><td>-0.19988</td><td>0.0815878</td></tr><tr><th>x<sub>2</sub>x<sub>1</sub></th><td>0.122256</td><td>-0.266536</td><td>-0.0950086</td><td>0.153598</td><td>0.157252</td><td>0.132199</td><td>0.00758549</td><td>-0.166831</td><td>-0.0610914</td><td>0.0913743</td></tr><tr><th>x<sub>2</sub><sup>2</sup></th><td>-0.00132947</td><td>-0.0950086</td><td>0.125904</td><td>0.0318254</td><td>0.132199</td><td>0.00758549</td><td>-0.19988</td><td>-0.0610914</td><td>0.0815878</td><td>0.0104525</td></tr><tr><th>x<sub>1</sub><sup>2</sup></th><td>-0.0602276</td><td>0.153598</td><td>0.0318254</td><td>-0.167819</td><td>-0.166831</td><td>-0.0610914</td><td>0.0815878</td><td>0.0913743</td><td>0.0104525</td><td>-0.0649653</td></tr></tbody></table>

By (3.8), $F(\mathbf{x}) = \sum_{i=1}^r \omega_i (1 + \langle \xi_i, \mathbf{x} \rangle)^d$ with $\xi_i \in S$, or equivalently, $\mu_F = \sum_{i=1}^r \omega_i \delta_{\xi_i}$.
We verify that a polynomial $q$ of degree $\le 2$, vanishing at $\xi_i$ is in the kernel of $H^{2,2}$:

$$ \forall q' \in \mathcal{R}_{\le 2}, \langle q', H^{2,2}(q) \rangle = \langle \mu_F, q q' \rangle = \sum_{i=1}^{r} \omega_i q(\xi_i) q'(\xi_i) = 0. $$

This implies that $q \in \ker H^{2,2}$.

To constrain the solution of (3.11), assuming that all polynomials in $\ker H^{2,2}$ vanish at $\xi_i^1$, we add the constraints $\langle \lambda_{\pm}, q p \rangle = 0$ for $q \in \ker H^{2,2}$ and $p \in \mathcal{R}_{\ell-d}$. We arrive at the following augmented form:

$$ \begin{array}{ll} \min & \langle \lambda_+, \Psi_+ \rangle + \langle \lambda_-, \Psi_- \rangle \\ \text{s.t.} & \langle \lambda_+, x^\alpha \rangle - \langle \lambda_-, x^\alpha \rangle = \begin{pmatrix} d \\ \alpha \end{pmatrix}^{-1} F_\alpha \quad \text{for } |\alpha| \le d, \\ (3.15) & \langle \lambda_+, q x^\beta \rangle = 0, \quad \forall q \in \ker H^{2,2}, |\beta| \le \ell - 2, \\ & \langle \lambda_-, q x^\beta \rangle = 0, \quad \forall q \in \ker H^{2,2}, |\beta| \le \ell - 2, \\ & \langle \lambda_+, 1 \rangle + \langle \lambda_-, 1 \rangle \le L, \\ & \lambda_+, \lambda_- \in \mathcal{L}_\ell(S). \end{array} $$

for $2d' > d$.

We keep $\Psi_+ = \Psi_- = \sum_{|\alpha| \le 6} x^{2\alpha}$, and $\ell = 12$, and solve the above via Julia package MomentPolynomialOpt.jl. The following vector of weights $\omega$ is retrieved:

$$ \omega = \begin{bmatrix} -0.4424776570254827 \\ -0.8445409705776897 \\ -0.1434193311604589 \\ 0.27399137914217964 \\ 0.38387835648816826 \\ 0.8233082986137222 \\ 0.5634142439124565 \end{bmatrix} $$

along with the scaled support points $\Xi$:

$$ \Xi = \begin{bmatrix} 1.0 & 1.0 & 1.0 & 1.0 & 1.0 & 1.0 & 1.0 \\ 0.637235 & 0.653722 & 0.460376 & 0.517252 & 0.728496 & -0.375355 & 0.457124 \\ -0.727603 & -0.486279 & -0.255616 & -0.0368457 & -0.995796 & 0.0720327 & -0.721705 \\ -0.023974 & -0.74095 & 0.726747 & -0.630254 & -0.253459 & 0.158722 & -0.141105 \end{bmatrix} $$

The reconstructed homogeneous polynomial $\sum_{i=1}^r \omega_i \langle \Xi[i, i], x \rangle^d$ corresponding to $\omega$, $\Xi$ differs from $F$ by $5.418 \times 10^{-7}$ in the apolar norm. We have an exact relaxation at the order $\ell = 12$ up to numerical errors. Similar to the previous example, we observe that the relaxation achieves exactness at a finite order, and that the convergence rate analysis is overly conservative.

**4. Conclusion.** Our primary contributions are twofold: First, we derived explicit polynomial convergence rates for the optimal values of the relaxations to the true optimum of the GMPs with countable moment constraints on vectors of measures, under dual optimum attainment, S-fullness and Archimedean conditions. These rates, detailed in Corollary 2.5, are geometry-adaptive, influenced by the underlying

<footnote n="1">¹This is not always the case. It happens when $d$ is big enough compared to the regularity of the points $\xi_1, \dots, \xi_r$. Specifically, when the Vandermonde $V_k$ in the Hankel-Vandermonde factorization $H^{k,l} = V_k \Delta V_l^T$ has full column rank.</footnote>
semi-algebraic sets through parameters obtained from effective Putinar's Positivstellensätze. Second, we extended this analysis to the convergence of the feasibility sets themselves. Theorem 2.11 provides polynomial rates for the convergence in Hausdorff distance between the cone of truncated moment sequences of positive measures and the cone of pseudo-moments arising from the SoS relaxations.

We also demonstrated the applicability of our framework to minimal rank symmetric tensor decomposition. We formulated this problem as a GMP, validated the dual optimum attainment, S-fullness and Archimedean conditions, consequently deriving explicit error bounds (Theorem 3.2 and Theorem 3.7). While our experiments in Example 3.5 and Example 3.9 show that the convergence rates can be conservative compared to the finite convergence observed in practice, they nonetheless provide valuable worst-case theoretical guarantees.

Promising future research directions include: (i) applying this framework to new domains, such as optimal control; (ii) identifying conditions for the existence of dual optimizers with application-specific a priori bounds; (iii) investigating the gap between the heuristic objective taken in the examples and the true objective; and (iv) characterizing conditions under which moment relaxations exhibit finite convergence at low orders.

## REFERENCES

[1] N. I. AKHIEZER, *The classical moment problem and some related questions in analysis*, SIAM, 2020.

[2] E. J. ANDERSON, *A review of duality theory for linear programming over topological vector spaces*, Journal of mathematical analysis and applications, 97 (1983), pp. 380–392.

[3] R. B. ASH, *Measure, integration, and functional analysis*, Academic Press, 2014.

[4] L. BALDI AND B. MOURRAIN, *On the effective Putinar's Positivstellensatz and moment approximation*, Mathematical Programming, 200 (2023), pp. 71–103, https://doi.org/10.1007/s10107-022-01877-6.

[5] L. BALDI AND B. MOURRAIN, *Exact Moment Representation in Polynomial Optimization*, Journal of Symbolic Computation, (2024), p. 102403, https://doi.org/10.1016/j.jsc.2024.102403.

[6] L. BALDI, B. MOURRAIN, AND A. PARUSIŃSKI, *On Lojasiewicz inequalities and the effective Putinar's positivstellensatz*, Journal of Algebra, 662 (2025), p. 741–767, https://doi.org/10.1016/j.jalgebra.2024.08.022.

[7] L. BALDI AND L. SLOT, *Degree bounds for Putinar's Positivstellensatz on the Hypercube*, SIAM Journal on Applied Algebra and Geometry, 8 (2024), p. 1–25, https://doi.org/10.1137/23m1555430.

[8] N. BOURBAKI, *Topological vector spaces: Chapters 1–5*, Springer Science & Business Media, 2013.

[9] S. BOYD AND L. VANDENBERGHE, *Convex optimization*, Cambridge university press, 2004.

[10] J. BRACHAT, P. COMON, B. MOURRAIN, AND E. TSIGARIDAS, *Symmetric tensor decomposition*, Linear Algebra and its Applications, 433 (2010), pp. 1851–1872.

[11] M. C. BRAMBILLA AND G. OTTAVIANI, *On the Alexander–Hirschowitz theorem*, Journal of Pure and Applied Algebra, 212 (2008), pp. 1229–1251.

[12] R. E. CURTO AND L. A. FIALKOW, *Solution of the Truncated Complex Moment Problem for Flat Data*, vol. 568 of Memoirs of the American Mathematical Society, American Mathematical Society, 1996.

[13] R. E. CURTO AND L. A. FIALKOW, *Truncated $k$-moment problems in several variables*, Journal of Operator Theory, 54 (2005), pp. 189–226.

[14] K. FANG AND H. FAWZI, *The sum-of-squares hierarchy on the sphere and applications in quantum information theory*, Mathematical Programming, 190 (2020), p. 331–360, https://doi.org/10.1007/s10107-020-01537-7.

[15] M. FAZEL, *Matrix rank minimization with applications*, PhD thesis, Stanford University, 2002.

[16] V. GAITSGORY AND S. ROSSOMAKHINE, *Linear programming approach to deterministic long run average problems of optimal control*, SIAM journal on control and optimization, 44 (2006),
pp. 2006–2037.

[17] V. GAITSGORY, S. ROSSOMAKHINE, AND N. THATCHER, *Approximate solution of the HJB in-equality related to the infinite horizon optimal control problem with discounting*, Dynamics of Continuous, Discrete and Impulsive Systems Series B: Applications and Algorithms, 19 (2012), pp. 65–92.

[18] L. HUANG, J. NIE, AND Y.-X. YUAN, *Finite convergence of moment-sos relaxations with nonreal radical ideals*, SIAM Journal on Optimization, 34 (2024), pp. 3399–3428, https://doi.org/10.1137/23M1605430.

[19] E. D. KLERK AND M. LAURENT, *A survey of semidefinite programming approaches to the generalized problem of moments and their error analysis*, in World Women in Mathematics 2018: Proceedings of the First World Meeting for Women in Mathematics (WM) 2, Springer, 2019, pp. 17–56.

[20] T. G. KOLDA AND B. W. BADER, *Tensor decompositions and applications*, SIAM review, 51 (2009), pp. 455–500.

[21] M. KORDA, D. HENRION, AND C. N. JONES, *Convergence rates of moment-sum-of-squares hierarchies for optimal control problems*, Systems & Control Letters, 100 (2017), pp. 1–5.

[22] H. J. LANDAU, *Moments in mathematics*, vol. 37, American Mathematical Soc., 1987.

[23] J. LASSERRE, *The K-moment problem for continuous linear functionals*, Transactions of the American Mathematical Society, 365 (2013), pp. 2489–2504.

[24] J. B. LASSERRE, *Global optimization with polynomials and the problem of moments*, SIAM Journal on optimization, 11 (2001), pp. 796–817.

[25] J. B. LASSERRE, *A semidefinite programming approach to the generalized problem of moments*, Mathematical Programming, 112 (2008), pp. 65–92.

[26] J. B. LASSERRE, *The moment-SOS hierarchy*, in Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, World Scientific, 2018, pp. 3773–3794.

[27] M. LAURENT AND B. MOURRAIN, *A generalized flat extension theorem for moment matrices*, Archiv der Mathematik, 93 (2009), p. 87–98, https://doi.org/10.1007/s00013-009-0007-6.

[28] M. LAURENT AND L. SLOT, *An effective version of Schmüdgen's Positivstellensatz for the hypercube*, Optimization Letters, 17 (2023), pp. 515–530.

[29] B. MOURRAIN AND A. ONETO, *On minimal decompositions of low rank symmetric tensors*, Linear Algebra and its Applications, 607 (2020), pp. 347–377.

[30] J. NIE, *The A-truncated k-moment problem*, Foundations of Computational Mathematics, 14 (2014), p. 1243–1276, https://doi.org/10.1007/s10208-014-9225-9.

[31] J. NIE, *Optimality conditions and finite convergence of Lasserre's hierarchy*, Mathematical Programming, 146 (2014), pp. 97–121.

[32] J. NIE AND M. SCHWEIGHOFER, *On the complexity of Putinar's Positivstellensatz*, Journal of Complexity, 23 (2007), pp. 135–150, https://doi.org/10.1016/j.jco.2006.07.002.

[33] M. PUCCI, *The Veronese variety and catalectic matrices*, Journal of Algebra, 202 (1998), pp. 72–95.

[34] M. PUTINAR, *Positive polynomials on compact semi-algebraic sets*, Indiana University Mathematics Journal, 42 (1993), pp. 969–984.

[35] B. RECHT, M. FAZEL, AND P. A. PARRILO, *Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization*, SIAM review, 52 (2010), pp. 471–501.

[36] R. ROCKAFELLAR, *Convex Analysis*, Princeton Landmarks in Mathematics and Physics, Princeton University Press, 1997.

[37] W. RUDIN, *Real and Complex Analysis*, Mathematics series, McGraw-Hill, 1987.

[38] W. RUDIN, *Functional Analysis*, International series in pure and applied mathematics, McGraw-Hill, 1991.

[39] C. SCHLOSSER, M. TACCHI, AND A. LAZAREV, *Convergence rates for the moment-SoS hierarchy*, preprint arXiv:2402.00436, (2024).

[40] K. SCHMÜDGEN, *The Moment Problem*, Springer International Publishing, 2017, https://doi.org/10.1007/978-3-319-64546-9.

[41] R. SCHNEIDER, *Convex bodies: the Brunn–Minkowski theory*, vol. 151, Cambridge university press, 2013.

[42] M. SCHWEIGHOFER, *On the complexity of Schmüdgen's Positivstellensatz*, Journal of Complexity, 20 (2004), pp. 529–543, https://doi.org/10.1016/j.jco.2004.01.005.

[43] L. SLOT, *Sum-of-squares hierarchies for polynomial optimization and the Christoffel–Darboux Kernel*, SIAM Journal on Optimization, 32 (2022), p. 2612–2635, https://doi.org/10.1137/21m1458338.

[44] M. TACCHI, J. B. LASSERRE, AND D. HENRION, *Stokes, Gibbs, and volume computation of semi-algebraic sets*, Discrete & Computational Geometry, 69 (2023), pp. 260–283.
## Appendix A. Linear programming proofs.

*Proof of Lemma 1.4.* Observe firstly that $\Omega$ is closed in $\mathcal{M}$. Let $\mu_n \xrightarrow{w} \mu$ with $\mu_n \in \Omega$ and $\mu \in \mathcal{M}$. We readily have that

$$ \lim_{n \to \infty} (t - \langle \mu_n, h \rangle) = t - \langle \mu, h \rangle \in K. $$

since $K$ is closed in $\mathbb{R}^J$. Moreover, for any $q \in C_+$, we have $\langle \mu_n, q \rangle \ge 0$, thus $\langle \mu, q \rangle = \lim_{n \to \infty} \langle \mu_n, q \rangle \ge 0$. The previous statements imply $\mu \in \Omega$, and so $\Omega$ is closed.

The Banach-Alaoglu theorem (see e.g. [3, Theorem 3.5.16]) implies that the closed unit ball $B_1(\mathcal{M}(S_i))$ in the space $\mathcal{M}(S_i)$ is weak* compact, as well as the ball $B_\kappa(\mathcal{M}(S_i))$ of radius $\kappa$ by rescaling. By Tychonoff's Theorem, the ball $B_\kappa(\mathcal{M})$ is also weak* compact.

Let $b_{\min} \stackrel{\text{def}}{=} \min_{i=1,...,m}(\min_{x \in S_i} b_i(x)) > 0$, since $b_i > 0$ on $S_i$ and $S_i$ is compact. Then, since $w \in K^*$ and $\mu \in \Omega$, we have $(t - \langle \mu, h \rangle) \cdot w \ge 0$. We deduce that

$$ (A.1) \qquad t \cdot w \ge (\langle \mu, h \rangle) \cdot w = \langle \mu, h \cdot w \rangle = \langle \mu, b \rangle \ge b_{\min} \sum_{i=1}^{m} \langle \mu_i, 1 \rangle $$

This implies that

$$ (A.2) \qquad \sum_{i=1}^{m} \langle \mu_i, 1 \rangle \le \rho \stackrel{\text{def}}{=} \frac{t \cdot w}{b_{\min}}. $$

The operator norm of a nonnegative measure is its mass, so we have $\|\mu\|_\infty \le \rho$, and $\mu \in B_\rho(\mathcal{M})$. We deduce that $\Omega$ is a closed subset of the weak* compact set in $B_\rho(\mathcal{M})$, and is therefore also weak* compact. The fact that the value of $\mathfrak{p}^*$ is attained follows by the extreme value theorem. $\square$

*Proof of Proposition 1.8.* By taking the following series of substitutions, (1.5) can be realized as $-\mathfrak{d}^*$, the problem identical to (1.3) except for the sign of the objective:

$$ 1. \quad v \to x, $$

$$ 5. \quad C_+ \to Q, $$

$$ 2. \quad h \cdot v \to Ax, $$

$$ 6. \quad K^* \to P, $$

$$ 3. \quad t \to c, $$

$$ 7. \quad b \to -f. $$

$$ 4. \quad \sup t \cdot v \to -\inf c \cdot -v, $$

Specifically, we obtain

$$ \begin{array}{l} -\mathfrak{d}^* = \inf t \cdot v \\ \text{s.t.} \quad h \cdot v + f \in C_+, \\ \qquad v \in K^*. \end{array} $$

Since $K$ is closed, $K^{**} = K$ (see e.g. [36, p. 121], [9, p. 53]) and by the Riesz representation theorem $(C_+)^* = M_+$. It is then readily verified with reference to the above substitutions and (1.6) that the dual to the above problem is $-\mathfrak{p}^*$. The weak duality condition is satisfied: $-\mathfrak{d}^* \ge -\mathfrak{p}^*$, and hence by Lemma 1.4, $-\mathfrak{d}^*$ has a finite infimum. To satisfy Condition 1.5, it remains to locate a vector $v_0 \in K^*$ such that $h \cdot v_0 + f$ is in the interior of $C_+$. By Assumption 1.3, there exists $w \in K^*$ such that $b = h \cdot w \ge b_{\min} > 0$. Since $f_i$ is bounded on $S_i$, we can find $\eta \in \mathbb{R}_+$ such that

$$ \eta(h \cdot w)_i + f_i > 0 \quad \forall i = 1, \dots, m, $$
implying that $v_0 = \eta w$ is the required vector. Thus, Condition 1.5 holds for $-\mathfrak{d}^*$, implying $-\mathfrak{d}^* = -\mathfrak{p}^*$, or equivalently, $\mathfrak{d}^* = \mathfrak{p}^*$. $\square$

## Appendix B. Dual of bounded functionals.

**LEMMA B.1.** *The space $(\mathcal{D}_i^b)^*$ equipped with the norm $\|\cdot\|_i^*$ is isometrically isomorphic to the space of real-analytic functions A with norm $\|f\|_A \stackrel{\text{def}}{=} \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f_\alpha|$.*

*Proof.* The result follows readily by verifying the following mapping is an isometric isomorphism:

$$ \varphi : (\mathcal{D}_i^b)^* \to A \\ \varphi(f)(\boldsymbol{x}) \stackrel{\text{def}}{=} \sum_{\alpha \in \mathbb{N}^{n_i}} f(d_\alpha) \boldsymbol{x}^\alpha, $$

where $d_\alpha(\boldsymbol{x}^\beta) = 1$ if $\alpha = \beta$ and 0 otherwise.

1. *Real-analyticity of $\varphi(f)$.* Let $f \in (\mathcal{D}_i^b)^*$. Then

$$ |f(d_\alpha)| \le \|f\|_i^* \|d_\alpha\|_i = \|f\|_i^* \sup_{\beta \in \mathbb{N}^{n_i}} |d_\alpha(\boldsymbol{x}^\beta)|/\beta! = \|f\|_i^*/\alpha!. $$

The absolute value of the $\alpha$-th term in the series of $\varphi(f)$ is $|f(d_\alpha)\boldsymbol{x}^\alpha| = |f(d_\alpha)||\boldsymbol{x}^\alpha| \le (\|f\|_i^*/\alpha!)|\boldsymbol{x}^\alpha|$ and the $\alpha!$ in the denominator ensures convergence. That $\varphi(f)$ also belongs to the space A (i.e., has a finite A-norm) is established by the isometry in point 5.

2. *Linearity.* Let $f, g \in (\mathcal{D}_i^b)^*$ and $a, b \in \mathbb{R}$. The fact $\varphi(af + bg) = a\varphi(f) + b\varphi(g)$ follows readily from the definition of $\varphi$.

3. *Injectivity.* Let $\varphi(f) = \varphi(g)$. By linearity, this is equivalent to showing that if $\varphi(F) = 0$ for $F = f - g$, then $F = 0$. The condition $\varphi(F) = 0$ means that

$$ \sum_{\alpha \in \mathbb{N}^{n_i}} F(d_\alpha) \boldsymbol{x}^\alpha = 0. $$

This implies that all coefficients are zero: $F(d_\alpha) = 0$ for all $\alpha \in \mathbb{N}^{n_i}$. From the definition of the A-norm, this gives $\|\varphi(F)\|_A = \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |F(d_\alpha)| = 0$. The norm-preservation property, established in point 5 below, shows that $\|F\|_i^* = \|\varphi(F)\|_A$. Therefore, $\|F\|_i^* = 0$, implying $F = 0$, and subsequently $f = g$. Thus, $\varphi$ is injective.

4. *Surjectivity.* Let $h = \sum_{\alpha \in \mathbb{N}^{n_i}} h_\alpha \boldsymbol{x}_i^\alpha \in A$. Take

$$ f_h(\lambda) \stackrel{\text{def}}{=} \sum_{\alpha \in \mathbb{N}^{n_i}} h_\alpha \lambda(\boldsymbol{x}_i^\alpha). $$

We verify that $f_h$ is well-defined and continuous. Note that the above series converges absolutely for any $\lambda \in \mathcal{D}_i^b$:

$$ |f_h(\lambda)| \le \sum_{\alpha \in \mathbb{N}^{n_i}} |h_\alpha| \|\lambda(\boldsymbol{x}_i^\alpha)\| \le \sum_{\alpha \in \mathbb{N}^{n_i}} |h_\alpha| (\|\lambda\|_i \alpha!) = \|\lambda\|_i \left( \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |h_\alpha| \right) = \|\lambda\|_i \|h\|_A. $$

This inequality also shows that $f_h$ is a bounded linear functional with $\|f_h\|_i^* \le \|h\|_A$, so $f_h \in (\mathcal{D}_i^b)^*$. We may then apply the definition of $\varphi(\cdot)$:

$$ \varphi(f_h) = \sum_{\alpha \in \mathbb{N}^{n_i}} h_\alpha \boldsymbol{x}_i^\alpha = h, $$

as required.

5. *Norm preservation.* We show:
(a) $\|f\|_i^* \le \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f(d_\alpha)|$,

(b) $\|f\|_i^* \ge \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f(d_\alpha)|$, and

(c) $\|\varphi(f)\|_A = \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f(d_\alpha)|$.

(a) Let $f \in (\mathcal{D}_i^b)^*$ and $\lambda \in \mathcal{D}_i^b$ with $\|\lambda\|_i \le 1$. Then,

$$|\langle f, \lambda \rangle| = \left| \sum_{\alpha \in \mathbb{N}^{n_i}} f(d_\alpha) \lambda(\mathbf{x}_i^\alpha) \right| \le \sum_{\alpha \in \mathbb{N}^{n_i}} |f(d_\alpha)| \|\lambda(\mathbf{x}_i^\alpha)\|.$$

Since $\|\lambda\|_i \le 1$, we have $|\lambda(\mathbf{x}_i^\alpha)| \le \alpha! \|\lambda\|_i \le \alpha!$. Thus,

$$|\langle f, \lambda \rangle| \le \sum_{\alpha \in \mathbb{N}^{n_i}} |f(d_\alpha)| \alpha! = \|\varphi(f)\|_A.$$

Taking the supremum over $\lambda$ with $\|\lambda\|_i \le 1$ yields $\|f\|_i^* \le \|\varphi(f)\|_A$.

(b) Given a non-zero $f$, define $\lambda_N \in \mathcal{D}_i^b$ as the finite sum:

$$\lambda_N \stackrel{\text{def}}{=} \sum_{|\alpha| \le N} \alpha! \operatorname{sgn}(f(d_\alpha)) d_\alpha.$$

The norm of this functional is

$$\|\lambda_N\|_i = \sup_{\beta \in \mathbb{N}^{n_i}} \frac{|\langle \lambda_N, \mathbf{x}_i^\beta \rangle|}{\beta!} = \sup_{|\beta| \le N} \frac{|\beta! \operatorname{sgn}(f(d_\beta))|}{\beta!} = 1.$$

Since $\|\lambda_N\|_i = 1$, by the definition of the operator norm, we have $\|f\|_i^* \ge |f(\lambda_N)|$ for any $N$. Evaluating $|f(\lambda_N)|$ gives

$$|f(\lambda_N)| = \left| \sum_{|\alpha| \le N} \alpha! \operatorname{sgn}(f(d_\alpha)) f(d_\alpha) \right| = \sum_{|\alpha| \le N} \alpha! |f(d_\alpha)|.$$

This inequality holds for all $N$. Taking the limit as $N \to \infty$, we obtain the desired bound:

$$\|f\|_i^* \ge \lim_{N \to \infty} \sum_{|\alpha| \le N} \alpha! |f(d_\alpha)| = \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f(d_\alpha)|.$$

(c) We have

$$\begin{aligned} \|\varphi(f)\|_A &= \| \sum_{\alpha \in \mathbb{N}^{n_i}} f(d_\alpha) \mathbf{x}^\alpha \|_A \\ &= \sum_{\alpha \in \mathbb{N}^{n_i}} \alpha! |f(d_\alpha)|, \end{aligned}$$

as required. Thus, $\varphi$ is an isometric isomorphism. □