Introduction
Global minimization of a multivariate polynomial is a fundamental yet computationally challenging problem, even at relatively low degrees. For instance, minimizing a homogeneous cubic over the Euclidean sphere is NP-hard [19 ] ; testing nonnegativity of quartic polynomials is NP-hard [17 ] ; and even deciding whether a quartic polynomial has a local minimizer is strongly NP-hard [3 ] . Despite these general hardness results, certain polynomial classes admit exact and computationally tractable formulations due to their underlying algebraic structure. This raises a fundamental question: beyond the classical tractable cases, can one identify broader classes of multivariate polynomials whose global minima can be computed and certified exactly?
A classical illustration of such algebraic structure dates back to Hilbert’s celebrated work in 1888. He showed that nonnegative polynomials need not be sums of squares (SoS), and characterized the three classical cases in which the two notions coincide: univariate polynomials of arbitrary degree, quadratic polynomials in any number of variables, and bivariate quartics [14 ] . This distinction has fundamental consequences for global optimization. Indeed, if a polynomial h h h attains its global minimum h ∗ h^* h ∗ , then the shifted polynomial h − h ∗ h-h^* h − h ∗ is nonnegative. When this nonnegative polynomial admits an SoS representation, its global minimum can be computed and certified through semidefinite programming (SDP) [21 , 16 ] . Beyond Hilbert’s classical cases, it is therefore natural to ask whether additional algebraic structure can guarantee SoS exactness and, consequently, exact global minimization by a tractable SDP.
In this paper, we show that sufficiently strong regularization provides precisely such a mechanism. We consider a broad class of multivariate polynomials of arbitrary even degree, obtained by adding a higher-degree Euclidean regularizer to a polynomial of lower degree. Let P P P be an arbitrary multivariate polynomial of degree at most p p p , and let 2 d > p 2d > p 2 d > p be an even integer. We study the regularized polynomial
m σ ( s ) : = P ( s ) + σ 2 d ∥ s ∥ 2 d , σ > 0 , (1) m_{\sigma}(s) := P(s) + \frac{\sigma}{2d}\lVert s\rVert^{2d}, \qquad\sigma> 0, \tag*{(1)} m σ ( s ) := P ( s ) + 2 d σ ∥ s ∥ 2 d , σ > 0 , (1)
where ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ denotes the Euclidean norm. Since the regularization term has higher degree than P P P , m σ m_{\sigma} m σ is coercive and therefore always attains a global minimum. Our main result shows that, under a nonzero linear-term assumption, sufficiently strong regularization makes m σ m_{\sigma} m σ SoS exact, with its unique global minimizer recoverable from a single SDP of polynomial size for every fixed d d d . To be precise, let
s σ ∗ ∈ arg min u ∈ R n m σ ( u ) , m σ ∗ : = m σ ( s σ ∗ ) , q σ : = m σ − m σ ∗ , s_{\sigma}^{*} \in\underset{u\in\mathbb{R}^{n}}{\arg\min}\ m_{\sigma}(u), \qquad m_{\sigma}^{*} := m_{\sigma}(s_{\sigma}^{*}), \qquad q_{\sigma} := m_{\sigma} - m_{\sigma}^{*}, s σ ∗ ∈ u ∈ R n arg min m σ ( u ) , m σ ∗ := m σ ( s σ ∗ ) , q σ := m σ − m σ ∗ ,
where s σ ∗ s_{\sigma}^{*} s σ ∗ denotes a minimizer and m σ ∗ m_{\sigma}^{*} m σ ∗ , its optimal value. The shifted polynomial q σ q_{\sigma} q σ is nonnegative by construction. We say that m σ m_{\sigma} m σ is SoS exact if q σ q_{\sigma} q σ is a sum of squares of polynomials of degree at most d d d . Equivalently, the global minimum m σ ∗ m_{\sigma}^{*} m σ ∗ is attained exactly by a single degree-d d d SoS representation, with no higher-order relaxations required. Furthermore, the SDP recovers not only the exact global minimum but also its unique global minimizer. In particular, the optimal moment matrix has rank one, and the minimizer can be read directly from the moments corresponding to the linear monomials. Our main result can be stated as follows; the precise statements are given in Corollaries 4.2 and 4.3.
Theorem 1.1 (Main result, informal). Let P P P be a polynomial of degree at most p p p with nonzero linear coefficient g : = ∇ P ( 0 ) ≠ 0 g := \nabla P(0) \ne0 g := ∇ P ( 0 ) = 0 , let 2 d > p 2d > p 2 d > p be even, and let m σ m_{\sigma} m σ be defined in (1) . Then there exists a threshold σ ∗ > 0 \sigma^{*} > 0 σ ∗ > 0 such that, for every σ ≥ σ ∗ \sigma\ge\sigma^{*} σ ≥ σ ∗ :
(i) The shifted polynomial m σ − m σ ∗ m_{\sigma} - m_{\sigma}^{*} m σ − m σ ∗ is a sum of squares of polynomials of degree at most d d d . Furthermore, it admits a positive-definite Gram representation on the nonconstant monomials centred at global minimizer s σ ∗ s_{\sigma}^{*} s σ ∗ .
(ii) A single degree-d d d moment SDP attains the exact global minimum and has a unique rank-one optimal moment matrix, from which s σ ∗ s_{\sigma}^{*} s σ ∗ can be recovered directly. For fixed d d d , this SDP has size polynomial in n n n .
The threshold σ ∗ \sigma^{*} σ ∗ is given explicitly in terms of the coefficients of P P P . Numerical evidence in the quartic case suggests that exactness may occur at substantially smaller regularization parameters [26 ] .
The class in (1) arises naturally in higher-order nonlinear optimization, where Taylor models combined with regularization provide a standard globalization mechanism. Any polynomial of degree at most p p p can be written exactly in Taylor form,
P ( s ) = T p ( s ) : = ∑ j = 0 p 1 j ! T j [ s ] j , (2) P(s) = \mathcal{T}_{p}(s) := \sum_{j=0}^{p} \frac{1}{j!} T_j[s]^j, \tag*{(2)} P ( s ) = T p ( s ) := j = 0 ∑ p j ! 1 T j [ s ] j , (2)
where T j T_j T j is a symmetric j j j th-order tensor determined by the coefficients of P P P (see § 2 ). For a Taylor approximation of a smooth function f f f at x x x , we have T j = ∇ j f ( x ) T_j = \nabla^j f(x) T j = ∇ j f ( x ) . The associated regularized model is
m σ ( s ) = T p ( s ) + σ p ′ ∥ s ∥ p ′ , (3) m_{\sigma}(s) = \mathcal{T}_{p}(s) + \frac{\sigma}{p'}\lVert s\rVert^{p'}, \tag*{(3)} m σ ( s ) = T p ( s ) + p ′ σ ∥ s ∥ p ′ , (3)
where σ > 0 \sigma> 0 σ > 0 and our polynomial setting takes the even exponent p ′ = 2 d > p p' = 2d > p p ′ = 2 d > p . Thus the P P P in (1) and the T p \mathcal{T}_p T p here are identical. Beginning with cubic regularization of Newton’s method [20 ] , higher-order adaptive regularization methods have developed a rich convergence and complexity theory [4 , 5 , 6 , 11 ] . Yet the global solution of their polynomial subproblems remains a central computational challenge. Nesterov [18 ] explicitly asked whether tools from algebraic geometry, particularly sums of squares, could be used to minimize such subproblems. Our result provides a positive answer in the sufficiently regularized regime. We also study the complementary trust-region globalization strategy [10 ] , which minimizes the same Taylor polynomial over ∥ s ∥ ≤ Δ \lVert s\rVert\le\Delta ∥ s ∥ ≤ Δ . For sufficiently small radii, we establish a correspondence with the large-regularization regime; see § 5 .
Classically, convexity is one of the principal sources of tractability in optimization [23 ] . We emphasize, however, that our framework does not rely on convexifying the polynomial model. Instead, we retain the regularized Taylor polynomial itself and prove that sufficiently strong Euclidean regularization makes its shifted nonnegative polynomial SoS exact, even when the model remains nonconvex. Thus regularization can do more than provide boundedness or globalization: it can enforce algebraic exactness without requiring convexity. This provides a different route from the SoS-convex higher-order Newton framework of Ahmadi, Chaudhry and Zhang [1 ] . Their approach constructs an SoS-convex polynomial subproblem through suitable corrections and regularization, whereas our result establishes an exact SoS representation for the original regularized model, without assuming convexity or SoS-convexity.
In addition to the result in Theorem 1.1, our contributions reveal three complementary aspects of this algebraic exactness mechanism.
A mechanism linking optimality and algebraic geometry. Our central technical result shows that the Bregman remainder of the Euclidean regularizer admits a positive-definite Gram representation on the full vector of nonconstant monomials. When the regularization is sufficiently large, this strict Gram margin absorbs the remaining Taylor terms, yielding an exact SoS representation of the shifted nonnegative polynomial. This mechanism is distinct from our earlier quartic analysis [26 ] , which relies on identities specific to degree four. The Bregman/strict-Gram argument developed here applies at every even regularization degree and extends to broader classes of regularizers; see § 3.2 . Thus the present result is not merely a higher-degree extension of the quartic case, but a degree-independent approach to establishing SoS exactness.
Small-radius trust-region problems admit exact SDP solutions. The same mechanism governs polynomial optimization over a Euclidean ball. Minimizing a degree-p p p polynomial over ∥ s ∥ ≤ Δ \lVert s\rVert\le\Delta ∥ s ∥ ≤ Δ is a higher-order trust-region subproblem and is NP-hard in general for p ≥ 3 p \ge3 p ≥ 3 [19 ] . In § 5 , we show that when the linear coefficient is nonzero and the radius Δ \Delta Δ is sufficiently small, the global minimizer is unique, lies on the sphere ∥ s ∥ = Δ \lVert s\rVert= \Delta ∥ s ∥ = Δ , and can be recovered exactly from a rank-one solution of a degree-d d d moment relaxation (Proposition 5.2). At an active trust-region solution, the multiplier λ Δ \lambda_{\Delta} λ Δ determines the matched regularization parameter σ = λ Δ / Δ 2 d − 2 \sigma= \lambda_{\Delta}/\Delta^{2d-2} σ = λ Δ / Δ 2 d − 2 . As Δ ↓ 0 \Delta\downarrow0 Δ ↓ 0 , this parameter tends to infinity, connecting small trust regions with the large-regularization regime of our main theorem. The radius threshold is explicit in the tensor norms of the Taylor coefficients. Thus, the two classical globalization strategies share the same algebraic mechanism for SoS exactness.
The choice of regularization matters. The mechanism depends on the algebraic structure of the regularizer, not merely on its strength. Euclidean regularization produces the strict Gram margin underlying our SoS exactness result, whereas other regularizers need not possess this property, regardless of how large the regularization parameter becomes. In § 3.2 , we investigate which regularizers admit such a margin: weighted Euclidean norms and regularizers constructed from spanning families of linear forms inherit the strict Gram property, while coordinate-separable regularization, although coercive and SoS-convex, does not control all mixed monomial directions needed for a full positive-definite Gram representation. This distinction holds across the even regularization degrees considered here. It shows that the choice of regularizer, often treated as a modelling tool, plays a decisive role in the algebraic structure underlying SoS exactness.
Background and Notation. We recall only the basic notions used throughout the paper: SoS polynomials, monomial vectors, Gram representations, and SoS-convexity. Unless stated otherwise, ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ denotes the Euclidean norm.
Definition 1.1 (Sum of squares and Gram representation). Let h ∈ R [ x ] h \in\mathbb{R}[x] h ∈ R [ x ] be a polynomial of degree at most 2 d 2d 2 d . We say that h h h is a sum of squares (SoS) if there exist polynomials h 1 , … , h r h_1,\ldots,h_r h 1 , … , h r of degree at most d d d such that
h ( x ) = ∑ i = 1 r h i ( x ) 2 . h(x)=\sum_{i=1}^{r}h_i(x)^2. h ( x ) = i = 1 ∑ r h i ( x ) 2 . We denote by Σ [ x ] 2 d \Sigma[x]_{2d} Σ [ x ] 2 d the cone of SoS polynomials of degree at most 2 d 2d 2 d . For k ≥ 0 k \ge0 k ≥ 0 , let [ x ] k [x]_k [ x ] k denote the normalized vector of monomials of total degree k k k , chosen so that ∥ [ x ] k ∥ 2 = ∥ x ∥ 2 k \|[x]_k\|^2=\|x\|^{2k} ∥ [ x ] k ∥ 2 = ∥ x ∥ 2 k . We write z d ( x ) : = ( 1 , [ x ] 1 T , … , [ x ] d T ) T z_d(x):=(1,[x]_1^{\mathsf T},\ldots,[x]_d^{\mathsf T})^{\mathsf T} z d ( x ) := ( 1 , [ x ] 1 T , … , [ x ] d T ) T for the full monomial vector of degree at most d d d . Then h h h is SoS if and only if it admits a Gram representation
h ( x ) = z d ( x ) T Q z d ( x ) h(x)=z_d(x)^{\mathsf T}Qz_d(x) h ( x ) = z d ( x ) T Q z d ( x ) for some symmetric Q ⪰ 0 Q \succeq0 Q ⪰ 0 . See, e.g., [21 , 16 ] .
Definition 1.2 (Nonconstant monomials and strict Gram representation). We denote by
v d ( x ) : = ( [ x ] 1 T , … , [ x ] d T ) T v_d(x):=([x]_1^{\mathsf T},\ldots,[x]_d^{\mathsf T})^{\mathsf T} v d ( x ) := ([ x ] 1 T , … , [ x ] d T ) T the vector of all nonconstant monomials of degrees 1 , … , d 1,\ldots,d 1 , … , d . Its dimension is N n , d = ∑ k = 1 d ( n + k − 1 k ) = ( n + d d ) − 1 N_{n,d}=\sum_{k=1}^{d}\binom{n+k-1}{k}=\binom{n+d}{d}-1 N n , d = ∑ k = 1 d ( k n + k − 1 ) = ( d n + d ) − 1 . When n n n and d d d are fixed, we write N : = N n , d N:=N_{n,d} N := N n , d . For a polynomial q q q with zero constant and linear terms, we say that q q q admits a strict Gram representation on v d v_d v d if
q ( x ) = v d ( x ) T Q v d ( x ) q(x)=v_d(x)^{\mathsf T}Qv_d(x) q ( x ) = v d ( x ) T Q v d ( x ) for some symmetric Q ≻ 0 Q \succ0 Q ≻ 0 . The matrix Q Q Q is called a Gram matrix of q q q . For a chosen strict Gram representation, λ min ( Q ) > 0 \lambda_{\min}(Q)>0 λ m i n ( Q ) > 0 is called its Gram margin. The Gram matrix need not be unique, so the margin is attached to the chosen representation.
Definition 1.3 (SoS-convexity). A polynomial h h h is SoS-convex if y T ∇ 2 h ( x ) y y^{\mathsf T}\nabla^2h(x)y y T ∇ 2 h ( x ) y is an SoS polynomial jointly in ( x , y ) (x,y) ( x , y ) . Equivalently, its Hessian is an SoS matrix [2 ] . We use the standard implication that the first-order Bregman remainder of an SoS-convex polynomial is SoS; the precise references are recalled in Remark 3.1.
How Regularization Creates SoS Exactness: An Overview
Before turning to the technical results, we give a short overview of the mechanism behind the proof. The aim is to explain why increasing regularization can change the SoS behaviour of the model even when the model itself remains nonconvex.
The phenomenon is perhaps easiest to understand geometrically. Suppose that the Taylor model has negative curvature at the base point s = 0 s=0 s = 0 . Since the Hessian of the higher-order regularization term
σ 2 d ∥ s ∥ 2 d , d ≥ 2 , \frac{\sigma}{2d}\|s\|^{2d},\qquad d\ge2, 2 d σ ∥ s ∥ 2 d , d ≥ 2 ,
vanishes at the origin, increasing σ \sigma σ does not remove this negative curvature. Hence the regularized polynomial may remain locally nonconvex at the base point for every finite value of σ \sigma σ ; see also [9 ] . Nevertheless, its algebraic behaviour can change substantially as the regularization increases. Interestingly, Parrilo [22, Sec. 5.1] observed numerically that certain quartically regularized polynomial models appear to be SoS once the regularization is sufficiently large.
Figure 1 gives a one-dimensional slice of a multivariate regularized polynomial at different regularization strengths. The panels illustrate a change in geometry from “not SoS” to “SoS exact” as regularization increases. Note that the SoS labels refer to the full multivariate optimality gap , not to the plotted univariate restriction: every nonnegative univariate polynomial is already SoS.
Figure 1. One-dimensional slices of multivariate regularized polynomial models as the regularization parameter increases. The red dot marks the base point s = 0 s = 0 s = 0 , where the negative quadratic curvature is unchanged by the higher-order regularizer; the star marks a global minimizer.
From polynomials to Taylor models. Any polynomial P : R n → R P:\mathbb{R}^n\to\mathbb{R} P : R n → R of degree at most p p p can be written exactly as a finite Taylor expansion,
P ( s ) = ∑ ∣ α ∣ ≤ p c α s α = ∑ j = 0 p 1 j ! T j [ s ] j , P(s)=\sum_{|\alpha|\le p}c_\alpha s^\alpha=\sum_{j=0}^{p}\frac{1}{j!}T_j[s]^j, P ( s ) = ∣ α ∣ ≤ p ∑ c α s α = j = 0 ∑ p j ! 1 T j [ s ] j ,
where α = ( α 1 , … , α n ) \alpha= (\alpha_1,\ldots,\alpha_n) α = ( α 1 , … , α n ) is a multi-index, ∣ α ∣ = ∑ i = 1 n α i |\alpha| = \sum_{i=1}^{n} \alpha_i ∣ α ∣ = ∑ i = 1 n α i , α ! = ∏ i = 1 n α i ! \alpha! = \prod_{i=1}^{n} \alpha_i! α ! = ∏ i = 1 n α i ! , and s α = ∏ i = 1 n s i α i s^\alpha= \prod_{i=1}^{n} s_i^{\alpha_i} s α = ∏ i = 1 n s i α i . Here T j T_j T j is the symmetric j j j th-order tensor determined by the coefficients of P P P : for indices i 1 , … , i j i_1,\ldots,i_j i 1 , … , i j with multiplicities α 1 , … , α n \alpha_1,\ldots,\alpha_n α 1 , … , α n , set
( T j ) i 1 ⋯ i j = α ! c α . (T_j)_{i_1\cdots i_j} = \alpha! \, c_\alpha. ( T j ) i 1 ⋯ i j = α ! c α .
Indeed, each monomial s α s^\alpha s α appears j ! / α ! j!/\alpha! j ! / α ! times in the symmetric tensor contraction T j [ s ] j T_j[s]^j T j [ s ] j , so the coefficient of s α s^\alpha s α in 1 j ! T j [ s ] j \frac{1}{j!}T_j[s]^j j ! 1 T j [ s ] j is exactly c α c_\alpha c α . In particular, T j = ∇ j P ( 0 ) T_j = \nabla^j P(0) T j = ∇ j P ( 0 ) ; thus this representation introduces no approximation or restriction on P P P .
For convenience, throughout the paper we write the fixed polynomial P P P as its exact symmetric-tensor Taylor form T p T_p T p ; the two symbols denote the same polynomial, not two different models. We study the corresponding Euclidean-regularized polynomial
m σ ( s ) = T 2 d − 1 ( s ) + σ 2 d ∥ s ∥ 2 d , d ≥ 2 , (4) m_\sigma(s) = T_{2d-1}(s) + \frac{\sigma}{2d}\lVert s\rVert^{2d}, \qquad d \ge2, \tag*{(4)} m σ ( s ) = T 2 d − 1 ( s ) + 2 d σ ∥ s ∥ 2 d , d ≥ 2 , (4)
where T 2 d − 1 T_{2d-1} T 2 d − 1 is any polynomial of degree at most 2 d − 1 2d-1 2 d − 1 . This also includes even-degree Taylor models by setting the ( 2 d − 1 ) (2d-1) ( 2 d − 1 ) st-order tensor to zero. Writing
T 2 d − 1 ( s ) = f 0 + g ⊤ s + 1 2 H [ s ] 2 + ∑ j = 3 2 d − 1 1 j ! T j [ s ] j , T_{2d-1}(s) = f_0 + g^\top s + \frac{1}{2}H[s]^2 + \sum_{j=3}^{2d-1}\frac{1}{j!}T_j[s]^j, T 2 d − 1 ( s ) = f 0 + g ⊤ s + 2 1 H [ s ] 2 + j = 3 ∑ 2 d − 1 j ! 1 T j [ s ] j ,
we have T 0 = f 0 T_0 = f_0 T 0 = f 0 , T 1 = g T_1 = g T 1 = g , and T 2 = H T_2 = H T 2 = H , with T j [ s ] j : = T j [ s , … , s ] T_j[s]^j := T_j[s,\ldots,s] T j [ s ] j := T j [ s , … , s ] .
Shifting the model at its global minimizer. The starting point of our proof is to rewrite the polynomial around a global minimizer. This is in the spirit of the classical optimality characterizations used for trust-region and regularization subproblems; see, e.g., [24 , 6 , 9 ] . The difference here is that we use the resulting identity as an algebraic decomposition for the SoS analysis. Let s σ ∗ s_\sigma^* s σ ∗ be a global minimizer of m σ m_\sigma m σ , and define
q σ ( v ) : = m σ ( s σ ∗ + v ) − m σ ( s σ ∗ ) . q_\sigma(v) := m_\sigma(s_\sigma^* + v) - m_\sigma(s_\sigma^*). q σ ( v ) := m σ ( s σ ∗ + v ) − m σ ( s σ ∗ ) .
The polynomial q σ q_\sigma q σ is nonnegative and vanishes at v = 0 v = 0 v = 0 . The following identity is the starting point of the argument.
Lemma 2.1 (Shifted optimality identity). Let s σ ∗ s_\sigma^* s σ ∗ be a global minimizer of (1). Then
q σ ( v ) = p σ ( v ) + σ d R s σ ∗ , d ( v ) , (5) q_\sigma(v) = p_\sigma(v) + \frac{\sigma}{d}R_{s_\sigma^*,d}(v), \tag*{(5)} q σ ( v ) = p σ ( v ) + d σ R s σ ∗ , d ( v ) , (5)
where
p σ ( v ) : = ∑ j = 2 2 d − 1 1 j ! ∇ j T 2 d − 1 ( s σ ∗ ) [ v ] j , R s , d ( v ) : = 1 2 ∥ s + v ∥ 2 d − 1 2 ∥ s ∥ 2 d − d ∥ s ∥ 2 d − 2 s T v . p_{\sigma}(v) := \sum_{j=2}^{2d-1} \frac{1}{j!}\nabla^j T_{2d-1}(s_{\sigma}^{*})[v]^j,\qquad R_{s,d}(v) := \frac{1}{2}\|s+v\|^{2d} - \frac{1}{2}\|s\|^{2d} - d\|s\|^{2d-2}s^{\mathsf T}v. p σ ( v ) := j = 2 ∑ 2 d − 1 j ! 1 ∇ j T 2 d − 1 ( s σ ∗ ) [ v ] j , R s , d ( v ) := 2 1 ∥ s + v ∥ 2 d − 2 1 ∥ s ∥ 2 d − d ∥ s ∥ 2 d − 2 s T v .
Proof. Since the Taylor expansion of T 2 d − 1 T_{2d-1} T 2 d − 1 around s σ ∗ s_{\sigma}^{*} s σ ∗ is exact,
q σ ( v ) = ∑ j = 1 2 d − 1 1 j ! ∇ j T 2 d − 1 ( s σ ∗ ) [ v ] j + σ 2 d ( ∥ s σ ∗ + v ∥ 2 d − ∥ s σ ∗ ∥ 2 d ) . q_{\sigma}(v) = \sum_{j=1}^{2d-1} \frac{1}{j!}\nabla^j T_{2d-1}(s_{\sigma}^{*})[v]^j + \frac{\sigma}{2d}\left(\|s_{\sigma}^{*}+v\|^{2d}-\|s_{\sigma}^{*}\|^{2d}\right). q σ ( v ) = j = 1 ∑ 2 d − 1 j ! 1 ∇ j T 2 d − 1 ( s σ ∗ ) [ v ] j + 2 d σ ( ∥ s σ ∗ + v ∥ 2 d − ∥ s σ ∗ ∥ 2 d ) .
The first-order optimality condition
∇ T 2 d − 1 ( s σ ∗ ) + σ ∥ s σ ∗ ∥ 2 d − 2 s σ ∗ = 0 \nabla T_{2d-1}(s_{\sigma}^{*})+\sigma\|s_{\sigma}^{*}\|^{2d-2}s_{\sigma}^{*}=0 ∇ T 2 d − 1 ( s σ ∗ ) + σ ∥ s σ ∗ ∥ 2 d − 2 s σ ∗ = 0
cancels the linear term and gives (5) .
We stress that Lemma 2.1 is an identity used in the analysis; it does not assume that the global minimizer is known in advance. The purpose of the subsequent SoS representation is precisely to recover this minimizer.
The three steps of the proof. The decomposition (5) separates the proof into two parts whose behaviour as σ \sigma σ increases is very different.
First, the regularization term provides a positive SoS core. The polynomial R s , d R_{s,d} R s , d is precisely the first-order Bregman remainder of Φ d ( s ) = 1 2 ∥ s ∥ 2 d \Phi_d(s)=\frac{1}{2}\|s\|^{2d} Φ d ( s ) = 2 1 ∥ s ∥ 2 d . Since Φ d \Phi_d Φ d is SoS-convex, R s , d R_{s,d} R s , d is SoS. This is standard result of SoS-convexity [2 , 13 ] . However, the key result of § 3 is considerably stronger: for every s ≠ 0 s\ne0 s = 0 , this remainder admits a positive-definite Gram representation on all nonconstant monomials up to degree d d d . Informally, the SoS representation therefore has some “room” to absorb additional polynomial terms. This is made precise through the strict Gram margin developed in § 3 .
Second, the remaining Taylor terms stay bounded. p σ p_{\sigma} p σ begins at quadratic order and has degree at most 2 d − 1 2d-1 2 d − 1 . Note that p σ p_{\sigma} p σ contains neither a constant nor a linear term; the constant term disappears because we shift by the value at s σ ∗ s_{\sigma}^{*} s σ ∗ , while the linear term is eliminated by the first-order optimality condition. Its coefficients depend only on the fixed Taylor tensors and on s σ ∗ s_{\sigma}^{*} s σ ∗ . As the regularization increases, s σ ∗ s_{\sigma}^{*} s σ ∗ approaches the base point, and these coefficients remain uniformly bounded; see § 4 .
Finally, the regularization eventually dominates. Generally, as σ \sigma σ grows, the global minimizer moves towards the base point s = 0 s=0 s = 0 . The important question is how quickly this happens, since the Gram margin itself also depends on s σ ∗ s_{\sigma}^{*} s σ ∗ . Under the assumption g ≠ 0 g\ne0 g = 0 , (i.e., the base point has not yet reached first-order stationarity), we show that
∥ s σ ∗ ∥ = Θ ( σ − 1 / ( 2 d − 1 ) ) . \|s_{\sigma}^{*}\|=\Theta\left(\sigma^{-1/(2d-1)}\right). ∥ s σ ∗ ∥ = Θ ( σ − 1/ ( 2 d − 1 ) ) .
Hence the strict Gram margin contributed by σ d R s σ ∗ , d \sigma^d R_{s_{\sigma}^{*},d} σ d R s σ ∗ , d grows with σ \sigma σ , whereas the coefficients of p σ p_{\sigma} p σ remain bounded. For sufficiently large σ \sigma σ , the regularization term therefore absorbs the remaining Taylor terms and the entire shifted polynomial q σ q_{\sigma} q σ becomes SoS. The perturbation argument and the resulting SoS exactness theorem are proved in § 4 . For example, in the quartic case d = 2 d=2 d = 2 , ∥ s σ ∗ ∥ = Θ ( σ − 1 / 3 ) \|s_{\sigma}^{*}\|=\Theta(\sigma^{-1/3}) ∥ s σ ∗ ∥ = Θ ( σ − 1/3 ) , σ ∥ s σ ∗ ∥ 2 = Θ ( σ 1 / 3 ) \sigma\|s_{\sigma}^{*}\|^2=\Theta(\sigma^{1/3}) σ ∥ s σ ∗ ∥ 2 = Θ ( σ 1/3 ) , so the effective strict Gram margin grows like σ 1 / 3 \sigma^{1/3} σ 1/3 . In one line, the proof structure can be summarized as
shift at the minimizer ⟹ \Longrightarrow ⟹ bounded Taylor part + growing strict Gram part
⟹ \Longrightarrow ⟹ SoS exactness as σ \sigma σ increases.
Bregman Remainders and Strict Gram Margins
This section studies the part of the model that comes from the regularization term. The reason is simple: after a regularized polynomial is shifted around a stationary point, the contribution of the regularizer is its first-order Bregman remainder. Understanding this remainder will tell us how much of the remaining Taylor polynomial the regularizer can absorb. Let d ≥ 2 d\ge2 d ≥ 2 and define the Euclidean regularizer
Φ d ( s ) : = 1 2 ∥ s ∥ 2 d . \Phi_d(s):=\frac{1}{2}\|s\|^{2d}. Φ d ( s ) := 2 1 ∥ s ∥ 2 d .
For a base point s ∈ R n s \in\mathbb{R}^{n} s ∈ R n and a displacement v ∈ R n v \in\mathbb{R}^{n} v ∈ R n , its Bregman remainder is
R s , d ( v ) : = Φ d ( s + v ) − Φ d ( s ) − ∇ Φ d ( s ) T v = 1 2 ∥ s + v ∥ 2 d − 1 2 ∥ s ∥ 2 d − d ∥ s ∥ 2 d − 2 s T v . (6) R_{s,d}(v) := \Phi_d(s+v)-\Phi_d(s)-\nabla\Phi_d(s)^{\mathsf{T}}v = \frac{1}{2}\lVert s+v\rVert^{2d}-\frac{1}{2}\lVert s\rVert^{2d}-d\lVert s\rVert^{2d-2}s^{\mathsf{T}}v. \tag*{(6)} R s , d ( v ) := Φ d ( s + v ) − Φ d ( s ) − ∇ Φ d ( s ) T v = 2 1 ∥ s + v ∥ 2 d − 2 1 ∥ s ∥ 2 d − d ∥ s ∥ 2 d − 2 s T v . (6)
It is standard that this polynomial is SoS when Φ d \Phi_d Φ d is SoS-convex; see Remark 3.1. Our main goal is stronger: we show that for every nonzero direction, the Bregman remainder has a strict Gram representation. This extra room inside the SoS cone is what will later allow us to absorb the other Taylor terms.
We use the monomial vector v d \mathbf{v}_d v d and the notion of strict Gram representation from Definition 1.2 .
Lemma 3.1 (SoS Bregman remainder). For every d ≥ 2 d \ge2 d ≥ 2 , the polynomial Φ d ( s ) = 1 2 ∥ s ∥ 2 d \Phi_d(s) = \frac{1}{2}\lVert s\rVert^{2d} Φ d ( s ) = 2 1 ∥ s ∥ 2 d is SoS-convex. Therefore, its first-order Bregman remainder R s , d ( v ) R_{s,d}(v) R s , d ( v ) is a sum-of-squares polynomial. Specifically, for any v ∈ R n v \in\mathbb{R}^{n} v ∈ R n , let w = s + v w=s+v w = s + v ,
Φ d ( w ) − Φ d ( s ) − ∇ Φ d ( s ) T ( w − s ) \Phi_d(w)-\Phi_d(s)-\nabla\Phi_d(s)^{\mathsf{T}}(w-s) Φ d ( w ) − Φ d ( s ) − ∇ Φ d ( s ) T ( w − s ) is SoS jointly in ( s , w ) (s,w) ( s , w ) . This means that R s , d ( v ) R_{s,d}(v) R s , d ( v ) is SoS jointly in ( s , v ) (s,v) ( s , v ) , and hence is R s , d ( v ) R_{s,d}(v) R s , d ( v ) SoS in v v v for every fixed s s s .
Proof. Φ d \Phi_d Φ d is clearly SoS-convex, to see this. We have ∇ 2 Φ d ( s ) = d ∥ s ∥ 2 d − 2 I + 2 d ( d − 1 ) ∥ s ∥ 2 d − 4 s s T \nabla^2\Phi_d(s)=d\lVert s\rVert^{2d-2}I+2d(d-1)\lVert s\rVert^{2d-4}ss^{\mathsf{T}} ∇ 2 Φ d ( s ) = d ∥ s ∥ 2 d − 2 I + 2 d ( d − 1 ) ∥ s ∥ 2 d − 4 s s T . Therefore, for w ∈ R n w \in\mathbb{R}^{n} w ∈ R n
w T ∇ 2 Φ d ( s ) w = d ∥ s ∥ 2 d − 2 ∥ w ∥ 2 + 2 d ( d − 1 ) ∥ s ∥ 2 d − 4 ( s T w ) 2 . w^{\mathsf{T}}\nabla^2\Phi_d(s)w=d\lVert s\rVert^{2d-2}\lVert w\rVert^2+2d(d-1)\lVert s\rVert^{2d-4}(s^{\mathsf{T}}w)^2. w T ∇ 2 Φ d ( s ) w = d ∥ s ∥ 2 d − 2 ∥ w ∥ 2 + 2 d ( d − 1 ) ∥ s ∥ 2 d − 4 ( s T w ) 2 .
Both terms are SoS polynomials in ( s , w ) (s,w) ( s , w ) , so Φ d \Phi_d Φ d is SoS-convex. The first-order characterization of SoS-convexity gives
Φ d ( w ) − Φ d ( s ) − ∇ Φ d ( s ) T ( w − s ) ∈ S o S . \Phi_d(w)-\Phi_d(s)-\nabla\Phi_d(s)^{\mathsf{T}}(w-s)\in\mathrm{SoS}. Φ d ( w ) − Φ d ( s ) − ∇ Φ d ( s ) T ( w − s ) ∈ SoS .
Equivalently, using the integral Taylor remainder,
Φ d ( w ) − Φ d ( s ) − ∇ Φ d ( s ) T ( w − s ) = ∫ 0 1 ( 1 − t ) ( w − s ) T ∇ 2 Φ d ( s + t ( w − s ) ) ( w − s ) d t , \Phi_d(w)-\Phi_d(s)-\nabla\Phi_d(s)^{\mathsf{T}}(w-s)=\int_0^1(1-t)(w-s)^{\mathsf{T}}\nabla^2\Phi_d(s+t(w-s))(w-s)\,\mathrm{d}t, Φ d ( w ) − Φ d ( s ) − ∇ Φ d ( s ) T ( w − s ) = ∫ 0 1 ( 1 − t ) ( w − s ) T ∇ 2 Φ d ( s + t ( w − s )) ( w − s ) d t ,
and the integral remains SoS because the SoS cone is closed. Setting w = s + v w=s+v w = s + v gives (6) .
Remark 3.1 (Standard reference). The result that
f is SoS convex i.e., ∇ 2 f is an SoS matrix ⟹ f ( y ) − f ( x ) − ∇ f ( x ) T ( y − x ) is SoS f\text{ is SoS convex i.e., }\nabla^2 f\text{ is an SoS matrix}\quad\Longrightarrow\quad f(y)-f(x)-\nabla f(x)^{\mathsf{T}}(y-x)\text{ is SoS} f is SoS convex i.e., ∇ 2 f is an SoS matrix ⟹ f ( y ) − f ( x ) − ∇ f ( x ) T ( y − x ) is SoS is standard. It appears as part of Theorem 3.1 in Ahmadi and Parrilo [2 ] . A closely related stationary-point statement appears as Lemma 8 in Helton and Nie [13 ] : if f ( u ) = 0 f(u)=0 f ( u ) = 0 , ∇ f ( u ) = 0 \nabla f(u)=0 ∇ f ( u ) = 0 , and ∇ 2 f \nabla^2f ∇ 2 f is an SoS matrix, then f f f is SoS. The complete statements of both results, in the form in which we use them, are reproduced in Section A. We emphasize that these cited results are used only to establish Lemma 3.1. The main result of this paper and the perturbation argument in Theorem 4.1 requires a positive-definite strict Gram representation where Lemma 3.1 is not enough. We will use the subsequent sections to develop the strict Gram argument.
A Strict Gram Margin for Euclidean Regularization
Being SoS is not enough for the perturbation argument used later: the Gram matrix could still be singular. We now show that the Euclidean Bregman remainder has a positive-definite Gram matrix whenever s ≠ 0 s\ne0 s = 0 , and we quantify how its smallest eigenvalue depends on ∥ s ∥ \lVert s\rVert ∥ s ∥ .
Theorem 3.1 (Strict Gram representation). For a fixed s ≠ 0 s\ne0 s = 0 , d ≥ 2 d\ge2 d ≥ 2 and R s , d ( v ) R_{s,d}(v) R s , d ( v ) defined in (6) , there exists a symmetric matrix Q R ( s ) ≻ 0 Q_R(s)\succ0 Q R ( s ) ≻ 0 such that
R s , d ( v ) = v d ( v ) T Q R ( s ) v d ( v ) . (7) R_{s,d}(v)=\mathbf{v}_d(v)^{\mathsf{T}}Q_R(s)\mathbf{v}_d(v). \tag*{(7)} R s , d ( v ) = v d ( v ) T Q R ( s ) v d ( v ) . (7) Moreover, there exists a constant c n , d > 0 c_{n,d}>0 c n , d > 0 , independent of s s s , such that for 0 < ∥ s ∥ ≤ 1 0<\lVert s\rVert\le1 0 < ∥ s ∥ ≤ 1 ,
λ min ( Q R ( s ) ) ≥ c n , d ∥ s ∥ 2 d − 2 . (8) \lambda_{\min}(Q_R(s))\ge c_{n,d}\lVert s\rVert^{2d-2}. \tag*{(8)} λ m i n ( Q R ( s )) ≥ c n , d ∥ s ∥ 2 d − 2 . (8)
Proof of Theorem 3.1. Applying the integral Taylor formula to (6) gives
R s , d ( v ) = d ∫ 0 1 ( 1 − t ) ∥ s + t v ∥ 2 d − 2 ∥ v ∥ 2 d t + 2 d ( d − 1 ) ∫ 0 1 ( 1 − t ) ∥ s + t v ∥ 2 d − 4 ( ( s + t v ) ⊤ v ) 2 d t . (9) R_{s,d}(v)=d\int_0^1(1-t)\lVert s+tv\rVert^{2d-2}\lVert v\rVert^2\,dt+2d(d-1)\int_0^1(1-t)\lVert s+tv\rVert^{2d-4}\bigl((s+tv)^\top v\bigr)^2\,dt. \tag*{(9)} R s , d ( v ) = d ∫ 0 1 ( 1 − t ) ∥ s + t v ∥ 2 d − 2 ∥ v ∥ 2 d t + 2 d ( d − 1 ) ∫ 0 1 ( 1 − t ) ∥ s + t v ∥ 2 d − 4 ( ( s + t v ) ⊤ v ) 2 d t . (9)
Here I 1 I_1 I 1 and I 2 I_2 I 2 denote the two integrals displayed in (9) . Their roles are different: I 1 I_1 I 1 supplies the strict part of the Gram matrix, whereas I 2 I_2 I 2 contributes only a positive-semidefinite part. The remaining lemmas verify these two facts and then transport the result from e 1 e_1 e 1 to an arbitrary nonzero point.
Table 1.
By Lemma 3.4, the polynomials in the first integral at s = e 1 s=e_1 s = e 1 have the full coefficient-spanning property. Hence Lemma 3.3 gives a Gram matrix Q 1 ( e 1 ) ≻ 0 Q_1(e_1)\succ0 Q 1 ( e 1 ) ≻ 0 satisfying
I 1 ( v ) = v d ( v ) ⊤ Q 1 ( e 1 ) v d ( v ) . I_1(v)=\mathbf{v}_d(v)^\top Q_1(e_1)\mathbf{v}_d(v). I 1 ( v ) = v d ( v ) ⊤ Q 1 ( e 1 ) v d ( v ) .
By Lemma 3.2, the second integral has a Gram matrix Q 2 ( e 1 ) ⪰ 0 Q_2(e_1)\succeq0 Q 2 ( e 1 ) ⪰ 0 satisfying
I 2 ( v ) = v d ( v ) ⊤ Q 2 ( e 1 ) v d ( v ) . I_2(v)=\mathbf{v}_d(v)^\top Q_2(e_1)\mathbf{v}_d(v). I 2 ( v ) = v d ( v ) ⊤ Q 2 ( e 1 ) v d ( v ) .
Therefore, using (9) , the Gram matrix for R e 1 , d R_{e_1,d} R e 1 , d satisfies
Q R ( e 1 ) : = d Q 1 ( e 1 ) + 2 d ( d − 1 ) Q 2 ( e 1 ) ⪰ d λ min ( Q 1 ( e 1 ) ) I N ≻ 0. (10) Q_R(e_1):=dQ_1(e_1)+2d(d-1)Q_2(e_1)\succeq d\lambda_{\min}\bigl(Q_1(e_1)\bigr)I_N\succ0. \tag*{(10)} Q R ( e 1 ) := d Q 1 ( e 1 ) + 2 d ( d − 1 ) Q 2 ( e 1 ) ⪰ d λ m i n ( Q 1 ( e 1 ) ) I N ≻ 0. (10)
Applying Lemma 3.5 gives the change of coordinates from e 1 e_1 e 1 to any fixed s ≠ 0 s\ne0 s = 0 ,
λ min ( Q R ( s ) ) ≥ ∥ s ∥ 2 d − 2 λ min ( Q R ( e 1 ) ) , 0 < ∥ s ∥ ≤ 1. \lambda_{\min}\bigl(Q_R(s)\bigr)\ge\lVert s\rVert^{2d-2}\lambda_{\min}\bigl(Q_R(e_1)\bigr),\qquad0<\lVert s\rVert\le1. λ m i n ( Q R ( s ) ) ≥ ∥ s ∥ 2 d − 2 λ m i n ( Q R ( e 1 ) ) , 0 < ∥ s ∥ ≤ 1.
Thus (8) holds with c n , d : = λ min ( Q R ( e 1 ) ) > 0 c_{n,d}:=\lambda_{\min}\bigl(Q_R(e_1)\bigr)>0 c n , d := λ m i n ( Q R ( e 1 ) ) > 0 .
The Two Integral Terms and the Spanning Argument
We first dispose of the easier term: I 2 I_2 I 2 is a weighted sum of squares and therefore contributes a positive-semidefinite Gram matrix.
Lemma 3.2 (The second integral contribution is SoS). For every fixed s s s and d ≥ 2 d\ge2 d ≥ 2 , there exists a symmetric matrix Q 2 ( s ) ⪰ 0 Q_2(s)\succeq0 Q 2 ( s ) ⪰ 0 such that
I 2 ( v ) = v d ( v ) ⊤ Q 2 ( s ) v d ( v ) . (11) I_2(v)=\mathbf{v}_d(v)^\top Q_2(s)\mathbf{v}_d(v). \tag*{(11)} I 2 ( v ) = v d ( v ) ⊤ Q 2 ( s ) v d ( v ) . (11) Proof. For d ≥ 2 d\ge2 d ≥ 2 , the multinomial expansion gives
∥ s + t v ∥ 2 d − 4 ( ( s + t v ) ⊤ v ) 2 = ∑ ∣ α ∣ = d − 2 c ~ α [ ∏ j = 1 n ( s j + t v j ) α j ( s + t v ) ⊤ v ] 2 , (12) \lVert s+tv\rVert^{2d-4}\bigl((s+tv)^\top v\bigr)^2
=\sum_{|\alpha|=d-2}\widetilde{c}_\alpha\left[\prod_{j=1}^{n}(s_j+tv_j)^{\alpha_j}(s+tv)^\top v\right]^2, \tag*{(12)} ∥ s + t v ∥ 2 d − 4 ( ( s + t v ) ⊤ v ) 2 = ∣ α ∣ = d − 2 ∑ c α [ j = 1 ∏ n ( s j + t v j ) α j ( s + t v ) ⊤ v ] 2 , (12) where
c ~ α = ( d − 2 α ) = ( d − 2 ) ! α 1 ! ⋯ α n ! > 0. \widetilde{c}_\alpha=\binom{d-2}{\alpha}=\frac{(d-2)!}{\alpha_1!\cdots\alpha_n!}>0. c α = ( α d − 2 ) = α 1 ! ⋯ α n ! ( d − 2 )! > 0. For each α \alpha α , let a ~ α ( s , t ) \widetilde{a}_\alpha(s,t) a α ( s , t ) denote the coefficient vector of ∏ j = 1 n ( s j + t v j ) α j ( s + t v ) ⊤ v \prod_{j=1}^{n}(s_j+tv_j)^{\alpha_j}(s+tv)^\top v ∏ j = 1 n ( s j + t v j ) α j ( s + t v ) ⊤ v with respect to v d ( v ) \mathbf{v}_d(v) v d ( v ) . Define
Q 2 ( s ) : = ∑ ∣ α ∣ = d − 2 c ~ α ∫ 0 1 ( 1 − t ) a ~ α ( s , t ) a ~ α ( s , t ) ⊤ d t . (13) Q_2(s):=\sum_{|\alpha|=d-2}\widetilde{c}_\alpha\int_0^1(1-t)\widetilde{a}_\alpha(s,t)\widetilde{a}_\alpha(s,t)^\top\,dt. \tag*{(13)} Q 2 ( s ) := ∣ α ∣ = d − 2 ∑ c α ∫ 0 1 ( 1 − t ) a α ( s , t ) a α ( s , t ) ⊤ d t . (13) Then (11) follows from (12) . Moreover, for every ξ ∈ R N \xi\in\mathbb{R}^N ξ ∈ R N ,
ξ ⊤ Q 2 ( s ) ξ = ∑ ∣ α ∣ = d − 2 c ~ α ∫ 0 1 ( 1 − t ) ( ξ ⊤ a ~ α ( s , t ) ) 2 d t ≥ 0. (14) \xi^\top Q_2(s)\xi=\sum_{|\alpha|=d-2}\widetilde{c}_\alpha\int_0^1(1-t)\bigl(\xi^\top\widetilde{a}_\alpha(s,t)\bigr)^2\,dt\ge0. \tag*{(14)} ξ ⊤ Q 2 ( s ) ξ = ∣ α ∣ = d − 2 ∑ c α ∫ 0 1 ( 1 − t ) ( ξ ⊤ a α ( s , t ) ) 2 d t ≥ 0. (14) Thus Q 2 ( s ) ⪰ 0 Q_2(s)\succeq0 Q 2 ( s ) ⪰ 0 . In particular, each matrix under the integral is rank at most one and positive semidefinite, and the strictly positive coefficients 2 d ( d − 1 ) 2d(d-1) 2 d ( d − 1 ) , c ~ α \widetilde{c}_\alpha c α , and 1 − t 1-t 1 − t prevent any cancellation between the square contributions.
The first integral I 1 I_1 I 1 is the source of strictness. To prove this, we track the coefficients of the squared polynomials appearing in the integral and ask whether they cover every nonconstant monomial direction.
Throughout the following lemmas, coefficient vectors are taken with respect to the fixed ordering of v d \mathbf{v}_d v d from Definition 1.2 .
Lemma 3.3 (The first integral contribution and coefficient spanning). The following statements hold.
For fixed s s s , let p α , i , t ( v ) : = v i ∏ j = 1 n ( s j + t v j ) α j p_{\alpha,i,t}(v) := v_i\prod_{j=1}^{n}(s_j+tv_j)^{\alpha_j} p α , i , t ( v ) := v i ∏ j = 1 n ( s j + t v j ) α j . The first integral in (9) can be expressed as
I 1 ( v ) = ∑ i = 1 n ∑ ∣ α ∣ = d − 1 c α ∫ 0 1 ( 1 − t ) p α , i , t ( v ) 2 d t = v d ( v ) ⊤ Q 1 ( s ) v d ( v ) , (15) I_1(v)=\sum_{i=1}^{n}\sum_{|\alpha|=d-1}c_\alpha\int_0^1(1-t)p_{\alpha,i,t}(v)^2\,dt=\mathbf{v}_d(v)^\top Q_1(s)\mathbf{v}_d(v), \tag*{(15)} I 1 ( v ) = i = 1 ∑ n ∣ α ∣ = d − 1 ∑ c α ∫ 0 1 ( 1 − t ) p α , i , t ( v ) 2 d t = v d ( v ) ⊤ Q 1 ( s ) v d ( v ) , (15) where
Q 1 ( s ) : = ∑ i = 1 n ∑ ∣ α ∣ = d − 1 c α ∫ 0 1 ( 1 − t ) a i , α ( s , t ) a i , α ( s , t ) ⊤ d t . (16) Q_1(s):=\sum_{i=1}^{n}\sum_{|\alpha|=d-1}c_\alpha\int_0^1(1-t)a_{i,\alpha}(s,t)a_{i,\alpha}(s,t)^\top\,dt. \tag*{(16)} Q 1 ( s ) := i = 1 ∑ n ∣ α ∣ = d − 1 ∑ c α ∫ 0 1 ( 1 − t ) a i , α ( s , t ) a i , α ( s , t ) ⊤ d t . (16) For fixed s ∈ R n s\in\mathbb{R}^n s ∈ R n , let a i , α ( s , t ) ∈ R N a_{i,\alpha}(s,t)\in\mathbb{R}^N a i , α ( s , t ) ∈ R N denote the coefficient vector of p α , i , t p_{\alpha,i,t} p α , i , t with respect to the ordered monomial vector v d ( v ) \mathbf{v}_d(v) v d ( v ) ; that is, p α , i , t ( v ) = a i , α ( s , t ) ⊤ v d ( v ) p_{\alpha,i,t}(v)=a_{i,\alpha}(s,t)^\top\mathbf{v}_d(v) p α , i , t ( v ) = a i , α ( s , t ) ⊤ v d ( v ) . Equivalently, we write
a i , α ( s , t ) = coeff v d ( p α , i , t ) ∈ R N . a_{i,\alpha}(s,t)=\operatorname{coeff}_{\mathbf{v}_d}(p_{\alpha,i,t})\in\mathbb{R}^N. a i , α ( s , t ) = coeff v d ( p α , i , t ) ∈ R N . *The map t ↦ a i , α ( s , t ) t\mapsto a_{i,\alpha}(s,t) t ↦ a i , α ( s , t ) is a vector-valued polynomial2 of degree at most d − 1 d-1 d − 1 in t t t . In particular,*
p α , i , t ( v ) = a i , α ( s , t ) ⊤ v d ( v ) = ( ∑ k = 0 d − 1 b i , α , k ( s ) t k ) ⊤ v d ( v ) . (17) p_{\alpha,i,t}(v)=a_{i,\alpha}(s,t)^\top\mathbf{v}_d(v)=\left(\sum_{k=0}^{d-1}b_{i,\alpha,k}(s)t^k\right)^\top\mathbf{v}_d(v). \tag*{(17)} p α , i , t ( v ) = a i , α ( s , t ) ⊤ v d ( v ) = ( k = 0 ∑ d − 1 b i , α , k ( s ) t k ) ⊤ v d ( v ) . (17) where for fixed s s s , each b i , α , k ∈ R N b_{i,\alpha,k}\in\mathbb{R}^N b i , α , k ∈ R N .
Q 1 ( s ) ≻ 0 Q_1(s)\succ0 Q 1 ( s ) ≻ 0 if and only if { b i , α , k ( s ) } i , α , k \{b_{i,\alpha,k}(s)\}_{i,\alpha,k} { b i , α , k ( s ) } i , α , k satisfies the following condition:
∀ 0 ≠ ξ ∈ R N , ∃ i = 1 , … , n , ∣ α ∣ = d − 1 , 0 ≤ k ≤ d − 1 s.t. ξ ⊤ b i , α , k ( s ) ≠ 0. \forall0\ne\xi\in\mathbb{R}^N,\quad\exists\ i=1,\ldots,n,\ |\alpha|=d-1,\quad0\le k\le d-1\quad\text{s.t.}\quad\xi^\top b_{i,\alpha,k}(s)\ne0. ∀0 = ξ ∈ R N , ∃ i = 1 , … , n , ∣ α ∣ = d − 1 , 0 ≤ k ≤ d − 1 s.t. ξ ⊤ b i , α , k ( s ) = 0. (Spanning property)
Proof. Expanding term by term gives
∥ s + t v ∥ 2 d − 2 ∥ v ∥ 2 = ( ∑ j = 1 n ( s j + t v j ) 2 ) d − 1 ( ∑ i = 1 n v i 2 ) = ( ∑ ∣ α ∣ = d − 1 c α ∏ j = 1 n ( s j + t v j ) 2 α j ) ( ∑ i = 1 n v i 2 ) = ∑ i = 1 n ∑ ∣ α ∣ = d − 1 c α [ v i ∏ j = 1 n ( s j + t v j ) α j ] 2 , where c α = ( d − 1 α ) = ( d − 1 ) ! α 1 ! ⋯ α n ! > 0. \begin{aligned}
\lVert s+tv\rVert^{2d-2}\lVert v\rVert^2
=\left(\sum_{j=1}^{n}(s_j+tv_j)^2\right)^{d-1}\left(\sum_{i=1}^{n}v_i^2\right)
=\left(\sum_{|\alpha|=d-1}c_\alpha\prod_{j=1}^{n}(s_j+tv_j)^{2\alpha_j}\right)\left(\sum_{i=1}^{n}v_i^2\right) \\
&=\sum_{i=1}^{n}\sum_{|\alpha|=d-1}c_\alpha\left[v_i\prod_{j=1}^{n}(s_j+tv_j)^{\alpha_j}\right]^2,\qquad\text{where}\quad c_\alpha=\binom{d-1}{\alpha}=\frac{(d-1)!}{\alpha_1!\cdots\alpha_n!}>0.
\end{aligned} ∥ s + t v ∥ 2 d − 2 ∥ v ∥ 2 = ( j = 1 ∑ n ( s j + t v j ) 2 ) d − 1 ( i = 1 ∑ n v i 2 ) = ∣ α ∣ = d − 1 ∑ c α j = 1 ∏ n ( s j + t v j ) 2 α j ( i = 1 ∑ n v i 2 ) = i = 1 ∑ n ∣ α ∣ = d − 1 ∑ c α [ v i j = 1 ∏ n ( s j + t v j ) α j ] 2 , where c α = ( α d − 1 ) = α 1 ! ⋯ α n ! ( d − 1 )! > 0.
Therefore,
I 1 ( v ) = ∑ i = 1 n ∑ ∣ α ∣ = d − 1 c α ∫ 0 1 ( 1 − t ) p α , i , t ( v ) 2 d t . (18) I_1(v)=\sum_{i=1}^{n}\sum_{|\alpha|=d-1}c_\alpha\int_0^1(1-t)p_{\alpha,i,t}(v)^2\,dt. \tag*{(18)} I 1 ( v ) = i = 1 ∑ n ∣ α ∣ = d − 1 ∑ c α ∫ 0 1 ( 1 − t ) p α , i , t ( v ) 2 d t . (18)
This proves the first equality in (15) . By the definition of a i , α ( s , t ) a_{i,\alpha}(s,t) a i , α ( s , t ) ,
p α , i , t ( v ) 2 = v d ( v ) ⊤ a i , α ( s , t ) a i , α ( s , t ) ⊤ v d ( v ) , p_{\alpha,i,t}(v)^2=\mathbf{v}_d(v)^\top a_{i,\alpha}(s,t)a_{i,\alpha}(s,t)^\top\mathbf{v}_d(v), p α , i , t ( v ) 2 = v d ( v ) ⊤ a i , α ( s , t ) a i , α ( s , t ) ⊤ v d ( v ) ,
and hence (16) proves the second equality in (15) . This proves part 1. Part 2 follows because, for fixed s s s , every entry of a i , α ( s , t ) a_{i,\alpha}(s,t) a i , α ( s , t ) is a polynomial in t t t of degree at most d − 1 d-1 d − 1 . For any ξ ∈ R N \xi\in\mathbb{R}^N ξ ∈ R N , we have
ξ ⊤ Q 1 ( s ) ξ = ∑ i = 1 n ∑ ∣ α ∣ = d − 1 c α ∫ 0 1 ( 1 − t ) [ ξ ⊤ a i , α ( s , t ) ] 2 d t . (19) \xi^\top Q_1(s)\xi=\sum_{i=1}^{n}\sum_{|\alpha|=d-1}c_\alpha\int_0^1(1-t)\left[\xi^\top a_{i,\alpha}(s,t)\right]^2\,dt. \tag*{(19)} ξ ⊤ Q 1 ( s ) ξ = i = 1 ∑ n ∣ α ∣ = d − 1 ∑ c α ∫ 0 1 ( 1 − t ) [ ξ ⊤ a i , α ( s , t ) ] 2 d t . (19)
Since every c α > 0 c_\alpha>0 c α > 0 , the weight 1 − t 1-t 1 − t is strictly positive on ( 0 , 1 ) (0,1) ( 0 , 1 ) , and every integrand in (19) is nonnegative, Q 1 ( s ) ⪰ 0 Q_1(s)\succeq0 Q 1 ( s ) ⪰ 0 .
We now prove part 3. Suppose first that (Spanning property) holds, and fix any 0 ≠ ξ ∈ R N 0 \ne\xi\in\mathbb{R}^{N} 0 = ξ ∈ R N . Then there exist i , α , k i,\alpha,k i , α , k such that ξ T b i , α , k ( s ) ≠ 0 \xi^{\mathsf{T}}b_{i,\alpha,k}(s) \ne0 ξ T b i , α , k ( s ) = 0 . ξ T a i , α ( s , t ) \xi^{\mathsf{T}}a_{i,\alpha}(s,t) ξ T a i , α ( s , t ) is a scalar polynomial with some non-zero coefficient (ξ T b i , α , k ( s ) ≠ 0 \xi^{\mathsf{T}}b_{i,\alpha,k}(s) \ne0 ξ T b i , α , k ( s ) = 0 ) and is therefore not identically zero
ξ T a i , α ( s , t ) = ∑ ℓ = 0 d − 1 ξ T b i , α , ℓ ( s ) t ℓ ≠ 0. \xi^{\mathsf{T}}a_{i,\alpha}(s,t)=\sum_{\ell=0}^{d-1}\xi^{\mathsf{T}}b_{i,\alpha,\ell}(s)t^{\ell}\ne0. ξ T a i , α ( s , t ) = ℓ = 0 ∑ d − 1 ξ T b i , α , ℓ ( s ) t ℓ = 0.
Therefore, for any fixed ξ ∈ R N \xi\in\mathbb{R}^{N} ξ ∈ R N , the following integrant is a nonnegative (not identically zero) polynomial in t ∈ ( 0 , 1 ) t \in(0,1) t ∈ ( 0 , 1 ) . Thus, we have
∫ 0 1 ( 1 − t ) [ ξ T a i , α ( s , t ) ] 2 d t > 0. \int_{0}^{1}(1-t)[\xi^{\mathsf{T}}a_{i,\alpha}(s,t)]^{2}\,dt>0. ∫ 0 1 ( 1 − t ) [ ξ T a i , α ( s , t ) ] 2 d t > 0.
It follows from (19) that ξ T Q 1 ( s ) ξ > 0 \xi^{\mathsf{T}}Q_{1}(s)\xi>0 ξ T Q 1 ( s ) ξ > 0 . Since this holds for every nonzero ξ \xi ξ , Q 1 ( s ) ≻ 0 Q_{1}(s)\succ0 Q 1 ( s ) ≻ 0 .
Conversely, suppose that (Spanning property) fails. Then there exists 0 ≠ ξ ∈ R N 0\ne\xi\in\mathbb{R}^{N} 0 = ξ ∈ R N such that
ξ T b i , α , k ( s ) = 0 for every i , α , k . \xi^{\mathsf{T}}b_{i,\alpha,k}(s)=0\qquad\text{for every }i,\alpha,k. ξ T b i , α , k ( s ) = 0 for every i , α , k .
This gives ξ T a i , α ( s , t ) = 0 \xi^{\mathsf{T}}a_{i,\alpha}(s,t)=0 ξ T a i , α ( s , t ) = 0 for every i , α i,\alpha i , α and every t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) . Hence (19) yields ξ T Q 1 ( s ) ξ = 0 \xi^{\mathsf{T}}Q_{1}(s)\xi=0 ξ T Q 1 ( s ) ξ = 0 , so Q 1 ( s ) Q_{1}(s) Q 1 ( s ) is not positive definite. This proves part 3.
The next lemma verifies the spanning property for Euclidean regularization. The low-degree examples in Examples 3.1 and 3.2 give illustrations of this lemma.
Lemma 3.4 (Spanning for the Euclidean radial polynomials). Fix s = r e 1 s=re_{1} s = r e 1 with r > 0 r>0 r > 0 . The coefficient vectors { b i , α , k ( r e 1 ) } i , α , k \{b_{i,\alpha,k}(re_{1})\}_{i,\alpha,k} { b i , α , k ( r e 1 ) } i , α , k are defined by (17) :
a i , α ( r e 1 , t ) T v d ( v ) = ( ∑ k = 0 d − 1 b i , α , k ( r e 1 ) t k ) T v d ( v ) . a_{i,\alpha}(re_{1},t)^{\mathsf{T}}v_{d}(v)=\left(\sum_{k=0}^{d-1}b_{i,\alpha,k}(re_{1})t^{k}\right)^{\mathsf{T}}v_{d}(v). a i , α ( r e 1 , t ) T v d ( v ) = ( k = 0 ∑ d − 1 b i , α , k ( r e 1 ) t k ) T v d ( v ) . Then { b i , α , k ( r e 1 ) } i , α , k \{b_{i,\alpha,k}(re_{1})\}_{i,\alpha,k} { b i , α , k ( r e 1 ) } i , α , k satisfies (Spanning property); consequently, Q 1 ( r e 1 ) ≻ 0 Q_{1}(re_{1})\succ0 Q 1 ( r e 1 ) ≻ 0 .
Proof. Fix any monomial v β v^{\beta} v β with 1 ≤ ∣ β ∣ ≤ d 1\le|\beta|\le d 1 ≤ ∣ β ∣ ≤ d . Choose an index i i i such that β i > 0 \beta_{i}>0 β i > 0 , and set γ : = β − e i \gamma:=\beta-e_{i} γ := β − e i . Thus ∣ γ ∣ = ∣ β ∣ − 1 ≤ d − 1 |\gamma|=|\beta|-1\le d-1 ∣ γ ∣ = ∣ β ∣ − 1 ≤ d − 1 . Define a multi-index α \alpha α by
α j = γ j ( j = 2 , … , n ) , α 1 = d − 1 − ∑ j = 2 n γ j . \alpha_{j}=\gamma_{j}\quad(j=2,\ldots,n),\qquad\alpha_{1}=d-1-\sum_{j=2}^{n}\gamma_{j}. α j = γ j ( j = 2 , … , n ) , α 1 = d − 1 − j = 2 ∑ n γ j .
Then ∣ α ∣ = d − 1 |\alpha|=d-1 ∣ α ∣ = d − 1 , and moreover α 1 − γ 1 = d − 1 − ∣ γ ∣ = d − ∣ β ∣ ≥ 0 \alpha_{1}-\gamma_{1}=d-1-|\gamma|=d-|\beta|\ge0 α 1 − γ 1 = d − 1 − ∣ γ ∣ = d − ∣ β ∣ ≥ 0 . Expanding the corresponding polynomial gives
p α , i , t ( v ) : = v i ( r + t v 1 ) α 1 ∏ j = 2 n ( t v j ) γ j = ∑ k = 0 α 1 ( α 1 k ) r α 1 − k t k + ∑ j = 2 n γ j v i v 1 k ∏ j = 2 n v j γ j . (20) p_{\alpha,i,t}(v):=v_{i}(r+tv_{1})^{\alpha_{1}}\prod_{j=2}^{n}(tv_{j})^{\gamma_{j}}
=\sum_{k=0}^{\alpha_{1}}\binom{\alpha_{1}}{k}r^{\alpha_{1}-k}t^{k+\sum_{j=2}^{n}\gamma_{j}}v_{i}v_{1}^{k}\prod_{j=2}^{n}v_{j}^{\gamma_{j}}. \tag*{(20)} p α , i , t ( v ) := v i ( r + t v 1 ) α 1 j = 2 ∏ n ( t v j ) γ j = k = 0 ∑ α 1 ( k α 1 ) r α 1 − k t k + ∑ j = 2 n γ j v i v 1 k j = 2 ∏ n v j γ j . (20)
The coefficient of t ∣ γ ∣ = t ∣ β ∣ − 1 t^{|\gamma|}=t^{|\beta|-1} t ∣ γ ∣ = t ∣ β ∣ − 1 is obtained by taking k = γ 1 k=\gamma_{1} k = γ 1 , and equals
( α 1 γ 1 ) r α 1 − γ 1 v i v 1 γ 1 ∏ j = 2 n v j γ j = ( α 1 γ 1 ) r α 1 − γ 1 v β . (21) \binom{\alpha_{1}}{\gamma_{1}}r^{\alpha_{1}-\gamma_{1}}v_{i}v_{1}^{\gamma_{1}}\prod_{j=2}^{n}v_{j}^{\gamma_{j}}
=\binom{\alpha_{1}}{\gamma_{1}}r^{\alpha_{1}-\gamma_{1}}v^{\beta}. \tag*{(21)} ( γ 1 α 1 ) r α 1 − γ 1 v i v 1 γ 1 j = 2 ∏ n v j γ j = ( γ 1 α 1 ) r α 1 − γ 1 v β . (21)
Comparing the coefficient of t ∣ β ∣ − 1 t^{|\beta|-1} t ∣ β ∣ − 1 in (20) with (17) gives
b i , α , ∣ β ∣ − 1 ( r e 1 ) = ( α 1 γ 1 ) r d − ∣ β ∣ coeff v d ( v β ) . (22) b_{i,\alpha,|\beta|-1}(re_{1})=\binom{\alpha_{1}}{\gamma_{1}}r^{d-|\beta|}\operatorname{coeff}_{v_{d}}(v^{\beta}). \tag*{(22)} b i , α , ∣ β ∣ − 1 ( r e 1 ) = ( γ 1 α 1 ) r d − ∣ β ∣ coeff v d ( v β ) . (22)
Now let 0 ≠ ξ ∈ R N 0\ne\xi\in\mathbb{R}^{N} 0 = ξ ∈ R N . Since the coefficient vectors { coeff v d ( v β ) : 1 ≤ ∣ β ∣ ≤ d } \{\operatorname{coeff}_{v_{d}}(v^{\beta}):1\le|\beta|\le d\} { coeff v d ( v β ) : 1 ≤ ∣ β ∣ ≤ d } form a basis of R N \mathbb{R}^{N} R N , there always exists a monomial v β v^{\beta} v β such that
ξ T coeff v d ( v β ) ≠ 0. \xi^{\mathsf{T}}\operatorname{coeff}_{v_{d}}(v^{\beta})\ne0. ξ T coeff v d ( v β ) = 0.
Choose i i i such that β i > 0 \beta_i > 0 β i > 0 , and γ : = β − e i \gamma:= \beta- e_i γ := β − e i , α : = γ + ( d − ∣ β ∣ ) e 1 \alpha:= \gamma+ (d - |\beta|)e_1 α := γ + ( d − ∣ β ∣ ) e 1 . Using (22) and since ( α 1 γ 1 ) r d − ∣ β ∣ > 0 \left(\frac{\alpha_1}{\gamma_1}\right)r^{d-|\beta|} > 0 ( γ 1 α 1 ) r d − ∣ β ∣ > 0 , we obtain
ξ ⊤ b i , α , ∣ β ∣ − 1 ( r e 1 ) = ( α 1 γ 1 ) r d − ∣ β ∣ ξ ⊤ coeff v d ( v β ) ≠ 0. \xi^\top b_{i,\alpha,|\beta|-1}(re_1) = \binom{\alpha_1}{\gamma_1}r^{d-|\beta|}\xi^\top\operatorname{coeff}_{v_d}(v^\beta) \ne0. ξ ⊤ b i , α , ∣ β ∣ − 1 ( r e 1 ) = ( γ 1 α 1 ) r d − ∣ β ∣ ξ ⊤ coeff v d ( v β ) = 0.
Therefore { b i , α , k ( r e 1 ) } i , α , k \{b_{i,\alpha,k}(re_1)\}_{i,\alpha,k} { b i , α , k ( r e 1 ) } i , α , k satisfies (Spanning property). Consequently, by Lemma 3.3, Q 1 ( r e 1 ) ≻ 0 Q_1(re_1) \succ0 Q 1 ( r e 1 ) ≻ 0 .
It remains only to move the certificate from e 1 e_1 e 1 to an arbitrary nonzero s s s . Orthogonal invariance handles the direction and homogeneity handles the length.
Lemma 3.5 (Orthogonal transport and homogeneous scaling). According to Lemma 3.4,
R e 1 , d ( v ) = v d ( v ) ⊤ Q ( e 1 ) v d ( v ) , Q ( e 1 ) ≻ 0. R_{e_1,d}(v)=v_d(v)^\top Q(e_1)v_d(v),\qquad Q(e_1)\succ0. R e 1 , d ( v ) = v d ( v ) ⊤ Q ( e 1 ) v d ( v ) , Q ( e 1 ) ≻ 0. Then every s ≠ 0 s\ne0 s = 0 admits a positive-definite Gram matrix Q R ( s ) Q_R(s) Q R ( s ) . Moreover, if s = r u s=ru s = r u , ∥ u ∥ = 1 \lVert u\rVert=1 ∥ u ∥ = 1 , and 0 < r ≤ 1 0<r\le1 0 < r ≤ 1 , then
λ min ( Q R ( r u ) ) ≥ r 2 d − 2 λ min ( Q ( e 1 ) ) . (23) \lambda_{\min}(Q_R(ru))\ge r^{2d-2}\lambda_{\min}(Q(e_1)). \tag*{(23)} λ m i n ( Q R ( r u )) ≥ r 2 d − 2 λ m i n ( Q ( e 1 )) . (23) Proof. First transport the certificate from e 1 e_1 e 1 to an arbitrary unit direction. For u ∈ S n − 1 u\in S^{n-1} u ∈ S n − 1 , choose an orthogonal matrix O u O_u O u such that u = O u e 1 u=O_ue_1 u = O u e 1 . The Euclidean radial structure gives R u , d ( v ) = R e 1 , d ( O u ⊤ v ) R_{u,d}(v)=R_{e_1,d}(O_u^\top v) R u , d ( v ) = R e 1 , d ( O u ⊤ v ) . With the orthogonally normalized monomial blocks in Definition 1.2, there exists a block-orthogonal matrix T O u T_{O_u} T O u satisfying
v d ( O u ⊤ v ) = T O u v d ( v ) , T O u ⊤ T O u = I . (24) v_d(O_u^\top v)=T_{O_u}v_d(v),\qquad T_{O_u}^\top T_{O_u}=I. \tag*{(24)} v d ( O u ⊤ v ) = T O u v d ( v ) , T O u ⊤ T O u = I . (24) Define Q R ( u ) : = T O u ⊤ Q ( e 1 ) T O u Q_R(u):=T_{O_u}^\top Q(e_1)T_{O_u} Q R ( u ) := T O u ⊤ Q ( e 1 ) T O u . Then Q R ( u ) Q_R(u) Q R ( u ) is a Gram matrix for R u , d R_{u,d} R u , d , and
λ min ( Q R ( u ) ) = λ min ( Q ( e 1 ) ) = : μ n , d > 0. (25) \lambda_{\min}(Q_R(u))=\lambda_{\min}(Q(e_1))=:\mu_{n,d}>0. \tag*{(25)} λ m i n ( Q R ( u )) = λ m i n ( Q ( e 1 )) =: μ n , d > 0. (25) Thus the orthogonal matrix O u O_u O u transports the certificate between unit directions and preserves its Gram margin.
Now let s = r u s=ru s = r u , where r > 0 r>0 r > 0 . By homogeneity,
R r u , d ( v ) = r 2 d R u , d ( v r ) . (26) R_{ru,d}(v)=r^{2d}R_{u,d}\left(\frac{v}{r}\right). \tag*{(26)} R r u , d ( v ) = r 2 d R u , d ( r v ) . (26) Since the degree-k k k homogeneous block of v d ( v / r ) v_d(v/r) v d ( v / r ) equals r − k [ v ] k r^{-k}[v]_k r − k [ v ] k , define the block-diagonal matrix
E r : = diag ( r d − 1 I [ v ] 1 , r d − 2 I [ v ] 2 , … , r I [ v ] d − 1 , I [ v ] d ) , r d v d ( v r ) = E r v d ( v ) . (27) E_r:=\operatorname{diag}\left(r^{d-1}I_{[v]_1},r^{d-2}I_{[v]_2},\ldots,rI_{[v]_{d-1}},I_{[v]_d}\right),\qquad r^dv_d\left(\frac{v}{r}\right)=E_rv_d(v). \tag*{(27)} E r := diag ( r d − 1 I [ v ] 1 , r d − 2 I [ v ] 2 , … , r I [ v ] d − 1 , I [ v ] d ) , r d v d ( r v ) = E r v d ( v ) . (27) It follows that
R r u , d ( v ) = v d ( v ) ⊤ E r Q R ( u ) E r v d ( v ) , Q R ( r u ) : = E r Q R ( u ) E r . (28) R_{ru,d}(v)=v_d(v)^\top E_rQ_R(u)E_rv_d(v),\qquad Q_R(ru):=E_rQ_R(u)E_r. \tag*{(28)} R r u , d ( v ) = v d ( v ) ⊤ E r Q R ( u ) E r v d ( v ) , Q R ( r u ) := E r Q R ( u ) E r . (28) Since E r E_r E r is invertible, Q R ( r u ) ≻ 0 Q_R(ru)\succ0 Q R ( r u ) ≻ 0 for every r > 0 r>0 r > 0 . If 0 < r ≤ 1 0<r\le1 0 < r ≤ 1 , then λ min ( E r ) = r d − 1 \lambda_{\min}(E_r)=r^{d-1} λ m i n ( E r ) = r d − 1 , and therefore
λ min ( Q R ( r u ) ) ≥ λ min ( E r ) 2 λ min ( Q R ( u ) ) = r 2 d − 2 μ n , d . \lambda_{\min}(Q_R(ru))\ge\lambda_{\min}(E_r)^2\lambda_{\min}(Q_R(u))=r^{2d-2}\mu_{n,d}. λ m i n ( Q R ( r u )) ≥ λ m i n ( E r ) 2 λ m i n ( Q R ( u )) = r 2 d − 2 μ n , d . This proves (23) .
Example 3.1 (Example proof Q 1 ≻ 0 Q_1\succ0 Q 1 ≻ 0 for d = 2 d=2 d = 2 , n = 3 n=3 n = 3 ). For d = 2 d=2 d = 2 , we have
∥ s + t v ∥ 2 ∥ v ∥ 2 = ∑ i = 1 3 ∑ j = 1 3 [ v i ( s j + t v j ) ] 2 , \lVert s+tv\rVert^2\lVert v\rVert^2=\sum_{i=1}^{3}\sum_{j=1}^{3}\left[v_i(s_j+tv_j)\right]^2, ∥ s + t v ∥ 2 ∥ v ∥ 2 = i = 1 ∑ 3 j = 1 ∑ 3 [ v i ( s j + t v j ) ] 2 , and hence
2 I 1 ( v ) = 2 ∑ i , j = 1 3 ∫ 0 1 ( 1 − t ) [ v i ( s j + t v j ) ] 2 d t . 2I_1(v)=2\sum_{i,j=1}^{3}\int_0^1(1-t)\left[v_i(s_j+tv_j)\right]^2\,dt. 2 I 1 ( v ) = 2 i , j = 1 ∑ 3 ∫ 0 1 ( 1 − t ) [ v i ( s j + t v j ) ] 2 d t . For each i , j i,j i , j , let a i j ( s , t ) a_{ij}(s,t) a ij ( s , t ) be the coefficient vector of v i ( s j + t v j ) v_i(s_j+tv_j) v i ( s j + t v j ) with respect to the nonconstant monomial vector
z 2 ( v ) = ( v 1 v 2 v 3 v 1 2 v 1 v 2 v 1 v 3 v 2 2 v 2 v 3 v 3 2 ) ⊤ . z_2(v)=\left(v_1\quad v_2\quad v_3\quad v_1^2\quad v_1v_2\quad v_1v_3\quad v_2^2\quad v_2v_3\quad v_3^2\right)^\top. z 2 ( v ) = ( v 1 v 2 v 3 v 1 2 v 1 v 2 v 1 v 3 v 2 2 v 2 v 3 v 3 2 ) ⊤ .
Then
Q 1 ( s ) = 2 ∑ i = 1 3 ∑ j = 1 3 ∫ 0 1 ( 1 − t ) a i j ( s , t ) a i j ( s , t ) T d t , 2 I 1 ( v ) = z 2 ( v ) T Q 1 ( s ) z 2 ( v ) . Q_1(s)=2\sum_{i=1}^{3}\sum_{j=1}^{3}\int_{0}^{1}(1-t)a_{ij}(s,t)a_{ij}(s,t)^{\mathsf T}\,dt,\qquad2I_1(v)=z_2(v)^{\mathsf T}Q_1(s)z_2(v). Q 1 ( s ) = 2 i = 1 ∑ 3 j = 1 ∑ 3 ∫ 0 1 ( 1 − t ) a ij ( s , t ) a ij ( s , t ) T d t , 2 I 1 ( v ) = z 2 ( v ) T Q 1 ( s ) z 2 ( v ) .
It suffices to consider s = r e 1 = ( r , 0 , 0 ) s=re_1=(r,0,0) s = r e 1 = ( r , 0 , 0 ) , r > 0 r>0 r > 0 . Then
v i ( s j + t v j ) = { v i ( r + t v 1 ) , j = 1 , t v i v j , j = 2 , 3. v_i(s_j+tv_j)=
\begin{cases}
v_i(r+tv_1), & j=1,\\
tv_iv_j, & j=2,3.
\end{cases} v i ( s j + t v j ) = { v i ( r + t v 1 ) , t v i v j , j = 1 , j = 2 , 3.
With respect to the above ordering of z 2 ( v ) z_2(v) z 2 ( v ) , we have
a 11 ( t ) = r e v 1 + t e v 1 2 , a 21 ( t ) = r e v 2 + t e v 1 v 2 , a 31 ( t ) = r e v 3 + t e v 1 v 3 , a 12 ( t ) = t e v 1 v 2 , a 22 ( t ) = t e v 2 2 , a 32 ( t ) = t e v 2 v 3 , a 13 ( t ) = t e v 1 v 3 , a 23 ( t ) = t e v 2 v 3 , a 33 ( t ) = t e v 3 2 . \begin{aligned}
a_{11}(t)&=re_{v_1}+te_{v_1^2}, & a_{21}(t)&=re_{v_2}+te_{v_1v_2}, & a_{31}(t)&=re_{v_3}+te_{v_1v_3},\\
a_{12}(t)&=te_{v_1v_2}, & a_{22}(t)&=te_{v_2^2}, & a_{32}(t)&=te_{v_2v_3},\\
a_{13}(t)&=te_{v_1v_3}, & a_{23}(t)&=te_{v_2v_3}, & a_{33}(t)&=te_{v_3^2}.
\end{aligned} a 11 ( t ) a 12 ( t ) a 13 ( t ) = r e v 1 + t e v 1 2 , = t e v 1 v 2 , = t e v 1 v 3 , a 21 ( t ) a 22 ( t ) a 23 ( t ) = r e v 2 + t e v 1 v 2 , = t e v 2 2 , = t e v 2 v 3 , a 31 ( t ) a 32 ( t ) a 33 ( t ) = r e v 3 + t e v 1 v 3 , = t e v 2 v 3 , = t e v 3 2 .
Note that since α = { e 1 , e 2 , e 3 } \alpha=\{e_1,e_2,e_3\} α = { e 1 , e 2 , e 3 } here, we denote a i , α ( r e 1 , t ) = a i j ( t ) a_{i,\alpha}(re_1,t)=a_{ij}(t) a i , α ( r e 1 , t ) = a ij ( t ) for abbreviation. With respect to the above ordering of z 2 ( v ) z_2(v) z 2 ( v ) , the nine coefficient vectors { a 11 ( t ) , a 21 ( t ) , a 31 ( t ) … a 33 ( t ) } \{a_{11}(t),a_{21}(t),a_{31}(t)\ldots a_{33}(t)\} { a 11 ( t ) , a 21 ( t ) , a 31 ( t ) … a 33 ( t )} are
( r 0 0 t 0 0 0 0 0 ) , ( 0 r 0 0 t 0 0 0 0 ) , ( 0 0 r 0 0 t 0 0 0 ) , ( 0 0 0 t 0 0 0 0 0 ) , ( 0 0 0 0 0 0 t 0 0 ) , ( 0 0 0 0 0 0 0 t 0 ) , ( 0 0 0 0 0 0 0 0 t ) , ( 0 0 0 0 0 0 0 t 0 ) , ( 0 0 0 0 0 0 0 0 t ) . \begin{pmatrix}r\\0\\0\\t\\0\\0\\0\\0\\0\end{pmatrix},
\begin{pmatrix}0\\r\\0\\0\\t\\0\\0\\0\\0\end{pmatrix},
\begin{pmatrix}0\\0\\r\\0\\0\\t\\0\\0\\0\end{pmatrix},
\begin{pmatrix}0\\0\\0\\t\\0\\0\\0\\0\\0\end{pmatrix},
\begin{pmatrix}0\\0\\0\\0\\0\\0\\t\\0\\0\end{pmatrix},
\begin{pmatrix}0\\0\\0\\0\\0\\0\\0\\t\\0\end{pmatrix},
\begin{pmatrix}0\\0\\0\\0\\0\\0\\0\\0\\t\end{pmatrix},
\begin{pmatrix}0\\0\\0\\0\\0\\0\\0\\t\\0\end{pmatrix},
\begin{pmatrix}0\\0\\0\\0\\0\\0\\0\\0\\t\end{pmatrix}. r 0 0 t 0 0 0 0 0 , 0 r 0 0 t 0 0 0 0 , 0 0 r 0 0 t 0 0 0 , 0 0 0 t 0 0 0 0 0 , 0 0 0 0 0 0 t 0 0 , 0 0 0 0 0 0 0 t 0 , 0 0 0 0 0 0 0 0 t , 0 0 0 0 0 0 0 t 0 , 0 0 0 0 0 0 0 0 t .
Since t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) , the last six vectors with j = 2 , 3 j=2,3 j = 2 , 3 , directly generate the five distinct quadratic directions
e v 1 v 2 , e v 1 v 3 , e v 2 2 , e v 2 v 3 , e v 3 2 , e_{v_1v_2},\quad e_{v_1v_3},\quad e_{v_2^2},\quad e_{v_2v_3},\quad e_{v_3^2}, e v 1 v 2 , e v 1 v 3 , e v 2 2 , e v 2 v 3 , e v 3 2 ,
where the direction e v 2 v 3 e_{v_2v_3} e v 2 v 3 appears twice, through both a 32 ( t ) = a 23 ( t ) = t e v 2 v 3 a_{32}(t)=a_{23}(t)=te_{v_2v_3} a 32 ( t ) = a 23 ( t ) = t e v 2 v 3 . The remaining quadratic direction e v 1 2 e_{v_1^2} e v 1 2 is obtained from the j = 1 j=1 j = 1 vectors. Indeed, choosing two distinct values t 0 , t 1 ∈ ( 0 , 1 ) t_0,t_1\in(0,1) t 0 , t 1 ∈ ( 0 , 1 ) , we have
a 11 ( t 1 ) − a 11 ( t 0 ) = ( t 1 − t 0 ) e v 1 2 . a_{11}(t_1)-a_{11}(t_0)=(t_1-t_0)e_{v_1^2}. a 11 ( t 1 ) − a 11 ( t 0 ) = ( t 1 − t 0 ) e v 1 2 .
Hence e v 1 2 e_{v_1^2} e v 1 2 also belongs to the span. Therefore all six quadratic directions
e v 1 2 , e v 1 v 2 , e v 1 v 3 , e v 2 2 , e v 2 v 3 , e v 3 2 e_{v_1^2},\quad e_{v_1v_2},\quad e_{v_1v_3},\quad e_{v_2^2},\quad e_{v_2v_3},\quad e_{v_3^2} e v 1 2 , e v 1 v 2 , e v 1 v 3 , e v 2 2 , e v 2 v 3 , e v 3 2
belong to the span. Finally, since
a 11 ( t 0 ) = r e v 1 + t 0 e v 1 2 , a 21 ( t 0 ) = r e v 2 + t 0 e v 1 v 2 , a 31 ( t 0 ) = r e v 3 + t 0 e v 1 v 3 , a_{11}(t_0)=re_{v_1}+t_0e_{v_1^2},\qquad a_{21}(t_0)=re_{v_2}+t_0e_{v_1v_2},\qquad a_{31}(t_0)=re_{v_3}+t_0e_{v_1v_3}, a 11 ( t 0 ) = r e v 1 + t 0 e v 1 2 , a 21 ( t 0 ) = r e v 2 + t 0 e v 1 v 2 , a 31 ( t 0 ) = r e v 3 + t 0 e v 1 v 3 ,
and r > 0 r>0 r > 0 , the linear directions
e v 1 , e v 2 , e v 3 e_{v_1},\quad e_{v_2},\quad e_{v_3} e v 1 , e v 2 , e v 3
also belong to the span. Hence, the vectors a i j ( r e 1 , t ) a_{ij}(re_1,t) a ij ( r e 1 , t ) , i , j = 1 , 2 , 3 i,j=1,2,3 i , j = 1 , 2 , 3 , t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) , span the full coefficient space generated by monomials of degrees 1 and 2. Namely,
span { a i j ( r e 1 , t ) : i , j = 1 , 2 , 3 , t ∈ ( 0 , 1 ) } = span { e v 1 , e v 2 , e v 3 , e v 1 2 , e v 1 v 2 , e v 1 v 3 , e v 2 2 , e v 2 v 3 , e v 3 2 } = R 9 . \boxed{\operatorname{span}\{a_{ij}(re_1,t):i,j=1,2,3,\ t\in(0,1)\}=\operatorname{span}\{e_{v_1},e_{v_2},e_{v_3},e_{v_1^2},e_{v_1v_2},e_{v_1v_3},e_{v_2^2},e_{v_2v_3},e_{v_3^2}\}=\mathbb{R}^{9}.} span { a ij ( r e 1 , t ) : i , j = 1 , 2 , 3 , t ∈ ( 0 , 1 )} = span { e v 1 , e v 2 , e v 3 , e v 1 2 , e v 1 v 2 , e v 1 v 3 , e v 2 2 , e v 2 v 3 , e v 3 2 } = R 9 .
Therefore, for any coefficient vector ξ \xi ξ ,
ξ T Q 1 ( s ) ξ = 2 ∑ i = 1 3 ∑ j = 1 3 ∫ 0 1 ( 1 − t ) ( ξ T a i j ( s , t ) ) 2 d t . \xi^{\mathsf T}Q_1(s)\xi=2\sum_{i=1}^{3}\sum_{j=1}^{3}\int_{0}^{1}(1-t)(\xi^{\mathsf T}a_{ij}(s,t))^2\,dt. ξ T Q 1 ( s ) ξ = 2 i = 1 ∑ 3 j = 1 ∑ 3 ∫ 0 1 ( 1 − t ) ( ξ T a ij ( s , t ) ) 2 d t .
If ξ T Q 1 ( s ) ξ = 0 \xi^{\mathsf T}Q_1(s)\xi=0 ξ T Q 1 ( s ) ξ = 0 , then all nonnegative integrands vanish identically, so ξ \xi ξ is orthogonal to all vectors a i j ( s , t ) a_{ij}(s,t) a ij ( s , t ) . Since these vectors span the full coefficient space, this implies ξ = 0 \xi=0 ξ = 0 . Thus Q 1 ( s ) > 0 Q_1(s)>0 Q 1 ( s ) > 0 .
Example 3.2 (d = 3 d=3 d = 3 , n = 3 n=3 n = 3 ). Let s = r e 1 = ( r , 0 , 0 ) s=r e_1=(r,0,0) s = r e 1 = ( r , 0 , 0 ) , r > 0 r>0 r > 0 . For d = 3 d=3 d = 3 , we have ∣ α ∣ = d − 1 = 2 |\alpha|=d-1=2 ∣ α ∣ = d − 1 = 2 . We use the nonconstant monomial vector
z 3 ( v ) = ( v 1 , v 2 , v 3 , v 1 2 , v 1 v 2 , v 1 v 3 , v 2 2 , v 2 v 3 , v 3 2 , v 1 2 v 2 , v 1 2 v 3 , v 1 v 2 2 , v 1 v 2 v 3 , v 1 v 3 2 , v 2 2 v 3 , v 2 v 3 2 , v 1 3 , v 2 3 , v 3 3 ) T . z_3(v)=\left(v_1,v_2,v_3,v_1^2,v_1v_2,v_1v_3,v_2^2,v_2v_3,v_3^2,v_1^2v_2,v_1^2v_3,v_1v_2^2,v_1v_2v_3,v_1v_3^2,v_2^2v_3,v_2v_3^2,v_1^3,v_2^3,v_3^3\right)^{\mathsf T}. z 3 ( v ) = ( v 1 , v 2 , v 3 , v 1 2 , v 1 v 2 , v 1 v 3 , v 2 2 , v 2 v 3 , v 3 2 , v 1 2 v 2 , v 1 2 v 3 , v 1 v 2 2 , v 1 v 2 v 3 , v 1 v 3 2 , v 2 2 v 3 , v 2 v 3 2 , v 1 3 , v 2 3 , v 3 3 ) T .
For each i = 1 , 2 , 3 i=1,2,3 i = 1 , 2 , 3 and each multi-index ∣ α ∣ = 2 |\alpha|=2 ∣ α ∣ = 2 , let a i , α ( t ) a_{i,\alpha}(t) a i , α ( t ) denote the coefficient vector of
v i ( r e 1 + t v ) α v_i(re_1+tv)^\alpha v i ( r e 1 + t v ) α
with respect to z 3 ( v ) z_3(v) z 3 ( v ) . The possible multi-indices are
α : = { 2 e 1 , e 1 + e 2 , e 1 + e 3 , 2 e 2 , e 2 + e 3 , 2 e 3 } . \alpha:=\{2e_1,\ e_1+e_2,\ e_1+e_3,\ 2e_2,\ e_2+e_3,\ 2e_3\}. α := { 2 e 1 , e 1 + e 2 , e 1 + e 3 , 2 e 2 , e 2 + e 3 , 2 e 3 } .
The corresponding polynomials and coefficient vectors have the form
v i ( r e 1 + t v ) 2 e 1 = r 2 v i + 2 r t v i v 1 + t 2 v i v 1 2 , a i , 2 e 1 ( t ) = r 2 e v i + 2 r t e v i v 1 + t 2 e v i v 1 2 , v i ( r e 1 + t v ) e 1 + e 2 = r t v i v 2 + t 2 v i v 1 v 2 , a i , e 1 + e 2 ( t ) = r t e v i v 2 + t 2 e v i v 1 v 2 , v i ( r e 1 + t v ) e 1 + e 3 = r t v i v 3 + t 2 v i v 1 v 3 , a i , e 1 + e 3 ( t ) = r t e v i v 3 + t 2 e v i v 1 v 3 , v i ( r e 1 + t v ) 2 e 2 = t 2 v i v 2 2 , a i , 2 e 2 ( t ) = t 2 e v i v 2 2 , v i ( r e 1 + t v ) e 2 + e 3 = t 2 v i v 2 v 3 , a i , e 2 + e 3 ( t ) = t 2 e v i v 2 v 3 , v i ( r e 1 + t v ) 2 e 3 = t 2 v i v 3 2 , a i , 2 e 3 ( t ) = t 2 e v i v 3 2 . \begin{aligned}
v_i(re_1+tv)^{2e_1}&=r^2v_i+2rtv_iv_1+t^2v_iv_1^2,
& a_{i,2e_1}(t)&=r^2e_{v_i}+2rt\,e_{v_iv_1}+t^2e_{v_iv_1^2},\\
v_i(re_1+tv)^{e_1+e_2}&=rtv_iv_2+t^2v_iv_1v_2,
& a_{i,e_1+e_2}(t)&=rt\,e_{v_iv_2}+t^2e_{v_iv_1v_2},\\
v_i(re_1+tv)^{e_1+e_3}&=rtv_iv_3+t^2v_iv_1v_3,
& a_{i,e_1+e_3}(t)&=rt\,e_{v_iv_3}+t^2e_{v_iv_1v_3},\\
v_i(re_1+tv)^{2e_2}&=t^2v_iv_2^2,
& a_{i,2e_2}(t)&=t^2e_{v_iv_2^2},\\
v_i(re_1+tv)^{e_2+e_3}&=t^2v_iv_2v_3,
& a_{i,e_2+e_3}(t)&=t^2e_{v_iv_2v_3},\\
v_i(re_1+tv)^{2e_3}&=t^2v_iv_3^2,
& a_{i,2e_3}(t)&=t^2e_{v_iv_3^2}.
\end{aligned} v i ( r e 1 + t v ) 2 e 1 v i ( r e 1 + t v ) e 1 + e 2 v i ( r e 1 + t v ) e 1 + e 3 v i ( r e 1 + t v ) 2 e 2 v i ( r e 1 + t v ) e 2 + e 3 v i ( r e 1 + t v ) 2 e 3 = r 2 v i + 2 r t v i v 1 + t 2 v i v 1 2 , = r t v i v 2 + t 2 v i v 1 v 2 , = r t v i v 3 + t 2 v i v 1 v 3 , = t 2 v i v 2 2 , = t 2 v i v 2 v 3 , = t 2 v i v 3 2 , a i , 2 e 1 ( t ) a i , e 1 + e 2 ( t ) a i , e 1 + e 3 ( t ) a i , 2 e 2 ( t ) a i , e 2 + e 3 ( t ) a i , 2 e 3 ( t ) = r 2 e v i + 2 r t e v i v 1 + t 2 e v i v 1 2 , = r t e v i v 2 + t 2 e v i v 1 v 2 , = r t e v i v 3 + t 2 e v i v 1 v 3 , = t 2 e v i v 2 2 , = t 2 e v i v 2 v 3 , = t 2 e v i v 3 2 .
Note that we denote a i , α ( r e 1 , t ) = a i , α ( t ) a_{i,\alpha}(re_1,t)=a_{i,\alpha}(t) a i , α ( r e 1 , t ) = a i , α ( t ) for abbreviation. Thus the t 0 t^0 t 0 -coefficients generate the degree-one directions
e v 1 , e v 2 , e v 3 . e_{v_1},\quad e_{v_2},\quad e_{v_3}. e v 1 , e v 2 , e v 3 .
More explicitly, each vector a i , α ( t ) a_{i,\alpha}(t) a i , α ( t ) is a vector-valued polynomial of degree at most two:
a i , α ( t ) = b 0 + t b 1 + t 2 b 2 . a_{i,\alpha}(t)=b_0+tb_1+t^2b_2. a i , α ( t ) = b 0 + t b 1 + t 2 b 2 .
Let ξ ∈ R 19 \xi\in\mathbb{R}^{19} ξ ∈ R 19 be orthogonal to a i , α ( t ) a_{i,\alpha}(t) a i , α ( t ) for every i , α i,\alpha i , α and every t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) . Then
t ⟼ ξ T a i , α ( t ) t\longmapsto\xi^{\mathsf T}a_{i,\alpha}(t) t ⟼ ξ T a i , α ( t )
is a scalar polynomial which vanishes on ( 0 , 1 ) (0,1) ( 0 , 1 ) , and hence it vanishes identically. Therefore ξ \xi ξ is orthogonal to every coefficient vector b 0 , b 1 , b 2 b_0,b_1,b_2 b 0 , b 1 , b 2 . By the displayed expansions above, the t 0 t^0 t 0 -, t 1 t^1 t 1 -, and t 2 t^2 t 2 -coefficients generate, respectively, all monomial coefficient directions of degrees one, two, and three. Thus ξ = 0 \xi=0 ξ = 0 , which proves that the value vectors a i , α ( t ) a_{i,\alpha}(t) a i , α ( t ) , with t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) , span the full coefficient space. Therefore,
span { a i , α ( t ) : i = 1 , 2 , 3 , ∣ α ∣ = 2 , t ∈ ( 0 , 1 ) } = span { e v β : 1 ≤ ∣ β ∣ ≤ 3 } = R 19 . \boxed{\operatorname{span}\{a_{i,\alpha}(t):i=1,2,3,\ |\alpha|=2,\ t\in(0,1)\}=\operatorname{span}\{e_{v_\beta}:1\leq|\beta|\leq3\}=\mathbb{R}^{19}.} span { a i , α ( t ) : i = 1 , 2 , 3 , ∣ α ∣ = 2 , t ∈ ( 0 , 1 )} = span { e v β : 1 ≤ ∣ β ∣ ≤ 3 } = R 19 .
That is, the vectors a i , α ( t ) a_{i,\alpha}(t) a i , α ( t ) span the full nonconstant coefficient space generated by monomials of degrees 1 , 2 1,2 1 , 2 , and 3 3 3 .
The radial term I 2 I_2 I 2 is PSD but has no strict Gram margin Although I 2 ( v ) I_2(v) I 2 ( v ) in (9) contains strong radial terms, it is not, by itself, strictly positive on the full nonconstant monomial vector v d ( v ) v_d(v) v d ( v ) . For reference, when d = 2 d=2 d = 2 ,
I 1 ( v ) = 1 2 ∥ s ∥ 2 ∥ v ∥ 2 + 1 3 ( s T v ) ∥ v ∥ 2 + 1 12 ∥ v ∥ 4 , I 2 ( v ) = 1 2 ( s T v ) 2 + 1 3 ( s T v ) ∥ v ∥ 2 + 1 12 ∥ v ∥ 4 . I_1(v)=\frac{1}{2}\|s\|^2\|v\|^2+\frac{1}{3}(s^{\mathsf T}v)\|v\|^2+\frac{1}{12}\|v\|^4,
\qquad
I_2(v)=\frac{1}{2}(s^{\mathsf T}v)^2+\frac{1}{3}(s^{\mathsf T}v)\|v\|^2+\frac{1}{12}\|v\|^4. I 1 ( v ) = 2 1 ∥ s ∥ 2 ∥ v ∥ 2 + 3 1 ( s T v ) ∥ v ∥ 2 + 12 1 ∥ v ∥ 4 , I 2 ( v ) = 2 1 ( s T v ) 2 + 3 1 ( s T v ) ∥ v ∥ 2 + 12 1 ∥ v ∥ 4 .
When d = 3 d=3 d = 3 ,
I 1 ( v ) = 1 2 ∥ s ∥ 4 ∥ v ∥ 2 + 2 3 ∥ s ∥ 2 ( s T v ) ∥ v ∥ 2 + 1 6 ∥ s ∥ 2 ∥ v ∥ 4 + 1 3 ( s T v ) 2 ∥ v ∥ 2 + 1 5 ( s T v ) ∥ v ∥ 4 + 1 30 ∥ v ∥ 6 . I_1(v)=\frac{1}{2}\|s\|^4\|v\|^2+\frac{2}{3}\|s\|^2(s^{\mathsf T}v)\|v\|^2+\frac{1}{6}\|s\|^2\|v\|^4+\frac{1}{3}(s^{\mathsf T}v)^2\|v\|^2+\frac{1}{5}(s^{\mathsf T}v)\|v\|^4+\frac{1}{30}\|v\|^6. I 1 ( v ) = 2 1 ∥ s ∥ 4 ∥ v ∥ 2 + 3 2 ∥ s ∥ 2 ( s T v ) ∥ v ∥ 2 + 6 1 ∥ s ∥ 2 ∥ v ∥ 4 + 3 1 ( s T v ) 2 ∥ v ∥ 2 + 5 1 ( s T v ) ∥ v ∥ 4 + 30 1 ∥ v ∥ 6 .
whereas
I 2 ( v ) = 1 2 ∥ s ∥ 2 ( s ⊤ v ) 2 + 1 3 ∥ s ∥ 2 ( s ⊤ v ) ∥ v ∥ 2 + 1 12 ∥ s ∥ 2 ∥ v ∥ 4 + 1 3 ( s ⊤ v ) 3 + 5 12 ( s ⊤ v ) 2 ∥ v ∥ 2 + 1 5 ( s ⊤ v ) ∥ v ∥ 4 + 1 30 ∥ v ∥ 6 . I_2(v)=\frac{1}{2}\lVert s\rVert^2(s^\top v)^2+\frac{1}{3}\lVert s\rVert^2(s^\top v)\lVert v\rVert^2+\frac{1}{12}\lVert s\rVert^2\lVert v\rVert^4+\frac{1}{3}(s^\top v)^3+\frac{5}{12}(s^\top v)^2\lVert v\rVert^2+\frac{1}{5}(s^\top v)\lVert v\rVert^4+\frac{1}{30}\lVert v\rVert^6. I 2 ( v ) = 2 1 ∥ s ∥ 2 ( s ⊤ v ) 2 + 3 1 ∥ s ∥ 2 ( s ⊤ v ) ∥ v ∥ 2 + 12 1 ∥ s ∥ 2 ∥ v ∥ 4 + 3 1 ( s ⊤ v ) 3 + 12 5 ( s ⊤ v ) 2 ∥ v ∥ 2 + 5 1 ( s ⊤ v ) ∥ v ∥ 4 + 30 1 ∥ v ∥ 6 .
Thus I 2 I_2 I 2 indeed contributes more visibly radial terms, such as
and
∥ s ∥ 2 ( s ⊤ v ) 2 . \lVert s\rVert^2(s^\top v)^2. ∥ s ∥ 2 ( s ⊤ v ) 2 .
By contrast, I 1 I_1 I 1 contains the isotropic factor ∥ v ∥ 2 \lVert v\rVert^2 ∥ v ∥ 2 and its associated squared terms span all nonconstant monomial directions. Hence I 1 I_1 I 1 , rather than I 2 I_2 I 2 , is the source of the strict Gram margin. More generally, we can prove that if n ≥ 2 n\ge2 n ≥ 2 , take w ⊥ s w\perp s w ⊥ s , ∥ w ∥ = 1 \lVert w\rVert=1 ∥ w ∥ = 1 , and v = τ w v=\tau w v = τ w . Then ( s + t τ w ) ⊤ ( τ w ) = t τ 2 (s+t\tau w)^\top(\tau w)=t\tau^2 ( s + t τ w ) ⊤ ( τ w ) = t τ 2 , and hence
I 2 ( τ w ) = O ( τ 4 ) as τ → 0. I_2(\tau w)=O(\tau^4)\qquad\text{as }\tau\to0. I 2 ( τ w ) = O ( τ 4 ) as τ → 0.
On the other hand, since v d ( τ w ) \mathbf{v}_d(\tau w) v d ( τ w ) contains linear monomials,
∥ v d ( τ w ) ∥ 2 = O ( τ 2 ) . \lVert\mathbf{v}_d(\tau w)\rVert^2=O(\tau^2). ∥ v d ( τ w ) ∥ 2 = O ( τ 2 ) .
Thus no bound of the form
I 2 ( v ) ≥ μ ∥ v d ( v ) ∥ 2 , μ > 0 , I_2(v)\ge\mu\lVert\mathbf{v}_d(v)\rVert^2,\qquad\mu>0, I 2 ( v ) ≥ μ ∥ v d ( v ) ∥ 2 , μ > 0 ,
can hold. Therefore I 2 I_2 I 2 is positive semidefinite but not strictly positive on the full coefficient space. The strict Gram margin is instead provided by I 1 I_1 I 1 .
More generally, the spanning viewpoint of Lemma 3.3 shows that this is structural. Every square in I 2 I_2 I 2 carries the common factor ( s + t v ) ⊤ v (s+tv)^\top v ( s + t v ) ⊤ v ; at s = e 1 s=e_1 s = e 1 the generators are
q ~ α , t ( v ) = ( 1 + t v 1 ) α 1 ∏ j ≥ 2 ( t v j ) α j ( v 1 + t ∥ v ∥ 2 ) , ∣ α ∣ = d − 2 , \widetilde{q}_{\alpha,t}(v)=(1+tv_1)^{\alpha_1}\prod_{j\ge2}(tv_j)^{\alpha_j}(v_1+t\lVert v\rVert^2),\qquad\lvert\alpha\rvert=d-2, q α , t ( v ) = ( 1 + t v 1 ) α 1 j ≥ 2 ∏ ( t v j ) α j ( v 1 + t ∥ v ∥ 2 ) , ∣ α ∣ = d − 2 ,
whose only linear term is a multiple of v 1 v_1 v 1 . For n ≥ 2 n\ge2 n ≥ 2 , the coefficient vectors a ~ α ( e 1 , t ) \widetilde{a}_\alpha(e_1,t) a α ( e 1 , t ) therefore never reach the linear monomials v 2 , … , v n v_2,\ldots,v_n v 2 , … , v n : these coordinate directions lie in the kernel of Q 2 ( e 1 ) Q_2(e_1) Q 2 ( e 1 ) , and the spanning property fails. Hence Q 2 ( e 1 ) ⪰ 0 Q_2(e_1)\succeq0 Q 2 ( e 1 ) ⪰ 0 but Q 2 ( e 1 ) ⊁ 0 Q_2(e_1)\not\succ0 Q 2 ( e 1 ) ≻ 0 . In fact, since each t ↦ a ~ α ( e 1 , t ) t\mapsto\widetilde{a}_\alpha(e_1,t) t ↦ a α ( e 1 , t ) is a polynomial of degree at most d − 1 d-1 d − 1 ,
rank Q 2 ( e 1 ) ≤ d ( n + d − 3 d − 2 ) , \operatorname{rank}Q_2(e_1)\le d\binom{n+d-3}{d-2}, rank Q 2 ( e 1 ) ≤ d ( d − 2 n + d − 3 ) ,
which is O ( n d − 2 ) O(n^{d-2}) O ( n d − 2 ) for fixed d d d , far below N = Θ ( n d ) N=\Theta(n^d) N = Θ ( n d ) ; by orthogonal invariance, the same holds at every s ≠ 0 s\ne0 s = 0 . The contrast with I 1 I_1 I 1 is precisely the spanning mechanism: the squares in I 1 I_1 I 1 carry the prefactors v i v_i v i for every coordinate i i i , whereas the squares in I 2 I_2 I 2 share a single radial factor. For n = 1 n=1 n = 1 , the generators v 1 ( 1 + t v 1 ) d − 1 v_1(1+tv_1)^{d-1} v 1 ( 1 + t v 1 ) d − 1 do span v 1 , … , v 1 d v_1,\ldots,v_1^d v 1 , … , v 1 d and Q 2 ≻ 0 Q_2\succ0 Q 2 ≻ 0 , so the failure is a genuinely multivariate phenomenon. The strict Gram margin is therefore necessarily supplied by I 1 I_1 I 1 .
Strict Gram Margins Beyond Euclidean Regularization
The strict-Gram argument is not limited to the Euclidean norm. What matters is that the Bregman remainder can be written as an integral of polynomial squares and that, together, those squares cover all monomial directions. We first record this principle and then apply it to several other regularizers, including examples where the property holds and examples where it fails.
Corollary 3.1 (Polynomial integral representations with a strict Gram margin). Let z ( v ) ∈ R N z(v) \in\mathbb{R}^{N} z ( v ) ∈ R N be a fixed monomial vector. Suppose that, for each ℓ \ell ℓ ,
p ℓ ( t , v ) = a ℓ ( t ) T z ( v ) , p_{\ell}(t,v) = a_{\ell}(t)^{\mathsf{T}}z(v), p ℓ ( t , v ) = a ℓ ( t ) T z ( v ) , where a ℓ ( t ) ∈ R N a_{\ell}(t) \in\mathbb{R}^{N} a ℓ ( t ) ∈ R N is a vector-valued polynomial in t t t ,
a ℓ ( t ) = ∑ k = 0 L ℓ b ℓ , k t k , b ℓ , k ∈ R N . a_{\ell}(t) = \sum_{k=0}^{L_{\ell}} b_{\ell,k}t^{k}, \qquad b_{\ell,k} \in\mathbb{R}^{N}. a ℓ ( t ) = k = 0 ∑ L ℓ b ℓ , k t k , b ℓ , k ∈ R N . Suppose that the coefficient vectors satisfy the analogue of (Spanning property), namely,
∀ 0 ≠ ξ ∈ R N , ∃ ℓ , 0 ≤ k ≤ L ℓ s.t. ξ T b ℓ , k ≠ 0. (29) \forall\, 0 \ne\xi\in\mathbb{R}^{N}, \qquad\exists\, \ell,\ 0 \le k \le L_{\ell}\ \text{s.t.}\ \xi^{\mathsf{T}}b_{\ell,k} \ne0. \tag*{(29)} ∀ 0 = ξ ∈ R N , ∃ ℓ , 0 ≤ k ≤ L ℓ s.t. ξ T b ℓ , k = 0. (29) Let c ℓ > 0 c_{\ell} > 0 c ℓ > 0 , and let w : ( 0 , 1 ) → R + w:(0,1) \to\mathbb{R}_{+} w : ( 0 , 1 ) → R + be nonnegative and strictly positive on a set of positive measure. Then
Q : = ∑ ℓ c ℓ ∫ 0 1 w ( t ) a ℓ ( t ) a ℓ ( t ) T d t Q := \sum_{\ell} c_{\ell}\int_{0}^{1} w(t)a_{\ell}(t)a_{\ell}(t)^{\mathsf{T}}\,\mathrm{d}t Q := ℓ ∑ c ℓ ∫ 0 1 w ( t ) a ℓ ( t ) a ℓ ( t ) T d t satisfies Q ≻ 0 Q \succ0 Q ≻ 0 . Equivalently, ∑ ℓ c ℓ ∫ 0 1 w ( t ) p ℓ ( t , v ) 2 d t = z ( v ) T Q z ( v ) \sum_{\ell} c_{\ell}\int_{0}^{1} w(t)p_{\ell}(t,v)^{2}\,\mathrm{d}t = z(v)^{\mathsf{T}}Qz(v) ∑ ℓ c ℓ ∫ 0 1 w ( t ) p ℓ ( t , v ) 2 d t = z ( v ) T Q z ( v ) has a strict Gram representation on z ( v ) z(v) z ( v ) .
Proof. This follows from the same argument as Lemma 3.3 . Let 0 ≠ ξ ∈ R N 0 \ne\xi\in\mathbb{R}^{N} 0 = ξ ∈ R N . By (29) , there exist ℓ \ell ℓ and k k k such that ξ T b ℓ , k ≠ 0 \xi^{\mathsf{T}}b_{\ell,k} \ne0 ξ T b ℓ , k = 0 . Hence ξ T a ℓ ( t ) = ∑ k = 0 L ℓ ξ T b ℓ , k t k \xi^{\mathsf{T}}a_{\ell}(t) = \sum_{k=0}^{L_{\ell}}\xi^{\mathsf{T}}b_{\ell,k}t^{k} ξ T a ℓ ( t ) = ∑ k = 0 L ℓ ξ T b ℓ , k t k is not identically zero as a polynomial in t t t . Therefore, ∫ 0 1 w ( t ) [ ξ T a ℓ ( t ) ] 2 d t > 0 \int_{0}^{1}w(t)[\xi^{\mathsf{T}}a_{\ell}(t)]^{2}\,\mathrm{d}t > 0 ∫ 0 1 w ( t ) [ ξ T a ℓ ( t ) ] 2 d t > 0 . Since c ℓ > 0 c_{\ell} > 0 c ℓ > 0 and all the remaining terms are nonnegative, ξ T Q ξ = ∑ ℓ c ℓ ∫ 0 1 w ( t ) [ ξ T a ℓ ( t ) ] 2 d t > 0 \xi^{\mathsf{T}}Q\xi= \sum_{\ell}c_{\ell}\int_{0}^{1}w(t)[\xi^{\mathsf{T}}a_{\ell}(t)]^{2}\,\mathrm{d}t > 0 ξ T Q ξ = ∑ ℓ c ℓ ∫ 0 1 w ( t ) [ ξ T a ℓ ( t ) ] 2 d t > 0 . Thus Q ≻ 0 Q \succ0 Q ≻ 0 .
Remark 3.3 (Stability under SOS-convex additions). Suppose that Φ 0 \Phi_{0} Φ 0 has a strict Bregman Gram representation on v d ( v ) v_{d}(v) v d ( v ) , and let Ψ \Psi Ψ be an SOS-convex polynomial of degree at most 2 d 2d 2 d . Then Φ 0 + Ψ \Phi_{0}+\Psi Φ 0 + Ψ also has a strict Bregman Gram representation on v d ( v ) v_{d}(v) v d ( v ) . Indeed, writing R Φ 0 , s ( v ) = v d ( v ) T Q 0 ( s ) v d ( v ) R_{\Phi_{0},s}(v) = v_{d}(v)^{\mathsf{T}}Q_{0}(s)v_{d}(v) R Φ 0 , s ( v ) = v d ( v ) T Q 0 ( s ) v d ( v ) , Q 0 ( s ) ≻ 0 Q_{0}(s) \succ0 Q 0 ( s ) ≻ 0 , R Ψ , s ( v ) = v d ( v ) T Q Ψ ( s ) v d ( v ) R_{\Psi,s}(v) = v_{d}(v)^{\mathsf{T}}Q_{\Psi}(s)v_{d}(v) R Ψ , s ( v ) = v d ( v ) T Q Ψ ( s ) v d ( v ) , Q Ψ ( s ) ⪰ 0 Q_{\Psi}(s) \succeq0 Q Ψ ( s ) ⪰ 0 , we obtain
R Φ 0 + Ψ , s ( v ) = v d ( v ) T ( Q 0 ( s ) + Q Ψ ( s ) ) v d ( v ) , R_{\Phi_{0}+\Psi,s}(v) = v_{d}(v)^{\mathsf{T}}\left(Q_{0}(s)+Q_{\Psi}(s)\right)v_{d}(v), R Φ 0 + Ψ , s ( v ) = v d ( v ) T ( Q 0 ( s ) + Q Ψ ( s ) ) v d ( v ) ,
where Q 0 ( s ) + Q Ψ ( s ) ≻ 0 Q_{0}(s)+Q_{\Psi}(s) \succ0 Q 0 ( s ) + Q Ψ ( s ) ≻ 0 .
We now give three examples. Weighted Euclidean regularization inherits the Euclidean result by a change of coordinates. Positive sums of linear forms can also work when they generate enough polynomial directions. By contrast, coordinate-separable regularization misses all mixed directions and therefore has no full strict Gram margin.
Weighted Euclidean radial regularizer. Beyond the Euclidean regularizer, a natural example is the weighted ellipsoidal regularization
Φ W ( x ) = 1 2 d ( x T W x ) d , W ≻ 0. \Phi_{W}(x) = \frac{1}{2d}(x^{\mathsf{T}}Wx)^{d}, \qquad W \succ0. Φ W ( x ) = 2 d 1 ( x T W x ) d , W ≻ 0.
This is an invertible linear transformation of the Euclidean regularizer. The induced transformations on the homogeneous monomial spaces are also invertible, and therefore preserve the spanning property and the existence of a positive-definite Gram representation. The same conclusion holds for positive weighted sums of such regularizers, for example
Φ ( x ) = ∑ ℓ = 1 L ω ℓ 2 d ( x T M ℓ x ) d , ω ℓ > 0 , \Phi(x) = \sum_{\ell=1}^{L}\frac{\omega_{\ell}}{2d}(x^{\mathsf{T}}M_{\ell}x)^{d}, \qquad\omega_{\ell} > 0, Φ ( x ) = ℓ = 1 ∑ L 2 d ω ℓ ( x T M ℓ x ) d , ω ℓ > 0 ,
provided that at least one M ℓ M_{\ell} M ℓ is positive definite. More generally, Theorem 3.1 applies to any SoS-convex regularizer whose Hessian-generated square terms satisfy the full monomial spanning condition (i.e., the Bregman remainder has a quantitative positive-definite Gram matrix).
Linear-form regularizers and Veronese spanning. Consider
Φ l f ( x ) = 1 2 d ∑ ℓ = 1 m w ℓ ( a ℓ T x ) 2 d , w ℓ > 0. \Phi_{\mathrm{lf}}(x)=\frac{1}{2d}\sum_{\ell=1}^{m}w_{\ell}(a_{\ell}^{\mathsf{T}}x)^{2d},\qquad w_{\ell}>0. Φ lf ( x ) = 2 d 1 ℓ = 1 ∑ m w ℓ ( a ℓ T x ) 2 d , w ℓ > 0.
The corresponding polynomials in the integral representation are
p ℓ ( t , v ) = ( a ℓ T v ) ( a ℓ T ( s + t v ) ) d − 1 = ∑ q = 1 d ( d − 1 q − 1 ) ( a ℓ T s ) d − q t q − 1 ( a ℓ T v ) q . p_{\ell}(t,v)=(a_{\ell}^{\mathsf{T}}v)(a_{\ell}^{\mathsf{T}}(s+tv))^{d-1}=\sum_{q=1}^{d}\binom{d-1}{q-1}(a_{\ell}^{\mathsf{T}}s)^{d-q}t^{q-1}(a_{\ell}^{\mathsf{T}}v)^q. p ℓ ( t , v ) = ( a ℓ T v ) ( a ℓ T ( s + t v ) ) d − 1 = q = 1 ∑ d ( q − 1 d − 1 ) ( a ℓ T s ) d − q t q − 1 ( a ℓ T v ) q .
Let coeff ( ( a ℓ T v ) q ) \operatorname{coeff}((a_{\ell}^{\mathsf{T}}v)^q) coeff (( a ℓ T v ) q ) denote the coefficient3 vector of the homogeneous degree-q q q polynomial ( a ℓ T v ) q (a_{\ell}^{\mathsf{T}}v)^q ( a ℓ T v ) q with respect to the monomial basis { v β : ∣ β ∣ = q } \{v^\beta:|\beta|=q\} { v β : ∣ β ∣ = q } . Hence a sufficient condition for a strict Gram margin on the full nonconstant monomial space is that, for every q = 1 , … , d q=1,\ldots,d q = 1 , … , d ,
span { coeff ( ( a ℓ T v ) q ) : ℓ = 1 , … , m } = H n , q : = span { e v β : ∣ β ∣ = q } . \operatorname{span}\{\operatorname{coeff}((a_{\ell}^{\mathsf{T}}v)^q):\ell=1,\ldots,m\}=\mathcal{H}_{n,q}:=\operatorname{span}\{e_{v^\beta}:|\beta|=q\}. span { coeff (( a ℓ T v ) q ) : ℓ = 1 , … , m } = H n , q := span { e v β : ∣ β ∣ = q } .
Note that H n , q \mathcal{H}_{n,q} H n , q denotes the coefficient space of homogeneous degree-q q q polynomials in v v v . This is exactly a Veronese spanning condition. In particular, for fixed s s s , a generic collection of sufficiently many linear forms can satisfy it. The Veronese embedding is precisely the map given by all degree-q q q monomials, turning degree-q q q polynomial data into linear coordinates.
This is exactly a Veronese spanning condition. In particular, for fixed s s s , a generic sufficient number of linear forms is
m ≥ dim H n , q = ( n + d − 1 d ) . m\geq\dim\mathcal{H}_{n,q}=\binom{n+d-1}{d}. m ≥ dim H n , q = ( d n + d − 1 ) .
In particular, for d = 2 d=2 d = 2 it suffices generically to take m ≥ ( n + 1 2 ) m\geq\binom{n+1}{2} m ≥ ( 2 n + 1 ) , whereas for d = 3 d=3 d = 3 it suffices generically to take m ≥ ( n + 2 3 ) m\geq\binom{n+2}{3} m ≥ ( 3 n + 2 ) . The bound comes from the standard Veronese spanning condition [12 Section 1.4] [15 Chapter 2] and a proof is given in Appendix § 8 for completeness.
Failure of a strict margin for separable regularization. Consider the separable regularizer
Φ s e p ( x ) = 1 2 d ∑ i = 1 n x i 2 d . \Phi_{\mathrm{sep}}(x)=\frac{1}{2d}\sum_{i=1}^{n}x_i^{2d}. Φ sep ( x ) = 2 d 1 i = 1 ∑ n x i 2 d .
It is SOS-convex, since y T ∇ 2 Φ s e p ( x ) y = ( 2 d − 1 ) ∑ i = 1 n x i 2 d − 2 y i 2 = ( 2 d − 1 ) ∑ i = 1 n ( x i d − 1 y i ) 2 y^{\mathsf{T}}\nabla^2\Phi_{\mathrm{sep}}(x)y=(2d-1)\sum_{i=1}^{n}x_i^{2d-2}y_i^2=(2d-1)\sum_{i=1}^{n}(x_i^{d-1}y_i)^2 y T ∇ 2 Φ sep ( x ) y = ( 2 d − 1 ) ∑ i = 1 n x i 2 d − 2 y i 2 = ( 2 d − 1 ) ∑ i = 1 n ( x i d − 1 y i ) 2 . Consequently, its Bregman remainder is SOS. However, the squared polynomials in the integral representation are only coordinate-separable. Indeed, along the segment s + t v s+tv s + t v , the Hessian representation involves terms of the form
v i ( s i + t v i ) d − 1 , i = 1 , … , n . v_i(s_i+tv_i)^{d-1},\qquad i=1,\ldots,n. v i ( s i + t v i ) d − 1 , i = 1 , … , n .
For each i i i , this generates only pure powers of the single variable v i v_i v i :
v i ( s i + t v i ) d − 1 = ∑ q = 1 d ( d − 1 q − 1 ) s i d − q t q − 1 v i q . v_i(s_i+tv_i)^{d-1}=\sum_{q=1}^{d}\binom{d-1}{q-1}s_i^{d-q}t^{q-1}v_i^q. v i ( s i + t v i ) d − 1 = q = 1 ∑ d ( q − 1 d − 1 ) s i d − q t q − 1 v i q .
Thus the coefficient directions generated by the separable regularizer are contained in
span { e v i q : i = 1 , … , n , q = 1 , … , d } , \operatorname{span}\{e_{v_i^q}:i=1,\ldots,n,\ q=1,\ldots,d\}, span { e v i q : i = 1 , … , n , q = 1 , … , d } ,
and no mixed monomial direction such as e v i v j e_{v_i v_j} e v i v j , i ≠ j i\ne j i = j , is generated. Hence the Bregman remainder cannot have a positive-definite Gram representation on the full nonconstant monomial vector v d ( v ) = ( v β : 1 ≤ ∣ β ∣ ≤ d ) \mathbf{v}_d(v)=(v^\beta:1\leq|\beta|\leq d) v d ( v ) = ( v β : 1 ≤ ∣ β ∣ ≤ d ) . The failure is already visible on a coordinate line. Take s = e 1 s=e_1 s = e 1 and v = τ e 2 v=\tau e_2 v = τ e 2 . Then
R s s e p ( τ e 2 ) = 1 2 d τ 2 d . (30) R_s^{\mathrm{sep}}(\tau e_2)=\frac{1}{2d}\tau^{2d}. \tag*{(30)} R s sep ( τ e 2 ) = 2 d 1 τ 2 d . (30)
If there existed a matrix Q ( s ) ≻ 0 Q(s) \succ0 Q ( s ) ≻ 0 such that R s s e p ( v ) = v d ( v ) ⊤ Q ( s ) v d ( v ) R_s^{\mathrm{sep}}(v) = v_d(v)^\top Q(s)v_d(v) R s sep ( v ) = v d ( v ) ⊤ Q ( s ) v d ( v ) , then, since v d ( τ e 2 ) v_d(\tau e_2) v d ( τ e 2 ) contains the linear monomial τ \tau τ , we would have
1 2 d τ 2 d = R s s e p ( τ e 2 ) ≥ λ min ( Q ( s ) ) ∥ v d ( τ e 2 ) ∥ 2 ≥ λ min ( Q ( s ) ) τ 2 . \frac{1}{2d}\tau^{2d} = R_s^{\mathrm{sep}}(\tau e_2) \ge\lambda_{\min}(Q(s))\lVert v_d(\tau e_2)\rVert^2 \ge\lambda_{\min}(Q(s))\tau^2. 2 d 1 τ 2 d = R s sep ( τ e 2 ) ≥ λ m i n ( Q ( s )) ∥ v d ( τ e 2 ) ∥ 2 ≥ λ m i n ( Q ( s )) τ 2 .
This is impossible as τ → 0 \tau\to0 τ → 0 for d ≥ 2 d \ge2 d ≥ 2 . Therefore separable regularization yields an SoS Bregman remainder, but it does not provide the full strict Gram margin required by the perturbation argument.
Remark 3.4 (Coercivity does not imply a strict Gram margin). Coercivity is not sufficient for a full strict Gram margin. Indeed,
Φ s e p ( x ) = 1 2 d ∑ i = 1 n x i 2 d = 1 2 d ∥ x ∥ 2 d 2 d \Phi_{\mathrm{sep}}(x) = \frac{1}{2d}\sum_{i=1}^{n}x_i^{2d} = \frac{1}{2d}\lVert x\rVert_{2d}^{2d} Φ sep ( x ) = 2 d 1 i = 1 ∑ n x i 2 d = 2 d 1 ∥ x ∥ 2 d 2 d
is coercive and SoS-convex, but it acts separately on each coordinate and does not generate mixed monomial directions. Hence, the key issue is not only how strongly the regularizer grows, but whether it controls all polynomial directions needed for a strict Gram representation.
The conclusion of this section is that Euclidean regularization contributes a strictly positive Gram core, while some other regularizers do not. We now ask whether this core is strong enough to dominate the rest of a higher-order Taylor polynomial.
Sufficient Regularization, SoS Exactness, and Minimizer Recovery
This section turns the strict Gram margin into a global optimization result. The idea is that a sufficiently large positive Gram core can dominate any bounded lower-order terms that start at quadratic order. We first quantify how the strict Gram margin absorbs bounded polynomial perturbations, then apply this estimate to the same regularized polynomial family written in symmetric-tensor Taylor form. Finally, we show that the resulting strictness forces rank-one moment recovery of the minimizer.
Absorbing Bounded Polynomial Perturbations
We quantify how a strict Gram margin survives after adding a bounded polynomial perturbation.
Theorem 4.1 (SoS under bounded perturbations). Let d ≥ 2 d \ge2 d ≥ 2 , fix s ∈ R n ∖ { 0 } s \in\mathbb{R}^n \setminus\{0\} s ∈ R n ∖ { 0 } , and let p ∈ R [ v ] p \in\mathbb{R}[v] p ∈ R [ v ] satisfy
deg p ≤ 2 d , p ( 0 ) = 0 , ∇ p ( 0 ) = 0 , ∥ coeff ( p ) ∥ ≤ M \deg p \le2d,\qquad p(0)=0,\qquad\nabla p(0)=0,\qquad\lVert\operatorname{coeff}(p)\rVert\le M deg p ≤ 2 d , p ( 0 ) = 0 , ∇ p ( 0 ) = 0 , ∥ coeff ( p )∥ ≤ M for some M ≥ 0 M \ge0 M ≥ 0 . Throughout this section, v d ( v ) v_d(v) v d ( v ) denotes the nonconstant monomial vector v d ( v ) = ( v β : 1 ≤ ∣ β ∣ ≤ d ) v_d(v) = (v^\beta: 1 \le|\beta| \le d) v d ( v ) = ( v β : 1 ≤ ∣ β ∣ ≤ d ) , so the constant monomial is not included. For σ > 0 \sigma> 0 σ > 0 , define
q σ ( v ) : = p ( v ) + σ R s , d ( v ) . q_\sigma(v) := p(v) + \sigma R_{s,d}(v). q σ ( v ) := p ( v ) + σ R s , d ( v ) . There exists a constant C n , d > 0 C_{n,d} > 0 C n , d > 0 , independent of s s s , p p p , and σ \sigma σ , such that whenever
σ > σ ˉ ( s , M ) : = C n , d M c n , d min { ∥ s ∥ 2 d − 2 , 1 } , (31) \sigma> \bar{\sigma}(s,M) := \frac{C_{n,d}M}{c_{n,d}\min\{\lVert s\rVert^{2d-2},1\}}, \tag*{(31)} σ > σ ˉ ( s , M ) := c n , d min {∥ s ∥ 2 d − 2 , 1 } C n , d M , (31) the polynomial q σ q_\sigma q σ admits a positive-definite Gram representation with respect to v d ( v ) v_d(v) v d ( v ) . Consequently, q σ ∈ S o S q_\sigma\in\mathrm{SoS} q σ ∈ SoS and q σ ( v ) ≥ 0 q_\sigma(v) \ge0 q σ ( v ) ≥ 0 with equality if and only if v = 0 v=0 v = 0 .
Proof. By Lemma 3.1,
R s , d ( v ) = v d ( v ) ⊤ Q R ( s ) v d ( v ) , Q R ( s ) ≻ 0 , R_{s,d}(v)=v_d(v)^\top Q_R(s)v_d(v),\qquad Q_R(s)\succ0, R s , d ( v ) = v d ( v ) ⊤ Q R ( s ) v d ( v ) , Q R ( s ) ≻ 0 , with λ min ( Q R ( s ) ) ≥ c n , d min { ∥ s ∥ 2 d − 2 , 1 } \lambda_{\min}(Q_R(s)) \ge c_{n,d}\min\{\lVert s\rVert^{2d-2},1\} λ m i n ( Q R ( s )) ≥ c n , d min {∥ s ∥ 2 d − 2 , 1 } . Because p p p has no constant or linear term and has degree at most 2 d 2d 2 d , there exists a symmetric matrix Q p Q_p Q p such that
p ( v ) = v d ( v ) ⊤ Q p v d ( v ) . p(v)=v_d(v)^\top Q_pv_d(v). p ( v ) = v d ( v ) ⊤ Q p v d ( v ) .
The coefficient map from symmetric Gram matrices indexed by v d ( v ) \mathbf{v}_d(v) v d ( v ) to polynomials of degree at most 2 d 2d 2 d with no constant or linear term is surjective. Fixing a linear right inverse of this map, whose operator norm defines the constant C n , d C_{n,d} C n , d in (31) , the coefficient bound gives
∥ Q p ∥ 2 ≤ C n , d M . \lVert Q_p\rVert_2 \le C_{n,d}M. ∥ Q p ∥ 2 ≤ C n , d M .
Therefore,
q σ ( v ) = v d ( v ) ⊤ Q σ v d ( v ) , Q σ : = σ Q R ( s ) + Q p . q_\sigma(v)=\mathbf{v}_d(v)^{\top}Q_\sigma\mathbf{v}_d(v),\qquad Q_\sigma:=\sigma Q_{R}(s)+Q_p. q σ ( v ) = v d ( v ) ⊤ Q σ v d ( v ) , Q σ := σ Q R ( s ) + Q p .
By Weyl’s inequality,
λ min ( Q σ ) ≥ σ λ min ( Q R ( s ) ) − ∥ Q p ∥ 2 ≥ c n , d σ min { ∥ s ∥ 2 d − 2 , 1 } − C n , d M , \lambda_{\min}(Q_\sigma)\ge\sigma\lambda_{\min}(Q_R(s))-\lVert Q_p\rVert_2\ge c_{n,d}\sigma\min\{\lVert s\rVert^{2d-2},1\}-C_{n,d}M, λ m i n ( Q σ ) ≥ σ λ m i n ( Q R ( s )) − ∥ Q p ∥ 2 ≥ c n , d σ min {∥ s ∥ 2 d − 2 , 1 } − C n , d M ,
which is strictly positive precisely under the threshold condition (31) . Hence Q σ ≻ 0 Q_\sigma\succ0 Q σ ≻ 0 , and q σ q_\sigma q σ is SoS. Finally,
q σ ( v ) = 0 ⟺ v d ( v ) = 0 , q_\sigma(v)=0\ \Longleftrightarrow\ \mathbf{v}_d(v)=0, q σ ( v ) = 0 ⟺ v d ( v ) = 0 ,
because Q σ ≻ 0 Q_\sigma\succ0 Q σ ≻ 0 . The first homogeneous block of v d ( v ) \mathbf{v}_d(v) v d ( v ) is [ v ] 1 = v [v]_1=v [ v ] 1 = v , so v d ( v ) = 0 \mathbf{v}_d(v)=0 v d ( v ) = 0 if and only if v = 0 v=0 v = 0 . Thus q σ ( v ) > 0 q_\sigma(v)>0 q σ ( v ) > 0 for all v ≠ 0 v\ne0 v = 0 .
Remark 4.1 (Why the perturbation starts at quadratic order). The assumptions p σ ( 0 ) = 0 p_\sigma(0)=0 p σ ( 0 ) = 0 , ∇ p σ ( 0 ) = 0 \nabla p_\sigma(0)=0 ∇ p σ ( 0 ) = 0 are intrinsic to the present shifted strict-Gram argument. Indeed, the Bregman remainder satisfies
R s , d ( 0 ) = 0 , ∇ R s , d ( 0 ) = 0 , R_{s,d}(0)=0,\qquad\nabla R_{s,d}(0)=0, R s , d ( 0 ) = 0 , ∇ R s , d ( 0 ) = 0 ,
and hence R s , d ( v ) = O ( ∥ v ∥ 2 ) R_{s,d}(v)=O(\lVert v\rVert^2) R s , d ( v ) = O (∥ v ∥ 2 ) as v → 0 v\to0 v → 0 . Moreover, since the Gram vector v d ( v ) \mathbf{v}_d(v) v d ( v ) contains only nonconstant monomials, every polynomial of the form v d ( v ) ⊤ Q v d ( v ) \mathbf{v}_d(v)^{\top}Q\mathbf{v}_d(v) v d ( v ) ⊤ Q v d ( v ) has zero constant and linear terms. Accordingly, the natural perturbation space is
P 2 d ( 2 ) : = { p ∈ R [ v ] 2 d : p ( 0 ) = 0 , ∇ p ( 0 ) = 0 } . \mathcal{P}_{2d}^{(2)}:=\{p\in\mathbb{R}[v]_{2d}:p(0)=0,\ \nabla p(0)=0\}. P 2 d ( 2 ) := { p ∈ R [ v ] 2 d : p ( 0 ) = 0 , ∇ p ( 0 ) = 0 } .
Every polynomial in P 2 d ( 2 ) \mathcal{P}_{2d}^{(2)} P 2 d ( 2 ) admits a symmetric Gram representation on v d ( v ) \mathbf{v}_d(v) v d ( v ) . The positive-definite Gram matrix of R s , d R_{s,d} R s , d can therefore absorb any uniformly bounded signed Gram perturbation in this space after sufficiently large scaling.
Corollary 4.1. Let d ≥ 2 d\ge2 d ≥ 2 , and let ( p σ ) σ > 0 ⊂ R [ v ] (p_\sigma)_{\sigma>0}\subset\mathbb{R}[v] ( p σ ) σ > 0 ⊂ R [ v ] and ( s σ ) σ > 0 ⊂ R n ∖ { 0 } (s_\sigma)_{\sigma>0}\subset\mathbb{R}^n\setminus\{0\} ( s σ ) σ > 0 ⊂ R n ∖ { 0 } satisfy
deg p σ ≤ 2 d , p σ ( 0 ) = 0 , ∇ p σ ( 0 ) = 0 , sup σ ∥ coeff ( p σ ) ∥ < ∞ , \deg p_\sigma\le2d,\qquad p_\sigma(0)=0,\qquad\nabla p_\sigma(0)=0,\qquad\sup_\sigma\lVert\operatorname{coeff}(p_\sigma)\rVert<\infty, deg p σ ≤ 2 d , p σ ( 0 ) = 0 , ∇ p σ ( 0 ) = 0 , σ sup ∥ coeff ( p σ )∥ < ∞ ,
together with the scaling condition
σ ∥ s σ ∥ 2 d − 2 ⟶ ∞ . (32) \sigma\lVert s_\sigma\rVert^{2d-2}\longrightarrow\infty. \tag*{(32)} σ ∥ s σ ∥ 2 d − 2 ⟶ ∞. (32)
Then, for all sufficiently large σ \sigma σ , the polynomial q σ = p σ + σ R s σ , d q_\sigma=p_\sigma+\sigma R_{s_\sigma,d} q σ = p σ + σ R s σ , d admits a positive-definite Gram representation with respect to v d ( v ) \mathbf{v}_d(v) v d ( v ) ; in particular q σ ∈ S o S q_\sigma\in\mathrm{SoS} q σ ∈ SoS and q σ ( v ) > 0 q_\sigma(v)>0 q σ ( v ) > 0 for v ≠ 0 v\ne0 v = 0 .
Proof. Set M : = sup σ ∥ coeff ( p σ ) ∥ < ∞ M:=\sup_\sigma\lVert\operatorname{coeff}(p_\sigma)\rVert<\infty M := sup σ ∥ coeff ( p σ )∥ < ∞ . By (32) , for all sufficiently large σ \sigma σ we have σ min { ∥ s σ ∥ 2 d − 2 , 1 } > C n , d M / c n , d \sigma\min\{\lVert s_\sigma\rVert^{2d-2},1\}>C_{n,d}M/c_{n,d} σ min {∥ s σ ∥ 2 d − 2 , 1 } > C n , d M / c n , d , so Theorem 4.1 applies with the fixed pair ( s , p ) = ( s σ , p σ ) (s,p)=(s_\sigma,p_\sigma) ( s , p ) = ( s σ , p σ ) at each such σ \sigma σ .
Remark 4.2 (Perturbed polynomial is nonconvex). For every fixed s s s , the polynomial R s , d R_{s,d} R s , d is SoS-convex. Indeed, ∇ v 2 R s , d ( v ) = ∇ 2 Φ d ( s + v ) \nabla_v^2R_{s,d}(v)=\nabla^2\Phi_d(s+v) ∇ v 2 R s , d ( v ) = ∇ 2 Φ d ( s + v ) , and Φ d ( x ) = 1 2 ∥ x ∥ 2 d \Phi_d(x)=\frac{1}{2}\lVert x\rVert^{2d} Φ d ( x ) = 2 1 ∥ x ∥ 2 d is SoS-convex. However, the perturbed polynomial q σ ( v ) = p σ ( v ) + σ R s σ , d ( v ) q_\sigma(v)=p_\sigma(v)+\sigma R_{s_\sigma,d}(v) q σ ( v ) = p σ ( v ) + σ R s σ , d ( v ) need not be convex, or SoS-convex. The proof of Theorem 4.1 uses the positive-definite Gram margin of R s σ , d R_{s_\sigma,d} R s σ , d in the polynomial SoS cone; it does not require the Hessian of q σ q_\sigma q σ to be positive semidefinite.
Sufficiently Regularized Taylor Models
We now apply the perturbation result to the regularized polynomial family of (1) , using the equivalent symmetric-tensor Taylor form from § 2 . Its shifted coefficients remain bounded while the Gram margin grows. The assumption g ≠ 0 g \ne0 g = 0 is what gives the required scaling of the global minimizer.
Corollary 4.2 (SoS exactness of sufficiently regularized Taylor models). Let d ≥ 2 d \ge2 d ≥ 2 , and consider
m σ ( s ) = T 2 d − 1 ( s ) + σ 2 d ∥ s ∥ 2 d , m_{\sigma}(s) = \mathcal{T}_{2d-1}(s) + \frac{\sigma}{2d}\lVert s\rVert^{2d}, m σ ( s ) = T 2 d − 1 ( s ) + 2 d σ ∥ s ∥ 2 d , where T 2 d − 1 \mathcal{T}_{2d-1} T 2 d − 1 is a fixed polynomial of degree at most 2 d − 1 2d-1 2 d − 1 . We assume that ∥ g ∥ ≠ 0 \lVert g\rVert\ne0 ∥ g ∥ = 0 and let s σ ∗ ≠ 0 s_{\sigma}^{*} \ne0 s σ ∗ = 0 be a global minimizer of m σ m_{\sigma} m σ . Then, for all sufficiently large σ \sigma σ , the shifted polynomial q σ ( v ) : = m σ ( s σ ∗ + v ) − m σ ( s σ ∗ ) q_{\sigma}(v) := m_{\sigma}(s_{\sigma}^{*}+v)-m_{\sigma}(s_{\sigma}^{*}) q σ ( v ) := m σ ( s σ ∗ + v ) − m σ ( s σ ∗ ) admits a positive-definite Gram representation with respect to v d ( v ) v_d(v) v d ( v ) (again excluding the constant monomial) and
q σ ∈ SoS , q_{\sigma} \in\operatorname{SoS}, q σ ∈ SoS , and q σ ( v ) = 0 q_{\sigma}(v)=0 q σ ( v ) = 0 if and only if v = 0 v=0 v = 0 . In particular, s σ ∗ s_{\sigma}^{*} s σ ∗ is the unique global minimizer of m σ m_{\sigma} m σ for all sufficiently large σ \sigma σ .
Proof. Since s σ ∗ s_{\sigma}^{*} s σ ∗ is an unconstrained global minimizer, it satisfies ∇ T 2 d − 1 ( s σ ∗ ) + σ ∥ s σ ∗ ∥ 2 d − 2 s σ ∗ = 0 \nabla\mathcal{T}_{2d-1}(s_{\sigma}^{*})+\sigma\lVert s_{\sigma}^{*}\rVert^{2d-2}s_{\sigma}^{*}=0 ∇ T 2 d − 1 ( s σ ∗ ) + σ ∥ s σ ∗ ∥ 2 d − 2 s σ ∗ = 0 . Expanding the shifted Taylor model around s σ ∗ s_{\sigma}^{*} s σ ∗ and using stationarity, we obtain q σ ( v ) = p σ ( v ) + σ d R s σ ∗ , d ( v ) q_{\sigma}(v)=p_{\sigma}(v)+\frac{\sigma}{d}R_{s_{\sigma}^{*},d}(v) q σ ( v ) = p σ ( v ) + d σ R s σ ∗ , d ( v ) , because R s , d R_{s,d} R s , d is defined for Φ d ( x ) = 1 2 ∥ x ∥ 2 d \Phi_d(x)=\frac{1}{2}\lVert x\rVert^{2d} Φ d ( x ) = 2 1 ∥ x ∥ 2 d , while the Taylor model contains σ 2 d ∥ s ∥ 2 d \frac{\sigma}{2d}\lVert s\rVert^{2d} 2 d σ ∥ s ∥ 2 d . where
p σ ( v ) : = ∑ j = 2 2 d − 1 1 j ! ∇ j T 2 d − 1 ( s σ ∗ ) [ v ] j . p_{\sigma}(v) := \sum_{j=2}^{2d-1}\frac{1}{j!}\nabla^{j}\mathcal{T}_{2d-1}(s_{\sigma}^{*})[v]^j. p σ ( v ) := j = 2 ∑ 2 d − 1 j ! 1 ∇ j T 2 d − 1 ( s σ ∗ ) [ v ] j .
Clearly,
deg p σ ≤ 2 d − 1 , p σ ( 0 ) = 0 , ∇ p σ ( 0 ) = 0. \deg p_{\sigma} \le2d-1,\qquad p_{\sigma}(0)=0,\qquad\nabla p_{\sigma}(0)=0. deg p σ ≤ 2 d − 1 , p σ ( 0 ) = 0 , ∇ p σ ( 0 ) = 0.
It remains to verify that the coefficients of p σ p_{\sigma} p σ are uniformly bounded. For convenience, write T 2 : = H \mathcal{T}_2:=H T 2 := H . For each $j=2,\ldots,2d-1,
∇ j T 2 d − 1 ( s σ ∗ ) = ∑ k = j 2 d − 1 1 ( k − j ) ! T k [ ( s σ ∗ ) ] k − j . \nabla^{j}\mathcal{T}_{2d-1}(s_{\sigma}^{*})=\sum_{k=j}^{2d-1}\frac{1}{(k-j)!}\mathcal{T}_k[(s_{\sigma}^{*})]^{k-j}. ∇ j T 2 d − 1 ( s σ ∗ ) = k = j ∑ 2 d − 1 ( k − j )! 1 T k [( s σ ∗ ) ] k − j .
Since Theorem C.1 gives s σ ∗ → 0 s_{\sigma}^{*}\to0 s σ ∗ → 0 , we have ∥ s σ ∗ ∥ ≤ 1 \lVert s_{\sigma}^{*}\rVert\le1 ∥ s σ ∗ ∥ ≤ 1 for all sufficiently large σ \sigma σ , and therefore
∥ ∇ j T 2 d − 1 ( s σ ∗ ) ∥ ≤ ∑ k = j 2 d − 1 ∥ T k ∥ ( k − j ) ! . \left\lVert\nabla^{j}\mathcal{T}_{2d-1}(s_{\sigma}^{*})\right\rVert\le\sum_{k=j}^{2d-1}\frac{\lVert\mathcal{T}_k\rVert}{(k-j)!}. ∇ j T 2 d − 1 ( s σ ∗ ) ≤ k = j ∑ 2 d − 1 ( k − j )! ∥ T k ∥ .
The right-hand side depends only on the fixed problem data and is independent of σ \sigma σ . Hence, sup σ ∥ coeff ( p σ ) ∥ < ∞ \sup_{\sigma}\lVert\operatorname{coeff}(p_{\sigma})\rVert<\infty sup σ ∥ coeff ( p σ )∥ < ∞ . Using Theorem C.1 , we have
σ ∥ s σ ∗ ∥ 2 d − 2 = Θ ( σ 1 / ( 2 d − 1 ) ) → ∞ , \sigma\lVert s_{\sigma}^{*}\rVert^{2d-2}=\Theta\left(\sigma^{1/(2d-1)}\right)\to\infty, σ ∥ s σ ∗ ∥ 2 d − 2 = Θ ( σ 1/ ( 2 d − 1 ) ) → ∞ ,
which verifies the required scaling condition. Equivalently,
σ d ∥ s σ ∗ ∥ 2 d − 2 → ∞ . \frac{\sigma}{d}\lVert s_{\sigma}^{*}\rVert^{2d-2}\to\infty. d σ ∥ s σ ∗ ∥ 2 d − 2 → ∞.
All the assumptions of Corollary 4.1 are therefore satisfied with perturbation parameter σ / d \sigma/d σ / d in place of σ \sigma σ , and the stated SoS and uniqueness conclusions follow.
:::
This corresponds to g = 0 g=0 g = 0 , H = − μ I H=-\mu I H = − μ I , and T 3 = ⋯ = T 2 d − 1 = 0 T_3=\cdots=T_{2d-1}=0 T 3 = ⋯ = T 2 d − 1 = 0 . Since r = 0 r=0 r = 0 is a local maximum and φ σ ( r ) → + ∞ \varphi_\sigma(r)\to+\infty φ σ ( r ) → + ∞ as r → ∞ r\to\infty r → ∞ , the set of global minimizers is
argmin s ∈ R n m σ ( s ) = { s ∈ R n : ∥ s ∥ = ( μ σ ) 1 / ( 2 d − 2 ) } . \underset{s\in\mathbb{R}^n}{\operatorname{argmin}}\ m_\sigma(s)=\left\{s\in\mathbb{R}^n:\|s\|=\left(\frac{\mu}{\sigma}\right)^{1/(2d-2)}\right\}. s ∈ R n argmin m σ ( s ) = { s ∈ R n : ∥ s ∥ = ( σ μ ) 1/ ( 2 d − 2 ) } .
Thus, there are infinitely many global minimizers, and every global minimizer satisfies
∥ s σ ∗ ∥ = Θ ( σ − 1 / ( 2 d − 2 ) ) . \|s_\sigma^*\|=\Theta\left(\sigma^{-1/(2d-2)}\right). ∥ s σ ∗ ∥ = Θ ( σ − 1/ ( 2 d − 2 ) ) .
rather than Θ ( σ − 1 / ( 2 d − 1 ) ) \Theta\left(\sigma^{-1/(2d-1)}\right) Θ ( σ − 1/ ( 2 d − 1 ) ) . The strict Gram-dominance condition (32) of Corollary 4.1 is also not satisfied. For any chosen global minimizer s σ ∗ s_\sigma^* s σ ∗ , the shifted polynomial q σ ( v ) = m σ ( s σ ∗ + v ) − m σ ( s σ ∗ ) q_\sigma(v)=m_\sigma(s_\sigma^*+v)-m_\sigma(s_\sigma^*) q σ ( v ) = m σ ( s σ ∗ + v ) − m σ ( s σ ∗ ) has multiple zeros, corresponding to all other global minimizers, and therefore cannot admit a positive-definite Gram representation with respect to the full nonconstant monomial vector. Although q σ q_\sigma q σ may still be SoS and admit a positive-semidefinite Gram representation, it cannot admit a positive-definite Gram representation with respect to the full nonconstant monomial vector.
Rank-One Moment Recovery and Exact Minimizer Extraction
SoS exactness gives the correct global minimum value, but we also want the minimizer itself. The strict Gram representation provides this extra information. At an optimum, a positive-definite Gram matrix can pair to zero with the positive-semidefinite moment matrix only if all shifted nonconstant moments vanish. The optimal moment matrix therefore collapses to rank one. In short,
strict Gram certificate ⟹ unique rank-one moment solution ⟹ exact minimizer recovery. \text{strict Gram certificate}\quad\Longrightarrow\quad\text{unique rank-one moment solution}\quad\Longrightarrow\quad\text{exact minimizer recovery.} strict Gram certificate ⟹ unique rank-one moment solution ⟹ exact minimizer recovery.
The next theorem makes this statement precise.
Theorem 4.2 (Rank-one moment recovery and exact minimizer extraction). Suppose that, for some d ≥ 2 d\ge2 d ≥ 2 , a polynomial m σ ∈ R [ x ] 2 d m_\sigma\in\mathbb{R}[x]_{2d} m σ ∈ R [ x ] 2 d has a unique global minimizer s σ ∗ s_\sigma^* s σ ∗ , and let m σ ∗ : = m σ ( s σ ∗ ) m_\sigma^*:=m_\sigma(s_\sigma^*) m σ ∗ := m σ ( s σ ∗ ) . Assume that the shifted polynomial q σ ( v ) : = m σ ( s σ ∗ + v ) − m σ ∗ q_\sigma(v):=m_\sigma(s_\sigma^*+v)-m_\sigma^* q σ ( v ) := m σ ( s σ ∗ + v ) − m σ ∗ admits the positive definite Gram representation with respect to the nonconstant monomial vector v d ( v ) v_d(v) v d ( v )
q σ ( v ) = v d ( v ) ⊤ Q σ v d ( v ) , Q σ ≻ 0. (33) q_\sigma(v)=v_d(v)^\top Q_\sigma v_d(v),\qquad Q_\sigma\succ0. \tag*{(33)} q σ ( v ) = v d ( v ) ⊤ Q σ v d ( v ) , Q σ ≻ 0. (33) Then the order-d d d SoS representation
ρ d S o S : = sup γ ∈ R γ \rho_d^{\mathrm{SoS}}:=\underset{\gamma\in\mathbb{R}}{\sup}\ \gamma ρ d SoS := γ ∈ R sup γ s.t. m σ ( x ) − γ ∈ Σ [ x ] 2 d (34) \text{s.t.}\quad m_\sigma(x)-\gamma\in\Sigma[x]_{2d} \tag*{(34)} s.t. m σ ( x ) − γ ∈ Σ [ x ] 2 d (34) is exact ρ d S o S = m σ ∗ \rho_d^{\mathrm{SoS}}=m_\sigma^* ρ d SoS = m σ ∗ . Moreover, the corresponding order-d d d moment relaxation
ρ d m o m : = inf y L y ( m σ ) \rho_d^{\mathrm{mom}}:=\underset{y}{\inf}\ L_y(m_\sigma) ρ d mom := y inf L y ( m σ ) s.t. y 0 = 1 , M d ( y ) ⪰ 0 (35) \text{s.t.}\quad y_0=1,\ M_d(y)\succeq0 \tag*{(35)} s.t. y 0 = 1 , M d ( y ) ⪰ 0 (35) has a unique optimal truncated moment sequence y ∗ y^* y ∗ , namely y α ∗ = ( s σ ∗ ) α y_\alpha^*=(s_\sigma^*)^\alpha y α ∗ = ( s σ ∗ ) α , ∣ α ∣ ≤ 2 d |\alpha|\le2d ∣ α ∣ ≤ 2 d . Consequently,
M d ( y ∗ ) = z d ( s σ ∗ ) z d ( s σ ∗ ) ⊤ , M_d(y^*)=z_d(s_\sigma^*)z_d(s_\sigma^*)^\top, M d ( y ∗ ) = z d ( s σ ∗ ) z d ( s σ ∗ ) ⊤ , where z d ( x ) = ( 1 , [ x ] ⊤ , … , [ x ] d ⊤ ) ⊤ z_d(x)=(1,[x]^\top,\ldots,[x]_{d}^{\top})^\top z d ( x ) = ( 1 , [ x ] ⊤ , … , [ x ] d ⊤ ) ⊤ , and hence rank M d ( y ∗ ) = rank M d − 1 ( y ∗ ) = 1 \operatorname{rank}M_d(y^*)=\operatorname{rank}M_{d-1}(y^*)=1 rank M d ( y ∗ ) = rank M d − 1 ( y ∗ ) = 1 . In particular, the unique global minimizer is recovered exactly from the first-order moments: ( s σ ∗ ) i = y e i ∗ (s_\sigma^*)_i=y_{e_i}^* ( s σ ∗ ) i = y e i ∗ , i = 1 , … , n i=1,\ldots,n i = 1 , … , n .
Proof. Primal feasible: Global minimum value attained. Since q σ q_\sigma q σ is SoS, the shifted polynomial m σ ( x ) − m σ ∗ = q σ ( x − s σ ∗ ) m_\sigma(x)-m_\sigma^*=q_\sigma(x-s_\sigma^*) m σ ( x ) − m σ ∗ = q σ ( x − s σ ∗ ) is also SoS by translations. Therefore, γ = m σ ∗ \gamma=m_\sigma^* γ = m σ ∗ is feasible for (34) , and hence ρ d S o S ≥ m σ ∗ \rho_d^{\mathrm{SoS}}\ge m_\sigma^* ρ d SoS ≥ m σ ∗ . On the other hand, if m σ ( x ) − γ ∈ Σ [ x ] 2 d m_\sigma(x)-\gamma\in\Sigma[x]_{2d} m σ ( x ) − γ ∈ Σ [ x ] 2 d , then m σ ( x ) − γ ≥ 0 m_\sigma(x)-\gamma\ge0 m σ ( x ) − γ ≥ 0 for every x x x , so necessarily γ ≤ inf x m σ ( x ) = m σ ∗ \gamma\le\inf_xm_\sigma(x)=m_\sigma^* γ ≤ inf x m σ ( x ) = m σ ∗ . Thus ρ d S o S = m σ ∗ \rho_d^{\mathrm{SoS}}=m_\sigma^* ρ d SoS = m σ ∗ .
Dual feasible. We next analyze the moment relaxation. The truncated moment sequence of the Dirac measure at s σ ∗ s_\sigma^* s σ ∗ , y α = ( s σ ∗ ) α y_\alpha=(s_\sigma^*)^\alpha y α = ( s σ ∗ ) α , ∣ α ∣ ≤ 2 d |\alpha|\le2d ∣ α ∣ ≤ 2 d , is feasible for (35) , because
M d ( y ) = z d ( s σ ∗ ) z d ( s σ ∗ ) ⊤ ⪰ 0 , y 0 = 1. M_d(y)=z_d(s_\sigma^*)z_d(s_\sigma^*)^\top\succeq0,\qquad y_0=1. M d ( y ) = z d ( s σ ∗ ) z d ( s σ ∗ ) ⊤ ⪰ 0 , y 0 = 1.
Its objective value is L y ( m σ ) = m σ ( s σ ∗ ) = m σ ∗ L_y(m_\sigma)=m_\sigma(s_\sigma^*)=m_\sigma^* L y ( m σ ) = m σ ( s σ ∗ ) = m σ ∗ . Weak duality and the exactness of the SoS representation therefore yield ρ d m o m = ρ d S o S = m σ ∗ \rho_d^{\mathrm{mom}}=\rho_d^{\mathrm{SoS}}=m_\sigma^* ρ d mom = ρ d SoS = m σ ∗ .
Global minimizer is recovered: It remains to prove uniqueness and the rank-one property. Let y y y be any optimal truncated moment sequence in the original x x x -coordinates. Define the shifted truncated moment sequence y ~ \widetilde{y} y by
L y ~ ( h ( v ) ) = L y ( h ( x − s σ ∗ ) ) , deg h ≤ 2 d . L_{\widetilde{y}}(h(v))=L_y(h(x-s_\sigma^*)),\qquad\deg h\le2d. L y ( h ( v )) = L y ( h ( x − s σ ∗ )) , deg h ≤ 2 d .
Then,
y ~ 0 = 1 , M d ( y ~ ) ⪰ 0 , L y ~ ( q σ ) = 0. \widetilde{y}_0=1,\qquad M_d(\widetilde{y})\succeq0,\qquad L_{\widetilde{y}}(q_\sigma)=0. y 0 = 1 , M d ( y ) ⪰ 0 , L y ( q σ ) = 0.
Indeed, for every polynomial r r r of degree at most d d d ,
L y ~ ( r ( v ) 2 ) = L y ( r ( x − s σ ∗ ) 2 ) ≥ 0 , L_{\widetilde{y}}(r(v)^2)=L_y(r(x-s_\sigma^*)^2)\ge0, L y ( r ( v ) 2 ) = L y ( r ( x − s σ ∗ ) 2 ) ≥ 0 ,
so M d ( y ~ ) ⪰ 0 M_d(\widetilde{y})\succeq0 M d ( y ) ⪰ 0 ; and optimality gives L y ~ ( q σ ) = L y ( m σ − m σ ∗ ) = 0 L_{\widetilde{y}}(q_\sigma)=L_y(m_\sigma-m_\sigma^*)=0 L y ( q σ ) = L y ( m σ − m σ ∗ ) = 0 . Partition the moment matrix according to the constant monomial and the nonconstant monomial vector v d ( v ) v_d(v) v d ( v ) :
M d ( y ~ ) = ( 1 a ⊤ a M d + ( y ~ ) ) . M_d(\widetilde{y})=
\begin{pmatrix}
1 & a^\top\\
a & M_d^+(\widetilde{y})
\end{pmatrix}. M d ( y ) = ( 1 a a ⊤ M d + ( y ) ) .
where M d + ( y ~ ) M_d^+(\widetilde{y}) M d + ( y ) is the principal submatrix indexed by all nonconstant monomials of degree at most d d d . Since M d ( y ~ ) ⪰ 0 M_d(\widetilde{y})\succeq0 M d ( y ) ⪰ 0 , we also have its principal submatrix M d + ( y ~ ) ⪰ 0 M_d^+(\widetilde{y})\succeq0 M d + ( y ) ⪰ 0 . Using the strict Gram representation (33) ,
0 = L y ~ ( q σ ) = L y ~ ( v d ( v ) ⊤ Q σ v d ( v ) ) = ⟨ Q σ , M d + ( y ~ ) ⟩ = trace ( Q σ M d + ( y ~ ) ) . 0=L_{\widetilde{y}}(q_\sigma)=L_{\widetilde{y}}(v_d(v)^\top Q_\sigma v_d(v))=\langle Q_\sigma,M_d^+(\widetilde{y})\rangle=\operatorname{trace}(Q_\sigma M_d^+(\widetilde{y})). 0 = L y ( q σ ) = L y ( v d ( v ) ⊤ Q σ v d ( v )) = ⟨ Q σ , M d + ( y )⟩ = trace ( Q σ M d + ( y )) .
where ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ denotes the Frobenius inner product. More details about the last two equalities are given in Remark D.1. Because
Q σ ≻ 0 and M d + ( y ~ ) ⪰ 0 , Q_\sigma\succ0\qquad\text{and}\qquad M_d^+(\widetilde{y})\succeq0, Q σ ≻ 0 and M d + ( y ) ⪰ 0 ,
the equality above implies M d + ( y ~ ) = 0 M_d^+(\widetilde{y})=0 M d + ( y ) = 0 . Indeed, Q σ 1 / 2 M d + ( y ~ ) Q σ 1 / 2 ⪰ 0 Q_\sigma^{1/2}M_d^+(\widetilde{y})Q_\sigma^{1/2}\succeq0 Q σ 1/2 M d + ( y ) Q σ 1/2 ⪰ 0 and its trace is zero, so it must be the zero matrix. Hence
M d ( y ~ ) = ( 1 a ⊤ a 0 ) . M_d(\widetilde{y})=
\begin{pmatrix}
1 & a^\top\\
a & 0
\end{pmatrix}. M d ( y ) = ( 1 a a ⊤ 0 ) .
The positive semidefiniteness of this matrix forces a = 0 a=0 a = 0 . For example, every 2 × 2 2\times2 2 × 2 principal minor satisfies
det ( 1 a i a i 0 ) = − a i 2 ≥ 0 , \det\begin{pmatrix}
1 & a_i\\
a_i & 0
\end{pmatrix}=-a_i^2\ge0, det ( 1 a i a i 0 ) = − a i 2 ≥ 0 ,
and therefore a i = 0 a_i=0 a i = 0 for every i i i . Consequently,
M d ( y ~ ) = ( 1 0 0 0 ) . M_d(\widetilde{y})=
\begin{pmatrix}
1 & 0\\
0 & 0
\end{pmatrix}. M d ( y ) = ( 1 0 0 0 ) .
This also implies that all nonconstant moments vanish: the vector a = 0 a=0 a = 0 gives the moments of degrees 1 , … , d 1,\ldots,d 1 , … , d , while M d + ( y ~ ) = 0 M_d^+(\widetilde{y})=0 M d + ( y ) = 0 gives all moments of degrees 2 , … , 2 d 2,\ldots,2d 2 , … , 2 d , since every monomial of degree between 2 2 2 and 2 d 2d 2 d is a product of two nonconstant monomials of degrees at most d d d . Thus y ~ \widetilde{y} y is uniquely the truncated moment sequence of the Dirac measure at v = 0 v=0 v = 0 (more details can be found in Remark D.2),
y ~ 0 = 1 , y ~ α = 0 for every 1 ≤ ∣ α ∣ ≤ 2 d . \widetilde{y}_0=1,\qquad\widetilde{y}_\alpha=0\quad\text{for every }1\le|\alpha|\le2d. y 0 = 1 , y α = 0 for every 1 ≤ ∣ α ∣ ≤ 2 d .
Translating back to the original variable x = v + s σ ∗ x=v+s_\sigma^* x = v + s σ ∗ gives the unique optimal moment sequence
y α ∗ = ( s σ ∗ ) α , ∣ α ∣ ≤ 2 d . y_\alpha^*=(s_\sigma^*)^\alpha,\qquad|\alpha|\le2d. y α ∗ = ( s σ ∗ ) α , ∣ α ∣ ≤ 2 d .
Therefore, M d ( y ∗ ) = z d ( s σ ∗ ) z d ( s σ ∗ ) ⊤ M_d(y^*)=z_d(s_\sigma^*)z_d(s_\sigma^*)^\top M d ( y ∗ ) = z d ( s σ ∗ ) z d ( s σ ∗ ) ⊤ , which has rank one. The same conclusion holds for M d − 1 ( y ∗ ) M_{d-1}(y^*) M d − 1 ( y ∗ ) , which is its principal submatrix indexed by monomials of degree at most d − 1 d-1 d − 1 .
Corollary 4.3 (Polynomial-size exact SDP and minimizer recovery). Fix d ≥ 2 d \ge2 d ≥ 2 . Under the assumptions of Corollary 4.2, for all sufficiently large σ \sigma σ , the global minimum of m σ m_\sigma m σ is attained exactly by its degree-d d d SoS/moment representation. The corresponding moment matrix has order ( n + d d ) \binom{n+d}{d} ( d n + d ) . Hence, for fixed d d d , the size of the semidefinite formulation is polynomial in n n n . Moreover, its unique optimal moment matrix has rank one and its first-order moments recover the unique global minimizer.
Proof. Exactness follows from Corollary 4.2; uniqueness and rank-one recovery follow from Theorem 4.2. The matrix-order formula is the number of monomials in n n n variables of degree at most d d d .
We have therefore completed the main chain of the paper:
large regularization ⟹ strict Gram dominance ⟹ exact SoS representation ⟹ rank-one minimizer recovery . \text{large regularization} \Longrightarrow\text{strict Gram dominance} \Longrightarrow\text{exact SoS representation} \Longrightarrow\text{rank-one minimizer recovery}. large regularization ⟹ strict Gram dominance ⟹ exact SoS representation ⟹ rank-one minimizer recovery .
The next section connects this unconstrained regularization picture with the other classical globalization mechanism for Taylor models: trust regions.
Further consequences of strict Gram representations
A strict Gram representation has several implications beyond SoS exactness and moment recovery. In particular, it guarantees a unique global minimizer, nondegeneracy at the minimizer, and a local Polyak–Łojasiewicz (PL) inequality. We first clarify the relationship between SoS exactness, uniqueness, and strict Gram representations, including their regularization thresholds. We then establish the local PL property and show that an interior SoS-convex certificate also implies a strict Gram representation.
SoS, unique global minimizers, and strict Gram A strict Gram representation implies both SoS exactness and uniqueness of the global minimizer. Therefore,
σ S o S ≤ σ s t r i c t , σ u n i q ≤ σ s t r i c t , \sigma_{\mathrm{SoS}} \le\sigma_{\mathrm{strict}}, \qquad\sigma_{\mathrm{uniq}} \le\sigma_{\mathrm{strict}}, σ SoS ≤ σ strict , σ uniq ≤ σ strict ,
where σ S o S \sigma_{\mathrm{SoS}} σ SoS , σ u n i q \sigma_{\mathrm{uniq}} σ uniq , and σ s t r i c t \sigma_{\mathrm{strict}} σ strict denote the smallest regularization thresholds for SoS exactness, uniqueness of the global minimizer, and the existence of a strict Gram representation, respectively. Each denotes the infimum of parameters beyond which the corresponding property holds for every larger regularization weight. The three thresholds need not be attained at equality. Note that in general, neither SoS exactness nor uniqueness of the global minimizer implies the other. An SoS polynomial may have multiple global minimizers, while a nonnegative polynomial with a unique global minimizer need not be SoS. Consequently, the sufficient regularization bound established above need not coincide with the sharp threshold for either property.
Example 4.1. To illustrate this distinction, consider the quartically regularized bivariate polynomial
m σ ( x , y ) = x + 1 2 x 2 − 1 2 y 2 + σ 4 ( x 2 + y 2 ) 2 , σ > 0. m_\sigma(x,y) = x + \frac{1}{2}x^2 - \frac{1}{2}y^2 + \frac{\sigma}{4}(x^2+y^2)^2,\qquad\sigma> 0. m σ ( x , y ) = x + 2 1 x 2 − 2 1 y 2 + 4 σ ( x 2 + y 2 ) 2 , σ > 0.
For every σ > 0 \sigma> 0 σ > 0 , completing squares gives
m σ ( x , y ) + 1 4 + 1 4 σ = ( x + 1 2 ) 2 + σ 4 ( x 2 + y 2 − 1 σ ) 2 . m_\sigma(x,y) + \frac{1}{4} + \frac{1}{4\sigma}
= \left(x+\frac{1}{2}\right)^2 + \frac{\sigma}{4}\left(x^2+y^2-\frac{1}{\sigma}\right)^2. m σ ( x , y ) + 4 1 + 4 σ 1 = ( x + 2 1 ) 2 + 4 σ ( x 2 + y 2 − σ 1 ) 2 .
For 0 < σ ≤ 4 0 < \sigma\le4 0 < σ ≤ 4 the two squares vanish simultaneously, so this identity gives the exact global minimum and an SoS certificate. For σ > 4 \sigma> 4 σ > 4 , the shifted polynomial is also SoS by the strict Gram representation stated below. For 0 < σ < 4 0 < \sigma< 4 0 < σ < 4 , there are two global minimizers, ( − 1 2 , ± 1 σ − 1 4 ) \left(-\frac{1}{2}, \pm\sqrt{\frac{1}{\sigma}-\frac{1}{4}}\right) ( − 2 1 , ± σ 1 − 4 1 ) . At σ = 4 \sigma= 4 σ = 4 , they merge into the unique global minimizer ( − 1 / 2 , 0 ) \left(-1/2,0\right) ( − 1/2 , 0 ) , where the Hessian is singular. For σ > 4 \sigma> 4 σ > 4 , the unique global minimizer is ( − u , 0 ) (-u,0) ( − u , 0 ) , where u ∈ ( 0 , 1 / 2 ) u \in(0,1/2) u ∈ ( 0 , 1/2 ) is the unique positive solution of σ u 3 + u = 1 \sigma u^3+u=1 σ u 3 + u = 1 . In this case, the shifted polynomial admits a positive-definite Gram representation on the full nonconstant monomial basis of degrees one and two. Therefore, the three sharp thresholds satisfy
σ S o S = 0 < σ u n i q = σ s t r i c t = 4. \sigma_{\mathrm{SoS}} = 0 < \sigma_{\mathrm{uniq}} = \sigma_{\mathrm{strict}} = 4. σ SoS = 0 < σ uniq = σ strict = 4.
Local PL inequality from a strict Gram representation
Lemma 4.1 (Strict Gram implies local PL). Let s ∗ s^* s ∗ be a global minimizer of a polynomial m m m , and suppose that the shifted polynomial admits a strict Gram representation
m ( s ∗ + v ) − m ( s ∗ ) = v d ( v ) T Q v d ( v ) , Q ≻ 0. m(s^*+v)-m(s^*)=v_d(v)^\mathsf{T}Qv_d(v),\qquad Q\succ0. m ( s ∗ + v ) − m ( s ∗ ) = v d ( v ) T Q v d ( v ) , Q ≻ 0. Then s ∗ s^* s ∗ is a nondegenerate global minimizer. Moreover, there exist a neighbourhood U U U of s ∗ s^* s ∗ and a constant μ > 0 \mu>0 μ > 0 such that
m ( s ) − m ( s ∗ ) ≤ 1 2 μ ∥ ∇ m ( s ) ∥ 2 , s ∈ U . m(s)-m(s^*)\leq\frac{1}{2\mu}\lVert\nabla m(s)\rVert^2,\qquad s\in U. m ( s ) − m ( s ∗ ) ≤ 2 μ 1 ∥ ∇ m ( s ) ∥ 2 , s ∈ U . Proof. Partition the monomial vector and its Gram matrix as
v d ( v ) = ( v v 2 : d ( v ) ) , Q = ( 1 2 ∇ 2 m ( s ∗ ) Q 12 Q 12 T Q 22 ) , v_d(v)=\begin{pmatrix}v\\v_{2:d}(v)\end{pmatrix},\qquad Q=\begin{pmatrix}\frac{1}{2}\nabla^2m(s^*) & Q_{12}\\Q_{12}^{\mathsf T} & Q_{22}\end{pmatrix}, v d ( v ) = ( v v 2 : d ( v ) ) , Q = ( 2 1 ∇ 2 m ( s ∗ ) Q 12 T Q 12 Q 22 ) , where v 2 : d v_{2:d} v 2 : d contains the monomials of degrees 2 , … , d 2,\ldots,d 2 , … , d . The upper-left block follows by comparing the quadratic terms in the Gram representation. Since Q ≻ 0 Q\succ0 Q ≻ 0 , we have ∇ 2 m ( s ∗ ) ≻ 0 \nabla^2m(s^*)\succ0 ∇ 2 m ( s ∗ ) ≻ 0 . By continuity, there exists a sufficiently small convex neighbourhood U U U of s ∗ s^* s ∗ on which ∇ 2 m ( s ) ⪰ μ I \nabla^2m(s)\succeq\mu I ∇ 2 m ( s ) ⪰ μ I for some μ > 0 \mu>0 μ > 0 . Thus m m m is strongly convex on U U U , which gives the stated local PL inequality.
SoS-convexity and strict Gram representations. Ahmadi, Chaudhry and Zhang [1 Lemmas 2–3] show that ∥ x ∥ 2 + ∥ x ∥ 2 d \lVert x\rVert^2+\lVert x\rVert^{2d} ∥ x ∥ 2 + ∥ x ∥ 2 d lies in the interior of the SoS-convex cone, and use this property to construct SoS-convex Taylor approximations. This raises a natural question about the relationship between interior SoS-convexity and the strict Gram representations studied here. We first give an example showing that a strict Gram representation may exist even when the polynomial is nonconvex. We then show that an interior SoS-convex certificate is sufficient for a strict Gram representation, but not necessary.
Example 4.2 (Strict Gram before global convexification). Consider the bivariate quartic polynomial
m σ ( x , y ) = 137 800 x + x 2 + y 2 + x 3 + σ 4 ( x 2 + y 2 ) 2 , σ > 0. m_{\sigma}(x,y)=\frac{137}{800}x+x^2+y^2+x^3+\frac{\sigma}{4}(x^2+y^2)^2,\qquad\sigma>0. m σ ( x , y ) = 800 137 x + x 2 + y 2 + x 3 + 4 σ ( x 2 + y 2 ) 2 , σ > 0.
It has a nonzero linear term and is locally strongly convex at the origin, since ∇ 2 m σ ( 0 , 0 ) = 2 I \nabla^2m_{\sigma}(0,0)=2I ∇ 2 m σ ( 0 , 0 ) = 2 I . For every σ > 0 \sigma>0 σ > 0 , the shifted polynomial m σ − m ∗ m_{\sigma}-m^* m σ − m ∗ is SoS, by the classical result on nonnegative bivariate quartics. Moreover, at σ = 5 / 4 \sigma=5/4 σ = 5/4 , the unique global minimizer is s ∗ = ( − 1 / 10 , 0 ) s^*=(-1/10,0) s ∗ = ( − 1/10 , 0 ) , and the shifted polynomial admits a positive-definite Gram representation on all nonconstant monomials of degrees one and two. Nevertheless, m 5 / 4 m_{5/4} m 5/4 is not globally convex. Indeed, direct calculation gives the exact convexity threshold
σ c o n v e x = 3 2 , and σ S o S c o n v e x = 3 2 . \sigma_{\mathrm{convex}}=\frac{3}{2},\qquad\text{and}\qquad\sigma_{\mathrm{SoSconvex}}=\frac{3}{2}. σ convex = 2 3 , and σ SoSconvex = 2 3 .
as convexity and SoS-convexity coincide for bivariate quartics [2 ] . Thus, this example has
σ S o S = 0 , σ s t r i c t ≤ 5 4 < σ c o n v e x = σ S o S c o n v e x = 3 2 . \sigma_{\mathrm{SoS}}=0,\qquad\sigma_{\mathrm{strict}}\le\frac{5}{4}<\sigma_{\mathrm{convex}}=\sigma_{\mathrm{SoSconvex}}=\frac{3}{2}. σ SoS = 0 , σ strict ≤ 4 5 < σ convex = σ SoSconvex = 2 3 .
In particular, strict Gram exactness can occur before global convexification, even when the polynomial is locally strongly convex at the regularization centre.
Helton and Nie [13 Lemma 8] showed that a polynomial with an SoS Hessian and a stationary zero is SoS, while Ahmadi and Parrilo [2 Theorem 3.1] established the corresponding first-order SoS characterization of SoS-convexity. The following lemma records a stronger conclusion when the Hessian SoS representation has a positive-definite Gram matrix.
Lemma 4.2 (Interior SoS-convexity implies strict Gram). Let h h h be a strictly SoS-convex polynomial of degree at most 2 d 2d 2 d , namely
y T ∇ 2 h ( x ) y = w ( x , y ) T M w ( x , y ) , M ≻ 0 , y^{\mathsf T}\nabla^2h(x)y=\mathbf{w}(x,y)^{\mathsf T}M\mathbf{w}(x,y),\qquad M\succ0, y T ∇ 2 h ( x ) y = w ( x , y ) T M w ( x , y ) , M ≻ 0 , where w ( x , y ) = ( y i x α ) 1 ≤ i ≤ n , ∣ α ∣ ≤ d − 1 \mathbf{w}(x,y)=\left(y_i x^\alpha\right)_{1\le i\le n,\ |\alpha|\le d-1} w ( x , y ) = ( y i x α ) 1 ≤ i ≤ n , ∣ α ∣ ≤ d − 1 . Then h h h has a unique global minimizer s ∗ s^* s ∗ , and the shifted polynomial h ( s ∗ + v ) − h ( s ∗ ) h(s^*+v)-h(s^*) h ( s ∗ + v ) − h ( s ∗ ) admits a strict Gram representation on v d ( v ) v_d(v) v d ( v ) .
Proof. By stationarity and Taylor’s integral formula,
h ( s ∗ + v ) − h ( s ∗ ) = ∫ 0 1 ( 1 − t ) v T ∇ 2 h ( s ∗ + t v ) v d t . h(s^*+v)-h(s^*)=\int_0^1(1-t)v^{\mathsf T}\nabla^2h(s^*+tv)v\,dt. h ( s ∗ + v ) − h ( s ∗ ) = ∫ 0 1 ( 1 − t ) v T ∇ 2 h ( s ∗ + t v ) v d t .
Substituting the assumed Hessian representation, the integrand is a positive-definite quadratic form in the polynomials
v i ( s ∗ + t v ) α , 1 ≤ i ≤ n , ∣ α ∣ ≤ d − 1. v_i(s^*+tv)^\alpha,\qquad1\le i\le n,\quad|\alpha|\le d-1. v i ( s ∗ + t v ) α , 1 ≤ i ≤ n , ∣ α ∣ ≤ d − 1.
Let Q Q Q denote the resulting Gram matrix on v d ( v ) v_d(v) v d ( v ) . If Q Q Q were singular, there would exist a nonzero vector ξ \xi ξ orthogonal to the coefficient vectors of all these polynomials for almost every t ∈ ( 0 , 1 ) t\in(0,1) t ∈ ( 0 , 1 ) . Since these coefficient vectors are polynomial in t t t , the same orthogonality would hold at t = 1 t=1 t = 1 . However, the polynomials v i ( s ∗ + v ) α v_i(s^*+v)^\alpha v i ( s ∗ + v ) α span all polynomials with zero constant term and degree at most d d d : translation preserves the polynomial space of degree at most d − 1 d-1 d − 1 , and multiplication by v i v_i v i generates every nonconstant monomial. Thus ξ = 0 \xi=0 ξ = 0 , a contradiction. Consequently, Q ≻ 0 Q\succ0 Q ≻ 0 .
Trust Regions and Regularization
The previous section used regularization. We now compare it with a trust-region constraint. The main observation is that, when the trust-region solution lies on the boundary, its multiplier selects a matching regularization parameter. With this choice the two shifted polynomial gaps are the same. This lets the SoS certificate pass from one formulation to the other. We then show that small trust-region radii correspond to large regularization, and we treat the interior cubic case separately.
We have therefore completed the main chain of the paper:
large regularization ⟹ \Longrightarrow ⟹ strict Gram dominance ⟹ \Longrightarrow ⟹ exact SoS representation ⟹ \Longrightarrow ⟹ rank-one minimizer recovery.
The next section connects this unconstrained regularization picture with the other classical globalization mechanism for Taylor models: trust regions.
Matching Trust-Region and Regularized Models
We first make the boundary correspondence exact. The T R + \mathrm{TR}^{+} TR + formulation keeps the same feasible ball but uses a higher even radial term in the certificate. The benefit is that, at an active solution, this certificate can be matched exactly with the regularized Taylor model. Recall that
T 2 d − 1 ( s ) = f 0 + g ⊤ s + ∑ j = 2 2 d − 1 1 j ! T j [ s j ] , (36) \mathcal{T}_{2d-1}(s) = f_0 + g^\top s + \sum_{j=2}^{2d-1} \frac{1}{j!}\mathcal{T}_j[s^j], \tag*{(36)} T 2 d − 1 ( s ) = f 0 + g ⊤ s + j = 2 ∑ 2 d − 1 j ! 1 T j [ s j ] , (36)
with d ≥ 2 d \ge2 d ≥ 2 . The standard trust-region problem is
s Δ ∗ ∈ arg min ∥ s ∥ ≤ Δ T 2 d − 1 ( s ) , s_{\Delta}^{*} \in\mathop{\arg\min}_{\lVert s\rVert\le\Delta} \mathcal{T}_{2d-1}(s), s Δ ∗ ∈ arg min ∥ s ∥ ≤ Δ T 2 d − 1 ( s ) ,
with standard Lagrangian
L T R ( s , λ ) = T 2 d − 1 ( s ) + λ 2 ( ∥ s ∥ 2 − Δ 2 ) , λ ≥ 0. L_{\mathrm{TR}}(s,\lambda) = \mathcal{T}_{2d-1}(s) + \frac{\lambda}{2}\left(\lVert s\rVert^2-\Delta^2\right), \qquad\lambda\ge0. L TR ( s , λ ) = T 2 d − 1 ( s ) + 2 λ ( ∥ s ∥ 2 − Δ 2 ) , λ ≥ 0.
Its active-boundary stationarity condition is ∇ T 2 d − 1 ( s Δ ∗ ) + λ Δ s Δ ∗ = 0 \nabla\mathcal{T}_{2d-1}(s_{\Delta}^{*})+\lambda_{\Delta}s_{\Delta}^{*}=0 ∇ T 2 d − 1 ( s Δ ∗ ) + λ Δ s Δ ∗ = 0 , ∥ s Δ ∗ ∥ = Δ \lVert s_{\Delta}^{*}\rVert=\Delta ∥ s Δ ∗ ∥ = Δ .
We define a new trust-region formulation, denoted by T R + \mathrm{TR}^{+} TR + , which uses the same feasible ball but replaces the quadratic localizer by a higher radial one. Equivalently, one may raise the radial constraint to degree 2 d 2d 2 d :
∥ s ∥ 2 ≤ Δ 2 ⟺ ∥ s ∥ 2 d ≤ Δ 2 d . \lVert s\rVert^2 \le\Delta^2 \Longleftrightarrow\lVert s\rVert^{2d} \le\Delta^{2d}. ∥ s ∥ 2 ≤ Δ 2 ⟺ ∥ s ∥ 2 d ≤ Δ 2 d .
For d ≥ 2 d \ge2 d ≥ 2 , we define the T R + \mathrm{TR}^{+} TR + Lagrangian polynomial (a normalized higher-radial Lagrangian, i.e. a global certificate polynomial) by
L Δ , λ ( s ) : = T 2 d − 1 ( s ) + λ 2 d Δ 2 d − 2 ( ∥ s ∥ 2 d − Δ 2 d ) . \mathcal{L}_{\Delta,\lambda}(s) := \mathcal{T}_{2d-1}(s) + \frac{\lambda}{2d\Delta^{2d-2}}\left(\lVert s\rVert^{2d}-\Delta^{2d}\right). L Δ , λ ( s ) := T 2 d − 1 ( s ) + 2 d Δ 2 d − 2 λ ( ∥ s ∥ 2 d − Δ 2 d ) .
Clearly, the trust-region constraint ∥ s ∥ 2 ≤ Δ 2 \lVert s\rVert^2 \le\Delta^2 ∥ s ∥ 2 ≤ Δ 2 and the higher radial constraint ∥ s ∥ 2 d ≤ Δ 2 d \lVert s\rVert^{2d} \le\Delta^{2d} ∥ s ∥ 2 d ≤ Δ 2 d define the same ball. Moreover, under the normalization 1 2 d Δ 2 d − 2 ( ∥ s ∥ 2 d − Δ 2 d ) \frac{1}{2d\Delta^{2d-2}}(\lVert s\rVert^{2d}-\Delta^{2d}) 2 d Δ 2 d − 2 1 (∥ s ∥ 2 d − Δ 2 d ) , they have the same active-boundary stationarity equation ∇ T 2 d − 1 ( s ∗ ) + λ s ∗ = 0 \nabla\mathcal{T}_{2d-1}(s^{*})+\lambda s^{*}=0 ∇ T 2 d − 1 ( s ∗ ) + λ s ∗ = 0 . Indeed, the normalization is chosen so that, on ∥ s ∥ = Δ \lVert s\rVert=\Delta ∥ s ∥ = Δ ,
∇ [ 1 2 d Δ 2 d − 2 ( ∥ s ∥ 2 d − Δ 2 d ) ] ∥ s ∥ = Δ = s . \nabla\left[\frac{1}{2d\Delta^{2d-2}}\left(\lVert s\rVert^{2d}-\Delta^{2d}\right)\right]_{\lVert s\rVert=\Delta}=s. ∇ [ 2 d Δ 2 d − 2 1 ( ∥ s ∥ 2 d − Δ 2 d ) ] ∥ s ∥ = Δ = s .
We say that the T R + \mathrm{TR}^{+} TR + certificate (Lagrangian-T R + \mathrm{TR}^{+} TR + ) is exact at an active trust-region minimizer s Δ ∗ s_{\Delta}^{*} s Δ ∗ , with multiplier λ Δ \lambda_{\Delta} λ Δ , if
L Δ , λ Δ ( s ) − L Δ , λ Δ ( s Δ ∗ ) ∈ Σ [ s ] 2 d . (37) \mathcal{L}_{\Delta,\lambda_{\Delta}}(s)-\mathcal{L}_{\Delta,\lambda_{\Delta}}(s_{\Delta}^{*}) \in\Sigma[s]_{2d}. \tag*{(37)} L Δ , λ Δ ( s ) − L Δ , λ Δ ( s Δ ∗ ) ∈ Σ [ s ] 2 d . (37)
where λ Δ \lambda_{\Delta} λ Δ represents the Lagrangian multiplier corresponding to s Δ ∗ s_{\Delta}^{*} s Δ ∗ .
Thus, when the constraint is active, TR and T R + \mathrm{TR}^{+} TR + have the same KKT equation, but they play different roles. The standard TR formulation is the constrained optimization problem, whereas T R + \mathrm{TR}^{+} TR + uses the same feasible ball to provide a global SOS certificate. The third related object is the unconstrained regularized model
s σ ∗ ∈ arg min s ∈ R n m σ ( s ) , m σ ( s ) : = T 2 d − 1 ( s ) + σ 2 d ∥ s ∥ 2 d . s_{\sigma}^{*} \in\mathop{\arg\min}_{s\in\mathbb{R}^n} m_{\sigma}(s), \qquad m_{\sigma}(s) := \mathcal{T}_{2d-1}(s) + \frac{\sigma}{2d}\lVert s\rVert^{2d}. s σ ∗ ∈ arg min s ∈ R n m σ ( s ) , m σ ( s ) := T 2 d − 1 ( s ) + 2 d σ ∥ s ∥ 2 d .
The next proposition makes precise the shared active-boundary KKT geometry of TR and T R + \mathrm{TR}^{+} TR + , and the matching relation with the regularized model when the radius is chosen consistently.
Proposition 5.1 (Matched trust-region and regularized formulations). Let d ≥ 2 d \ge2 d ≥ 2 and Δ > 0 \Delta> 0 Δ > 0 , and let s Δ ∗ s_\Delta^* s Δ ∗ be a global minimizer of the trust-region problem (TR) at which the constraint is active, ∥ s Δ ∗ ∥ = Δ \lVert s_\Delta^* \rVert= \Delta ∥ s Δ ∗ ∥ = Δ . Then the following hold.
s Δ ∗ s_\Delta^* s Δ ∗ satisfies the active-boundary KKT equation ∇ T 2 d − 1 ( s Δ ∗ ) + λ Δ s Δ ∗ = 0 \nabla T_{2d-1}(s_\Delta^*) + \lambda_\Delta s_\Delta^* = 0 ∇ T 2 d − 1 ( s Δ ∗ ) + λ Δ s Δ ∗ = 0 for some multiplier λ Δ ≥ 0 \lambda_\Delta\ge0 λ Δ ≥ 0 .
(Matching.) Set σ : = λ Δ / Δ 2 d − 2 \sigma:= \lambda_\Delta/\Delta^{2d-2} σ := λ Δ / Δ 2 d − 2 . Then the matched T R + \mathrm{TR}^{+} TR + Lagrangian gap coincides, as a polynomial in s s s , with the shifted regularized gap:
L Δ , λ Δ ( s ) − L Δ , λ Δ ( s Δ ∗ ) = m σ ( s ) − m σ ( s Δ ∗ ) . \mathcal{L}_{\Delta,\lambda_\Delta}(s) - \mathcal{L}_{\Delta,\lambda_\Delta}(s_\Delta^*) = m_\sigma(s) - m_\sigma(s_\Delta^*). L Δ , λ Δ ( s ) − L Δ , λ Δ ( s Δ ∗ ) = m σ ( s ) − m σ ( s Δ ∗ ) . with m σ m_\sigma m σ as in (Regularized model). Consequently, the T R + \mathrm{TR}^{+} TR + Lagrangian gap is SOS exact at ( Δ , λ Δ ) (\Delta,\lambda_\Delta) ( Δ , λ Δ ) if and only if the shifted regularized polynomial m σ ( s ) − m σ ( s Δ ∗ ) m_\sigma(s) - m_\sigma(s_\Delta^*) m σ ( s ) − m σ ( s Δ ∗ ) is SOS exact.
(Converse matching.) If s σ ∗ ≠ 0 s_\sigma^* \ne0 s σ ∗ = 0 is a global minimizer of m σ m_\sigma m σ in (Regularized model), then, with Δ : = ∥ s σ ∗ ∥ \Delta:= \lVert s_\sigma^* \rVert Δ := ∥ s σ ∗ ∥ , the point s σ ∗ s_\sigma^* s σ ∗ is a global minimizer of the trust-region problem min ∥ s ∥ ≤ Δ T 2 d − 1 ( s ) \min_{\lVert s\rVert\le\Delta} T_{2d-1}(s) min ∥ s ∥ ≤ Δ T 2 d − 1 ( s ) , the constraint is active, and items 1–2 hold with multiplier λ Δ = σ Δ 2 d − 2 > 0 \lambda_\Delta= \sigma\Delta^{2d-2} > 0 λ Δ = σ Δ 2 d − 2 > 0 .
Proof. (1) At an active minimizer, the gradient of the constraint ∥ s ∥ 2 − Δ 2 \lVert s\rVert^2-\Delta^2 ∥ s ∥ 2 − Δ 2 is 2 s Δ ∗ ≠ 0 2s_\Delta^* \ne0 2 s Δ ∗ = 0 , so the linear independence constraint qualification holds on the boundary and the KKT conditions produce a multiplier λ Δ ≥ 0 \lambda_\Delta\ge0 λ Δ ≥ 0 with ∇ T 2 d − 1 ( s Δ ∗ ) + λ Δ s Δ ∗ = 0 \nabla T_{2d-1}(s_\Delta^*) + \lambda_\Delta s_\Delta^* = 0 ∇ T 2 d − 1 ( s Δ ∗ ) + λ Δ s Δ ∗ = 0 .
(2) Since ∥ s Δ ∗ ∥ = Δ \lVert s_\Delta^* \rVert= \Delta ∥ s Δ ∗ ∥ = Δ , the localizer vanishes at s Δ ∗ s_\Delta^* s Δ ∗ , and with σ = λ Δ / Δ 2 d − 2 \sigma= \lambda_\Delta/\Delta^{2d-2} σ = λ Δ / Δ 2 d − 2 ,
λ Δ 2 d Δ 2 d − 2 ( ∥ s ∥ 2 d − Δ 2 d ) = σ 2 d ( ∥ s ∥ 2 d − ∥ s Δ ∗ ∥ 2 d ) . \frac{\lambda_\Delta}{2d\Delta^{2d-2}}\left(\lVert s\rVert^{2d}-\Delta^{2d}\right)=\frac{\sigma}{2d}\left(\lVert s\rVert^{2d}-\lVert s_\Delta^*\rVert^{2d}\right). 2 d Δ 2 d − 2 λ Δ ( ∥ s ∥ 2 d − Δ 2 d ) = 2 d σ ( ∥ s ∥ 2 d − ∥ s Δ ∗ ∥ 2 d ) .
Adding T 2 d − 1 ( s ) − T 2 d − 1 ( s Δ ∗ ) T_{2d-1}(s)-T_{2d-1}(s_\Delta^*) T 2 d − 1 ( s ) − T 2 d − 1 ( s Δ ∗ ) to both sides gives the polynomial identity of item 2; the SOS equivalence is immediate from the identity.
(3) Since s σ ∗ s_\sigma^* s σ ∗ is a global minimizer of m σ m_\sigma m σ , for every s s s with ∥ s ∥ ≤ Δ = ∥ s σ ∗ ∥ \lVert s\rVert\le\Delta= \lVert s_\sigma^*\rVert ∥ s ∥ ≤ Δ = ∥ s σ ∗ ∥ ,
T 2 d − 1 ( s ) − T 2 d − 1 ( s σ ∗ ) ≥ σ 2 d ( Δ 2 d − ∥ s ∥ 2 d ) ≥ 0 , T_{2d-1}(s)-T_{2d-1}(s_\sigma^*) \ge\frac{\sigma}{2d}\left(\Delta^{2d}-\lVert s\rVert^{2d}\right) \ge0, T 2 d − 1 ( s ) − T 2 d − 1 ( s σ ∗ ) ≥ 2 d σ ( Δ 2 d − ∥ s ∥ 2 d ) ≥ 0 ,
so s σ ∗ s_\sigma^* s σ ∗ is a global minimizer of the trust-region problem with radius Δ \Delta Δ , attained on the boundary because s σ ∗ ≠ 0 s_\sigma^* \ne0 s σ ∗ = 0 . The first-order condition ∇ T 2 d − 1 ( s σ ∗ ) + σ ∥ s σ ∗ ∥ 2 d − 2 s σ ∗ = 0 \nabla T_{2d-1}(s_\sigma^*)+\sigma\lVert s_\sigma^*\rVert^{2d-2}s_\sigma^*=0 ∇ T 2 d − 1 ( s σ ∗ ) + σ ∥ s σ ∗ ∥ 2 d − 2 s σ ∗ = 0 is the KKT equation of item 1 with λ Δ = σ Δ 2 d − 2 \lambda_\Delta=\sigma\Delta^{2d-2} λ Δ = σ Δ 2 d − 2 , and item 2 applies verbatim.
:::
Small Trust Regions and Large Regularization
The matching formula has a simple consequence: shrinking the trust-region radius increases the matching regularization parameter. Thus the small-radius regime is the trust-region version of the large-regularization regime studied in § 4 .
Proposition 5.1 identifies shrinking the trust-region radius with increasing the regularization weight: the matched parameter is σ = λ Δ / Δ 2 d − 2 \sigma=\lambda_\Delta/\Delta^{2d-2} σ = λ Δ / Δ 2 d − 2 , and, by the boundary expansion of Lemma 5.1 below, the active multiplier satisfies λ Δ Δ → ∥ g ∥ \lambda_\Delta\Delta\to\lVert g\rVert λ Δ Δ → ∥ g ∥ as Δ ↓ 0 \Delta\downarrow0 Δ ↓ 0 , so that
σ = λ Δ Δ 2 d − 2 = ∥ g ∥ Δ 2 d − 1 ( 1 + o ( 1 ) ) ⟶ ∞ . \sigma=\frac{\lambda_\Delta}{\Delta^{2d-2}}=\frac{\lVert g\rVert}{\Delta^{2d-1}}(1+o(1))\longrightarrow\infty. σ = Δ 2 d − 2 λ Δ = Δ 2 d − 1 ∥ g ∥ ( 1 + o ( 1 )) ⟶ ∞.
Consequently, when a trust-region scheme keeps shrinking the radius at a nonstationary point, it is implicitly driving the matched regularized model into the large-σ \sigma σ regime of § 4 . The next lemma gives the first half of this picture: an explicit radius threshold, depending only on the coefficients of the higher-order Taylor terms, below which the global trust-region minimizer is forced onto the boundary.
For the small-radius estimate below, let
Λ j : = max ∥ v 1 ∥ = ⋯ = ∥ v j ∥ = 1 ∣ T j [ v 1 , … , v j ] ∣ \Lambda_j := \max_{\lVert v_1\rVert=\cdots=\lVert v_j\rVert=1}\lvert T_j[v_1,\ldots,v_j]\rvert Λ j := ∥ v 1 ∥ = ⋯ = ∥ v j ∥ = 1 max ∣ T j [ v 1 , … , v j ]∣
denote the operator norm of the symmetric tensor T j T_j T j (and hence Λ 2 = ∥ H ∥ 2 \Lambda_2=\lVert H\rVert_2 Λ 2 = ∥ H ∥ 2 ).
The next lemma shows that, when the linear term is nonzero, sufficiently small trust-region subproblems are forced to attain their global minimizer on the boundary. The radius threshold is controlled explicitly by the tensor norms of the higher-order terms.
Lemma 5.1 (Global minimizer on the boundary for small radius). Let T 2 d − 1 \mathcal{T}_{2d-1} T 2 d − 1 be defined as in (36) , and assume g ≠ 0 g \ne0 g = 0 . Define
A T : = ∑ j = 2 2 d − 1 Λ j ( j − 1 ) ! . A_T := \sum_{j=2}^{2d-1} \frac{\Lambda_j}{(j-1)!}. A T := j = 2 ∑ 2 d − 1 ( j − 1 )! Λ j . where the constant A T A_T A T depends only on the coefficients H , T 3 , … , T 2 d − 1 H,T_3,\ldots,\mathcal{T}_{2d-1} H , T 3 , … , T 2 d − 1 of T 2 d − 1 \mathcal{T}_{2d-1} T 2 d − 1 . Let
Δ ‾ b d : = { 1 , A T = 0 , min { 1 , ∥ g ∥ 2 A T } , A T > 0. (38) \overline{\Delta}_{\mathrm{bd}} :=
\begin{cases}
1, & A_T = 0,\\
\min\left\{1,\frac{\lVert g\rVert}{2A_T}\right\}, & A_T > 0.
\end{cases} \tag*{(38)} Δ bd := { 1 , min { 1 , 2 A T ∥ g ∥ } , A T = 0 , A T > 0. (38) Then, for every 0 < Δ ≤ Δ ‾ b d 0 < \Delta\le\overline{\Delta}_{\mathrm{bd}} 0 < Δ ≤ Δ bd , every global minimizer s Δ ∗ ∈ a r g m i n ∥ s ∥ ≤ Δ T 2 d − 1 ( s ) s_\Delta^* \in\mathop{\mathrm{argmin}}_{\lVert s\rVert\le\Delta} \mathcal{T}_{2d-1}(s) s Δ ∗ ∈ argmin ∥ s ∥ ≤ Δ T 2 d − 1 ( s ) lies on the boundary, ∥ s Δ ∗ ∥ = Δ \lVert s_\Delta^*\rVert= \Delta ∥ s Δ ∗ ∥ = Δ . After possibly decreasing Δ ‾ b d \overline{\Delta}_{\mathrm{bd}} Δ bd , the minimizer is unique and satisfies s Δ ∗ = − Δ g ∥ g ∥ + O ( Δ 2 ) s_\Delta^* = -\Delta\frac{g}{\lVert g\rVert} + O(\Delta^2) s Δ ∗ = − Δ ∥ g ∥ g + O ( Δ 2 ) .
Proof. Write T 2 d − 1 ( s ) = f 0 + g ⊤ s + E ( s ) \mathcal{T}_{2d-1}(s) = f_0 + g^\top s + E(s) T 2 d − 1 ( s ) = f 0 + g ⊤ s + E ( s ) , where ∇ E ( s ) = O ( ∥ s ∥ ) \nabla E(s) = O(\lVert s\rVert) ∇ E ( s ) = O (∥ s ∥) on the unit ball. By the definition of A T A_T A T , ∥ ∇ E ( s ) ∥ ≤ A T ∥ s ∥ \lVert\nabla E(s)\rVert\le A_T\lVert s\rVert ∥ ∇ E ( s )∥ ≤ A T ∥ s ∥ for ∥ s ∥ ≤ 1 \lVert s\rVert\le1 ∥ s ∥ ≤ 1 . An interior minimizer with ∥ s ∥ < Δ ≤ Δ ‾ b d \lVert s\rVert< \Delta\le\overline{\Delta}_{\mathrm{bd}} ∥ s ∥ < Δ ≤ Δ bd would satisfy g + ∇ E ( s ) = 0 g + \nabla E(s) = 0 g + ∇ E ( s ) = 0 , and hence ∥ g ∥ ≤ A T Δ ≤ ∥ g ∥ / 2 \lVert g\rVert\le A_T\Delta\le\lVert g\rVert/2 ∥ g ∥ ≤ A T Δ ≤ ∥ g ∥ /2 , a contradiction.
For uniqueness and the expansion, set s = Δ y s = \Delta y s = Δ y and consider F Δ ( y ) = [ T 2 d − 1 ( Δ y ) − f 0 ] / Δ F_\Delta(y) = [\mathcal{T}_{2d-1}(\Delta y) - f_0]/\Delta F Δ ( y ) = [ T 2 d − 1 ( Δ y ) − f 0 ] /Δ on ∥ y ∥ ≤ 1 \lVert y\rVert\le1 ∥ y ∥ ≤ 1 . Then F Δ ( y ) = g ⊤ y + O ( Δ ) F_\Delta(y) = g^\top y + O(\Delta) F Δ ( y ) = g ⊤ y + O ( Δ ) uniformly in C 2 C^2 C 2 . The limiting linear problem has the unique solution y 0 = − g / ∥ g ∥ y_0 = -g/\lVert g\rVert y 0 = − g / ∥ g ∥ on the sphere, so all minimizers approach y 0 y_0 y 0 . In a sufficiently small spherical neighborhood of y 0 y_0 y 0 , the restriction of g ⊤ y g^\top y g ⊤ y has a positive-definite tangential Hessian. This remains true for F Δ F_\Delta F Δ when Δ \Delta Δ is small, giving a unique minimizer y Δ = y 0 + O ( Δ ) y_\Delta= y_0 + O(\Delta) y Δ = y 0 + O ( Δ ) and thus the claimed expansion. □
Proposition 5.2 (Small-radius SoS exactness). Assume g ≠ 0 g \ne0 g = 0 . For all sufficiently small Δ > 0 \Delta> 0 Δ > 0 , the global minimizer s Δ ∗ s_\Delta^* s Δ ∗ of the trust-region problem is unique and lies on the boundary. Its matched TR+ ^+ + Lagrangian gap admits a strict Gram representation in v = s − s Δ ∗ v = s - s_\Delta^* v = s − s Δ ∗ . Consequently, the degree-d d d moment relaxation is exact and recovers s Δ ∗ s_\Delta^* s Δ ∗ from its unique rank-one optimal moment matrix.
Proof. By Lemma 5.1, s Δ ∗ = − Δ g / ∥ g ∥ + O ( Δ 2 ) s_\Delta^* = -\Delta g/\lVert g\rVert+ O(\Delta^2) s Δ ∗ = − Δ g / ∥ g ∥ + O ( Δ 2 ) . The active KKT equation and ∇ T 2 d − 1 ( s Δ ∗ ) = g + O ( Δ ) \nabla\mathcal{T}_{2d-1}(s_\Delta^*) = g + O(\Delta) ∇ T 2 d − 1 ( s Δ ∗ ) = g + O ( Δ ) therefore give λ Δ Δ → ∥ g ∥ \lambda_\Delta\Delta\to\lVert g\rVert λ Δ Δ → ∥ g ∥ , so λ Δ → ∞ \lambda_\Delta\to\infty λ Δ → ∞ as Δ ↓ 0 \Delta\downarrow0 Δ ↓ 0 . By Proposition 5.1, the shifted TR+ ^+ + gap equals the shifted model with σ = λ Δ / Δ 2 d − 2 \sigma= \lambda_\Delta/\Delta^{2d-2} σ = λ Δ / Δ 2 d − 2 . Its Taylor perturbation has no constant or linear term and has uniformly bounded coefficients as s Δ ∗ → 0 s_\Delta^* \to0 s Δ ∗ → 0 . The Gram margin supplied by σ d R s Δ ∗ , d \frac{\sigma}{d}R_{s_\Delta^*,d} d σ R s Δ ∗ , d is at least c n , d d σ Δ 2 d − 2 = c n , d d λ Δ → ∞ \frac{c_{n,d}}{d}\sigma\Delta^{2d-2} = \frac{c_{n,d}}{d}\lambda_\Delta\to\infty d c n , d σ Δ 2 d − 2 = d c n , d λ Δ → ∞ . Thus Theorem 4.1 gives a strict Gram matrix for sufficiently small Δ \Delta Δ , and Theorem 4.2 gives rank-one recovery. □
Remark 5.1 (Use within adaptive regularization and trust-region frameworks). The polynomial subproblems considered here are closely related to those used in adaptive regularization and trust-region methods [6 Chs. 3–4] ; see also [4 , 7 ] . The standard ARp p p method uses a p + 1 p+1 p + 1 power, whereas our SoS analysis requires an even polynomial degree; the trust-region certificate likewise uses the matched higher-radial TR+ ^+ + formulation. At a nonstationary iterate, sufficiently large σ k \sigma_k σ k , or a sufficiently small trust-region radius Δ k \Delta_k Δ k , yields an exact SoS certificate and rank-one recovery of the model minimizer. Under the usual smoothness and acceptance-ratio assumptions, a sufficiently large regularization parameter also ensures successful ARp p p iterations. Thus a certified inner solve can be incorporated into an adaptive scheme without changing its acceptance mechanism. A complete convergence and complexity analysis, including uniform thresholds, inexact SDP solutions and the cost of inner solves, is beyond the scope of this paper.
Interior Solutions in the Cubic Case
The matching argument above concerns boundary solutions. If a trust-region minimizer lies strictly inside the ball, the constraint is locally inactive, so the point is simply an unconstrained local minimizer of the polynomial. For cubic models, this case can be handled by the semidefinite local-minimum results of Ahmadi and Zhang.
Proposition 5.3 (Interior trust-region local minima). Let T 3 T_3 T 3 be a cubic polynomial and let Δ > 0 \Delta> 0 Δ > 0 . If s ∗ s^* s ∗ is a local minimizer of min ∥ s ∥ ≤ Δ T 3 ( s ) \min_{\lVert s\rVert\le\Delta} T_3(s) min ∥ s ∥ ≤ Δ T 3 ( s ) and satisfies ∥ s ∗ ∥ < Δ \lVert s^*\rVert< \Delta ∥ s ∗ ∥ < Δ , then s ∗ s^* s ∗ is an unconstrained local minimizer of T 3 T_3 T 3 . Conversely, any unconstrained local minimizer of T 3 T_3 T 3 that lies strictly inside the ball is a local minimizer of the trust-region problem.
Proof. If ∥ s ∗ ∥ < Δ \lVert s^*\rVert< \Delta ∥ s ∗ ∥ < Δ , then there exists a neighbourhood U U U of s ∗ s^* s ∗ such that U ⊂ { s : ∥ s ∥ < Δ } U \subset\{s : \lVert s\rVert< \Delta\} U ⊂ { s : ∥ s ∥ < Δ } . Hence constrained local minimality on the trust-region ball is equivalent to unconstrained local minimality on U U U . The converse follows from the same argument in reverse.
The two trust-region cases therefore fit together cleanly. On a sufficiently small active boundary, the multiplier matches the problem to the large-regularization regime and gives the same strict Gram/SoS certificate. In the cubic interior case, one instead uses an unconstrained local-minimum oracle. This completes the connection between the strict-Gram theory above and trust-region globalization.
Conclusion
This paper studies when the polynomial subproblems arising in higher-order optimization become exactly solvable through a single SoS/moment semidefinite representation. Our main result shows that, under a nonzero linear term and sufficient Euclidean regularization, the nonnegative polynomial obtained by shifting a higher-order Taylor model by its global minimum is SoS. For every fixed degree, the resulting SDP has polynomial size in the dimension, and its rank-one moment solution recovers the unique global minimizer. Importantly, this conclusion does not require the regularized polynomial to be convex or SoS-convex.
The proof identifies the structural reason behind this phenomenon. The Bregman remainder of the Euclidean radial regularizer has a strict Gram representation at every nonzero point, with a strict Gram margin. This margin eventually dominates the bounded lower-order Taylor terms. The same viewpoint also explains a genuine boundary: some regularizers inherit the strict Gram property, whereas coordinate-separable regularization does not control the mixed polynomial directions required by the argument. Thus not only the amount and degree of regularization, but also its algebraic structure, determine SoS exactness.
The trust-region results provide a second interpretation. At an active boundary solution, the multiplier defines a matched radial regularization, and the small-radius regime corresponds precisely to the large-regularization regime of the main theorem. For cubic models, the complementary interior case is also tractable through the semidefinite characterization of cubic local minima.
Several broader questions remain open. The first is how far the tractable regime identified in this paper can be extended beyond sufficient regularization. Our results show that sufficiently strong regularization can turn a structured nonconvex higher-order polynomial subproblem into an exact SoS/SDP problem of polynomial size for every fixed degree. A natural next question is whether the same phenomenon persists under substantially weaker regularization. General polynomial optimization is of course intractable, so such a result cannot hold without additional structure; the challenge is to identify how much structure is sufficient for exact global optimization to remain possible.
A second fundamental issue is scalability. Although the SoS/moment formulation obtained here has polynomial size for fixed degree, standard SDP representations still grow rapidly with the dimension and can become expensive in practice. There are, however, reasons for optimism. The proof developed in this paper does more than establish SoS exactness: it exposes specific algebraic structure in the Gram representation generated by the regularization term. Related low-order models already show that exploiting such structure can lead to substantially smaller tight SDP formulations, including linear-size formulations in certain cubic–quartic settings [25 , 8 ] .
This suggests that symmetry, sparsity, low-rank tensor structure, and the particular Gram structure revealed here may be used to construct much smaller exact or approximate formulations. Turning these structural observations into scalable global solvers, and ultimately incorporating them into globally convergent higher-order methods, is an important direction for future research.
More broadly, the results suggest that the computational difficulty of higher-order polynomial models is governed not only by their degree, but by the algebraic structure created by regularization. Understanding and exploiting this structure may provide a route from worst-case polynomial hardness to globally solvable and practically scalable subclasses.
Declaration of generative AI and AI-assisted technologies. During the preparation of this work, the authors used large language model systems (Claude, Anthropic; Codex models, OpenAI; Qwen, Alibaba) to assist in reviewing mathematical proofs for potential errors or gaps. The authors independently assessed the feedback and take full responsibility for the correctness and content of the publication.
Funding. The research of Coralia Cartis and Wenqi Zhu was also supported by the Engineering and Physical Sciences Research Council under grant EP/Y028872/1, *Mathematical Foundations of Intelligence: An “Erlangen Programme” for AI.
Competing interests. The authors have no relevant financial or non-financial interests to disclose.
Data availability. No datasets were generated or analysed during the current study.
Full Statements of the Cited SoS-Convexity Results
For completeness, and to make the citations in Remark 3.1 precise, we reproduce the two results of Ahmadi–Parrilo and Helton–Nie in the form in which they are used in § 3 .
Theorem A.1 (Ahmadi–Parrilo [2 Thm. 3.1] ). Let f ∈ R [ x ] f \in\mathbb{R}[x] f ∈ R [ x ] be a polynomial. The following are equivalent:
(i) the Hessian ∇ 2 f ( x ) \nabla^{2}f(x) ∇ 2 f ( x ) is an SoS matrix, i.e. y T ∇ 2 f ( x ) y y^{\mathsf{T}}\nabla^{2}f(x)y y T ∇ 2 f ( x ) y is a sum of squares in ( x , y ) (x,y) ( x , y ) (f f f is SoS-convex);
(ii) the first-order divergence f ( y ) − f ( x ) − ∇ f ( x ) T ( y − x ) f(y)-f(x)-\nabla f(x)^{\mathsf{T}}(y-x) f ( y ) − f ( x ) − ∇ f ( x ) T ( y − x ) is a sum of squares in ( x , y ) (x,y) ( x , y ) ;
(iii) the midpoint gap 1 2 f ( x ) + 1 2 f ( y ) − f ( x + y 2 ) \frac{1}{2}f(x)+\frac{1}{2}f(y)-f\left(\frac{x+y}{2}\right) 2 1 f ( x ) + 2 1 f ( y ) − f ( 2 x + y ) is a sum of squares in ( x , y ) (x,y) ( x , y ) .
In particular, SoS-convexity of f f f implies that every first-order Bregman divergence of f f f is SoS, jointly in the base point and the increment.
Lemma A.1 (Helton–Nie [13 Lem. 8] ). Let f ∈ R [ x ] f \in\mathbb{R}[x] f ∈ R [ x ] and suppose there exists a point u ∈ R n u \in\mathbb{R}^{n} u ∈ R n such that
f ( u ) = 0 , ∇ f ( u ) = 0 , f(u)=0,\qquad\nabla f(u)=0, f ( u ) = 0 , ∇ f ( u ) = 0 , and the Hessian ∇ 2 f ( x ) \nabla^{2}f(x) ∇ 2 f ( x ) is an SoS matrix. Then f f f is a sum of squares.
The point u u u in Lemma A.1 is the second-order contact point of f f f : f f f vanishes and is stationary at u u u , so that in the shifted variable v = x − u v=x-u v = x − u the polynomial has no constant or linear part. In our setting the lemma is applied to f ( v ) = R s , d ( v ) f(v)=R_{s,d}(v) f ( v ) = R s , d ( v ) with contact point u = 0 u=0 u = 0 : indeed R s , d ( 0 ) = 0 R_{s,d}(0)=0 R s , d ( 0 ) = 0 , ∇ v R s , d ( 0 ) = 0 \nabla_{v}R_{s,d}(0)=0 ∇ v R s , d ( 0 ) = 0 , and ∇ v 2 R s , d ( v ) = ∇ 2 Φ d ( s + v ) \nabla_{v}^{2}R_{s,d}(v)=\nabla^{2}\Phi_{d}(s+v) ∇ v 2 R s , d ( v ) = ∇ 2 Φ d ( s + v ) is an SoS matrix by the computation in the proof of Lemma 3.1. Either result therefore yields the qualitative SoS property of the Bregman remainder R s , d R_{s,d} R s , d . Neither result is quantitative: the strict Gram margin [8 ] , on which Theorem 4.1 rests, is established independently in Theorem 3.1.
Generic Veronese spanning
This is the usual Veronese embedding/spanning viewpoint; see, e.g., [12 Section 1.4] for the Veronese embedding in algebraic geometry, or [15 Chapter 2] for the symmetric tensor interpretation.
Lemma B.1 (Generic Veronese spanning). Let H n , q : = span { e β : ∣ β ∣ = q } \mathcal{H}_{n,q} := \operatorname{span}\{e_\beta: |\beta| = q\} H n , q := span { e β : ∣ β ∣ = q } denote the coefficient space of homogeneous degree-q q q polynomials in v ∈ R n v \in\mathbb{R}^n v ∈ R n . For a ∈ R n a \in\mathbb{R}^n a ∈ R n , define ν q ( a ) : = coeff ( ( a T v ) q ) ∈ H n , q \nu_q(a) := \operatorname{coeff}((a^\mathsf{T}v)^q) \in\mathcal{H}_{n,q} ν q ( a ) := coeff (( a T v ) q ) ∈ H n , q . Let d ≥ 1 d \ge1 d ≥ 1 , and suppose
m ≥ max 1 ≤ q ≤ d dim H n , q = max 1 ≤ q ≤ d ( n + q − 1 q ) = ( n + d − 1 d ) . m \ge\max_{1 \le q \le d} \dim\mathcal{H}_{n,q}
= \max_{1 \le q \le d} \binom{n+q-1}{q}
= \binom{n+d-1}{d}. m ≥ 1 ≤ q ≤ d max dim H n , q = 1 ≤ q ≤ d max ( q n + q − 1 ) = ( d n + d − 1 ) . Then, for a generic collection of vectors a 1 , … , a m ∈ R n a_1,\ldots,a_m \in\mathbb{R}^n a 1 , … , a m ∈ R n , we have
span { ν q ( a ℓ ) : ℓ = 1 , … , m } = H n , q , q = 1 , … , d . \operatorname{span}\{\nu_q(a_\ell) : \ell= 1,\ldots,m\} = \mathcal{H}_{n,q}, \qquad q = 1,\ldots,d. span { ν q ( a ℓ ) : ℓ = 1 , … , m } = H n , q , q = 1 , … , d . Equivalently, the Veronese matrices (i.e., multivariate homogeneous Vandermonde matrix)
M q = [ ν q ( a 1 ) ⋯ ν q ( a m ) ] ∈ R ( n + q − 1 q ) × m M_q = \left[\nu_q(a_1)\ \cdots\ \nu_q(a_m)\right] \in\mathbb{R}^{\binom{n+q-1}{q} \times m} M q = [ ν q ( a 1 ) ⋯ ν q ( a m ) ] ∈ R ( q n + q − 1 ) × m have full row rank for every q = 1 , … , d q = 1,\ldots,d q = 1 , … , d . Moreover, for fixed s ≠ 0 s \ne0 s = 0 , the same generic choice can be made so that a ℓ T s ≠ 0 a_\ell^\mathsf{T}s \ne0 a ℓ T s = 0 for every ℓ \ell ℓ .
Proof. First note that
dim H n , q = ( n + q − 1 q ) , max 1 ≤ q ≤ d dim H n , q = ( n + d − 1 d ) . \dim\mathcal{H}_{n,q} = \binom{n+q-1}{q}, \qquad
\max_{1 \le q \le d} \dim\mathcal{H}_{n,q} = \binom{n+d-1}{d}. dim H n , q = ( q n + q − 1 ) , 1 ≤ q ≤ d max dim H n , q = ( d n + d − 1 ) . as this quantity is nondecreasing in q q q . Fix q ∈ { 1 , … , d } q \in\{1,\ldots,d\} q ∈ { 1 , … , d } . The entries of M q M_q M q are polynomial functions of the vectors a 1 , … , a m a_1,\ldots,a_m a 1 , … , a m . Therefore the condition rank M q < dim H n , q \operatorname{rank} M_q < \dim\mathcal{H}_{n,q} rank M q < dim H n , q is an algebraic condition, given by the vanishing of all maximal minors of M q M_q M q . It remains to show that these minors are not all identically zero. Let N q : = dim H n , q N_q := \dim\mathcal{H}_{n,q} N q := dim H n , q . The homogeneous monomials { a β : ∣ β ∣ = q } \{a^\beta: |\beta| = q\} { a β : ∣ β ∣ = q } are linearly independent polynomial functions of a a a . Hence one can choose points
b 1 , … , b N q ∈ R n b_1,\ldots,b_{N_q} \in\mathbb{R}^n b 1 , … , b N q ∈ R n such that the homogeneous Vandermonde matrix [ b j β ] ∣ β ∣ = q , j = 1 , … , N q \left[b_j^\beta\right]_{|\beta|=q,\ j=1,\ldots,N_q} [ b j β ] ∣ β ∣ = q , j = 1 , … , N q is nonsingular. Since ν q ( b j ) \nu_q(b_j) ν q ( b j ) differs from ( b j β ) ∣ β ∣ = q \left(b_j^\beta\right)_{|\beta|=q} ( b j β ) ∣ β ∣ = q only by nonzero multinomial factors on the rows, the matrix
[ ν q ( b 1 ) ⋯ ν q ( b N q ) ] \left[\nu_q(b_1)\ \cdots\ \nu_q(b_{N_q})\right] [ ν q ( b 1 ) ⋯ ν q ( b N q ) ] also has full rank N q N_q N q . Thus at least one maximal minor of M q M_q M q is not the zero polynomial. Consequently, for each fixed q q q , the set of vectors ( a 1 , … , a m ) (a_1,\ldots,a_m) ( a 1 , … , a m ) for which M q M_q M q has full row rank is the complement of a proper algebraic set. Taking the finite intersection over q = 1 , … , d q = 1,\ldots,d q = 1 , … , d , we obtain a generic set on which all matrices M q M_q M q have full row rank simultaneously. Finally, for fixed s ≠ 0 s \ne0 s = 0 , the conditions a ℓ T s ≠ 0 a_\ell^\mathsf{T}s \ne0 a ℓ T s = 0 , ℓ = 1 , … , m \ell= 1,\ldots,m ℓ = 1 , … , m , exclude only finitely many proper hyperplanes. Intersecting with their complement preserves genericity. This proves the claim. □ \square □
Scaling of Global Minimizers under Large Regularization
Theorem C.1 (Scaling of the global minimizer). Assume that ∥ g ∥ ≠ 0 \lVert g\rVert\ne0 ∥ g ∥ = 0 , and let s σ ∗ s_\sigma^* s σ ∗ satisfy
∇ m σ ( s σ ∗ ) = 0 , m σ ( s σ ∗ ) ≤ m σ ( 0 ) . \nabla m_\sigma(s_\sigma^*) = 0, \qquad m_\sigma(s_\sigma^*) \le m_\sigma(0). ∇ m σ ( s σ ∗ ) = 0 , m σ ( s σ ∗ ) ≤ m σ ( 0 ) . Then there exists a constant σ ˉ > 0 \bar{\sigma} > 0 σ ˉ > 0 , depending only on the fixed problem data, such that, for every σ ≥ σ ˉ \sigma\ge\bar{\sigma} σ ≥ σ ˉ ,
( ∥ g ∥ 2 σ ) 1 2 d − 1 ≤ ∥ s σ ∗ ∥ ≤ ( 3 d ∥ g ∥ σ ) 1 2 d − 1 . (39) \left(\frac{\lVert g\rVert}{2\sigma}\right)^{\frac{1}{2d-1}}
\le\lVert s_\sigma^* \rVert
\le\left(\frac{3d\lVert g\rVert}{\sigma}\right)^{\frac{1}{2d-1}}. \tag*{(39)} ( 2 σ ∥ g ∥ ) 2 d − 1 1 ≤ ∥ s σ ∗ ∥ ≤ ( σ 3 d ∥ g ∥ ) 2 d − 1 1 . (39) Consequently,
∥ s σ ∗ ∥ = Θ ( σ − 1 2 d − 1 ) as σ → ∞ . \lVert s_\sigma^* \rVert= \Theta\left(\sigma^{-\frac{1}{2d-1}}\right)
\qquad\text{as } \sigma\to\infty. ∥ s σ ∗ ∥ = Θ ( σ − 2 d − 1 1 ) as σ → ∞.
Proof. Let r σ : = ∥ s σ ∗ ∥ r_\sigma:= \lVert s_\sigma^*\rVert r σ := ∥ s σ ∗ ∥ , a j : = Λ j j ! a_j := \frac{\Lambda_j}{j!} a j := j ! Λ j , b j : = Λ j ( j − 1 ) ! b_j := \frac{\Lambda_j}{(j-1)!} b j := ( j − 1 )! Λ j , where Λ j \Lambda_j Λ j is the tensor operator norm introduced before Lemma 5.1. Since m σ ( s σ ∗ ) ≤ m σ ( 0 ) m_\sigma(s_\sigma^*) \le m_\sigma(0) m σ ( s σ ∗ ) ≤ m σ ( 0 ) , we have
0 ≥ m σ ( s σ ∗ ) − m σ ( 0 ) ≥ − ∥ g ∥ r σ − ∑ j = 2 2 d − 1 a j r σ j + σ 2 d r σ 2 d . 0 \ge m_\sigma(s_\sigma^*)-m_\sigma(0) \ge-\lVert g\rVert r_\sigma-\sum_{j=2}^{2d-1}a_jr_\sigma^j+\frac{\sigma}{2d}r_\sigma^{2d}. 0 ≥ m σ ( s σ ∗ ) − m σ ( 0 ) ≥ − ∥ g ∥ r σ − j = 2 ∑ 2 d − 1 a j r σ j + 2 d σ r σ 2 d .
We first show that r σ → 0 r_\sigma\to0 r σ → 0 . Let C : = ∥ g ∥ + ∑ j = 2 2 d − 1 a j C := \lVert g\rVert+\sum_{j=2}^{2d-1}a_j C := ∥ g ∥ + ∑ j = 2 2 d − 1 a j . If r σ ≥ 1 r_\sigma\ge1 r σ ≥ 1 , then σ 2 d r σ 2 d ≤ C r σ 2 d − 1 \frac{\sigma}{2d}r_\sigma^{2d}\le Cr_\sigma^{2d-1} 2 d σ r σ 2 d ≤ C r σ 2 d − 1 , and hence r σ ≤ 2 d C σ r_\sigma\le\frac{2dC}{\sigma} r σ ≤ σ 2 d C , which contradicts r σ ≥ 1 r_\sigma\ge1 r σ ≥ 1 for all sufficiently large σ \sigma σ . Therefore r σ < 1 r_\sigma<1 r σ < 1 eventually, and σ 2 d r σ 2 d ≤ C r σ \frac{\sigma}{2d}r_\sigma^{2d}\le Cr_\sigma 2 d σ r σ 2 d ≤ C r σ , so r σ 2 d − 1 ≤ 2 d C σ r_\sigma^{2d-1}\le\frac{2dC}{\sigma} r σ 2 d − 1 ≤ σ 2 d C . Thus r σ → 0 r_\sigma\to0 r σ → 0 . Since r σ → 0 r_\sigma\to0 r σ → 0 , for all sufficiently large σ \sigma σ , ∑ j = 2 2 d − 1 a j r σ j ≤ ∥ g ∥ 2 r σ \sum_{j=2}^{2d-1}a_jr_\sigma^j\le\frac{\lVert g\rVert}{2}r_\sigma ∑ j = 2 2 d − 1 a j r σ j ≤ 2 ∥ g ∥ r σ . Using again m σ ( s σ ∗ ) ≤ m σ ( 0 ) m_\sigma(s_\sigma^*)\le m_\sigma(0) m σ ( s σ ∗ ) ≤ m σ ( 0 ) , we obtain
σ 2 d r σ 2 d ≤ 3 ∥ g ∥ 2 r σ . \frac{\sigma}{2d}r_\sigma^{2d}\le\frac{3\lVert g\rVert}{2}r_\sigma. 2 d σ r σ 2 d ≤ 2 3 ∥ g ∥ r σ .
Since ∥ g ∥ ≠ 0 \lVert g\rVert\ne0 ∥ g ∥ = 0 , stationarity implies r σ > 0 r_\sigma>0 r σ > 0 , and hence
r σ 2 d − 1 ≤ 3 d ∥ g ∥ σ . r_\sigma^{2d-1}\le\frac{3d\lVert g\rVert}{\sigma}. r σ 2 d − 1 ≤ σ 3 d ∥ g ∥ .
This proves the upper bound in (39) .
For the lower bound, the stationarity condition gives
g + ∑ j = 2 2 d − 1 1 ( j − 1 ) ! T j [ ( s σ ∗ ) ] j − 1 + σ r σ 2 d − 2 s σ ∗ = 0. g+\sum_{j=2}^{2d-1}\frac{1}{(j-1)!}T_j[(s_\sigma^*)]^{j-1}+\sigma r_\sigma^{2d-2}s_\sigma^*=0. g + j = 2 ∑ 2 d − 1 ( j − 1 )! 1 T j [( s σ ∗ ) ] j − 1 + σ r σ 2 d − 2 s σ ∗ = 0.
Taking norms and using the reverse triangle inequality yields
σ r σ 2 d − 1 ≥ ∥ g ∥ − ∑ j = 2 2 d − 1 b j r σ j − 1 . \sigma r_\sigma^{2d-1}\ge\lVert g\rVert-\sum_{j=2}^{2d-1}b_jr_\sigma^{j-1}. σ r σ 2 d − 1 ≥ ∥ g ∥ − j = 2 ∑ 2 d − 1 b j r σ j − 1 .
Since r σ → 0 r_\sigma\to0 r σ → 0 , for all sufficiently large σ \sigma σ , ∑ j = 2 2 d − 1 b j r σ j − 1 ≤ ∥ g ∥ 2 \sum_{j=2}^{2d-1}b_jr_\sigma^{j-1}\le\frac{\lVert g\rVert}{2} ∑ j = 2 2 d − 1 b j r σ j − 1 ≤ 2 ∥ g ∥ . Therefore, σ r σ 2 d − 1 ≥ ∥ g ∥ 2 \sigma r_\sigma^{2d-1}\ge\frac{\lVert g\rVert}{2} σ r σ 2 d − 1 ≥ 2 ∥ g ∥ , which gives r σ ≥ ( ∥ g ∥ 2 σ ) 1 2 d − 1 r_\sigma\ge\left(\frac{\lVert g\rVert}{2\sigma}\right)^{\frac{1}{2d-1}} r σ ≥ ( 2 σ ∥ g ∥ ) 2 d − 1 1 . Combining the two bounds proves ∥ s σ ∗ ∥ = Θ ( σ − 1 2 d − 1 ) \lVert s_\sigma^*\rVert=\Theta\left(\sigma^{-\frac{1}{2d-1}}\right) ∥ s σ ∗ ∥ = Θ ( σ − 2 d − 1 1 ) .
More Discussions on Moment Sequence
Remark D.1. Let A d : = { α ∈ N n : 1 ≤ ∣ α ∣ ≤ d } A_d:=\{\alpha\in\mathbb{N}^n:1\le|\alpha|\le d\} A d := { α ∈ N n : 1 ≤ ∣ α ∣ ≤ d } , ∣ α ∣ : = α 1 + ⋯ + α n |\alpha|:=\alpha_1+\cdots+\alpha_n ∣ α ∣ := α 1 + ⋯ + α n . Then
v d ( v ) = ( v α ) α ∈ A d , v α : = v 1 α 1 ⋯ v n α n , v_d(v)=\left(v^\alpha\right)_{\alpha\in A_d},\qquad v^\alpha:=v_1^{\alpha_1}\cdots v_n^{\alpha_n}, v d ( v ) = ( v α ) α ∈ A d , v α := v 1 α 1 ⋯ v n α n ,
is the vector of all nonconstant monomials in v v v of degree at most d d d . Then,
q σ ( v ) = ∑ α , β ∈ A d ( Q σ ) α β v α + β , q_\sigma(v)=\sum_{\alpha,\beta\in A_d}(Q_\sigma)_{\alpha\beta}v^{\alpha+\beta}, q σ ( v ) = α , β ∈ A d ∑ ( Q σ ) α β v α + β ,
while ( M d + ( y ~ ) ) α β = y ~ α + β = L y ~ ( v α + β ) (M_d^+(\widetilde y))_{\alpha\beta}=\widetilde y_{\alpha+\beta}=L_{\widetilde y}(v^{\alpha+\beta}) ( M d + ( y ) ) α β = y α + β = L y ( v α + β ) . Hence, L y ~ ( q σ ) = ∑ α , β ( Q σ ) α β y ~ α + β = ⟨ Q σ , M d + ( y ~ ) ⟩ L_{\widetilde y}(q_\sigma)=\sum_{\alpha,\beta}(Q_\sigma)_{\alpha\beta}\widetilde y_{\alpha+\beta}=\langle Q_\sigma,M_d^+(\widetilde y)\rangle L y ( q σ ) = ∑ α , β ( Q σ ) α β y α + β = ⟨ Q σ , M d + ( y )⟩ .
Remark D.2. The unique optimal truncated moment sequence is the moment sequence of the Dirac measure at v = 0 v=0 v = 0 . More precisely,
y ~ 0 = 1 , y ~ α = 0 for every 1 ≤ ∣ α ∣ ≤ 2 d . \widetilde y_0=1,\qquad\widetilde y_\alpha=0\quad\text{for every }1\le|\alpha|\le2d. y 0 = 1 , y α = 0 for every 1 ≤ ∣ α ∣ ≤ 2 d .
Indeed, for the Dirac measure δ 0 \delta_0 δ 0 ,
∫ R n v α d δ 0 ( v ) = { 1 , α = 0 , 0 , ∣ α ∣ ≥ 1. \int_{\mathbb{R}^n}v^\alpha\,\mathrm{d}\delta_0(v)=
\begin{cases}
1, & \alpha=0,\\
0, & |\alpha|\ge1.
\end{cases} ∫ R n v α d δ 0 ( v ) = { 1 , 0 , α = 0 , ∣ α ∣ ≥ 1.
Hence y ~ \widetilde y y coincides with the truncated moment sequence of δ 0 \delta_0 δ 0 . The uniqueness follows from the preceding argument, which shows that any optimal shifted moment matrix must equal M d ( y ~ ) = ( 1 0 0 0 ) M_d(\widetilde y)=\begin{pmatrix}1&0\\0&0\end{pmatrix} M d ( y ) = ( 1 0 0 0 ) . For x = v + s σ ∗ x=v+s_\sigma^* x = v + s σ ∗ , under this translation, the Dirac measure at v = 0 v = 0 v = 0 is mapped to the Dirac measure at x = s σ ∗ x = s_\sigma^* x = s σ ∗ . Therefore, the unique optimal truncated moment sequence in the original coordinates is
y α ∗ = ∫ R n x α d δ s σ ∗ ( x ) = ( s σ ∗ ) α , ∣ α ∣ ≤ 2 d . y_\alpha^* = \int_{\mathbb{R}^n} x^\alpha\, \mathrm{d}\delta_{s_\sigma^*}(x) = (s_\sigma^*)^\alpha,\qquad|\alpha| \le2d. y α ∗ = ∫ R n x α d δ s σ ∗ ( x ) = ( s σ ∗ ) α , ∣ α ∣ ≤ 2 d .
Consequently, for every multi-index α , β ∈ N n \alpha,\beta\in\mathbb{N}^n α , β ∈ N n satisfying ∣ α ∣ , ∣ β ∣ ≤ d |\alpha|,|\beta| \le d ∣ α ∣ , ∣ β ∣ ≤ d , the corresponding entry of the moment matrix is
( M d ( y ∗ ) ) α , β = y α + β ∗ = ( s σ ∗ ) α + β = ( s σ ∗ ) α ( s σ ∗ ) β . \left(M_d(y^*)\right)_{\alpha,\beta} = y_{\alpha+\beta}^* = (s_\sigma^*)^{\alpha+\beta} = (s_\sigma^*)^\alpha(s_\sigma^*)^\beta. ( M d ( y ∗ ) ) α , β = y α + β ∗ = ( s σ ∗ ) α + β = ( s σ ∗ ) α ( s σ ∗ ) β .
Hence
M d ( y ∗ ) = z d ( s σ ∗ ) z d ( s σ ∗ ) T , M_d(y^*) = z_d(s_\sigma^*)z_d(s_\sigma^*)^\mathsf{T}, M d ( y ∗ ) = z d ( s σ ∗ ) z d ( s σ ∗ ) T ,
where z d ( x ) = ( x α ) ∣ α ∣ ≤ d = ( 1 , [ x ] 1 T , … , [ x ] d T ) T z_d(x) = (x^\alpha)_{|\alpha|\le d} = (1,[x]_1^\mathsf{T},\ldots,[x]_d^\mathsf{T})^\mathsf{T} z d ( x ) = ( x α ) ∣ α ∣ ≤ d = ( 1 , [ x ] 1 T , … , [ x ] d T ) T . Since z d ( s σ ∗ ) ≠ 0 z_d(s_\sigma^*) \ne0 z d ( s σ ∗ ) = 0 , we have rank M d ( y ∗ ) = 1 \operatorname{rank} M_d(y^*) = 1 rank M d ( y ∗ ) = 1 . Likewise,
M d − 1 ( y ∗ ) = z ≤ d − 1 ( s σ ∗ ) z ≤ d − 1 ( s σ ∗ ) T , M_{d-1}(y^*) = z_{\le d-1}(s_\sigma^*)z_{\le d-1}(s_\sigma^*)^\mathsf{T}, M d − 1 ( y ∗ ) = z ≤ d − 1 ( s σ ∗ ) z ≤ d − 1 ( s σ ∗ ) T ,
which also have rank M d − 1 ( y ∗ ) = 1 M_{d-1}(y^*) = 1 M d − 1 ( y ∗ ) = 1 . Thus the flat rank condition holds:
rank M d ( y ∗ ) = rank M d − 1 ( y ∗ ) = 1. \operatorname{rank} M_d(y^*) = \operatorname{rank} M_{d-1}(y^*) = 1. rank M d ( y ∗ ) = rank M d − 1 ( y ∗ ) = 1.
Finally, for the standard unit multi-index e i e_i e i , y e i ∗ = ( s σ ∗ ) e i = ( s σ ∗ ) i y_{e_i}^* = (s_\sigma^*)^{e_i} = (s_\sigma^*)_i y e i ∗ = ( s σ ∗ ) e i = ( s σ ∗ ) i , i = 1 , … , n i = 1,\ldots,n i = 1 , … , n . Therefore, the unique global minimizer can be recovered directly from the first-order moments: s σ ∗ = ( y e 1 ∗ , … , y e n ∗ ) T s_\sigma^* = (y_{e_1}^*,\ldots,y_{e_n}^*)^\mathsf{T} s σ ∗ = ( y e 1 ∗ , … , y e n ∗ ) T . Finally, the first-order moments satisfy y e i ∗ = ( s σ ∗ ) i y_{e_i}^* = (s_\sigma^*)_i y e i ∗ = ( s σ ∗ ) i , which gives the claimed exact extraction formula.