In mathematics, a form (i.e. a homogeneous polynomial) h(x) of degree 2m in the real n-dimensional vector x is sum of squares of forms (SOS) if and only if there exist forms g 1 ( x ) , … , g k ( x ) {\displaystyle g_{1}(x),\ldots ,g_{k}(x)} of degree m such that
h ( x ) = ∑ i = 1 k g i ( x ) 2 . {\displaystyle h(x)=\sum _{i=1}^{k}g_{i}(x)^{2}.}
Every form that is SOS is also a positive polynomial, although the converse is not always true in general. In the special cases of n = 2 and 2m = 2, or n = 3 and 2m = 4, Hilbert proved that a form is SOS if and only if it is positive. The same is also true for the analogous problem with positive symmetric forms. Although not every form is SOS, there are efficiently testable sufficient conditions for a form to be SOS. Moreover, every real nonnegative form can be approximated as closely as desired (in the l 1 {\displaystyle l_{1}} -norm of its coefficient vector) by a sequence of forms { f ϵ } {\displaystyle \{f_{\epsilon }\}} that are SOS.
Square matricial representation (SMR) To establish whether a form h(x) is SOS amounts to solving a convex optimization problem. Indeed, any h(x) can be written as
h ( x ) = ( x { m } ) T ( H + L ( α ) ) x { m } {\displaystyle h(x)=(x^{\{m\}})^{T}\left(H+L(\alpha )\right)x^{\{m\}}}
where x { m } {\displaystyle x^{\{m\}}} is a vector containing a basis for the space of forms of degree m in x (such as all monomials of degree m), H is any symmetric matrix satisfying h ( x ) = ( x { m } ) T H x { m } {\displaystyle h(x)=(x^{\left\{m\right\}})^{T}Hx^{\{m\}}} , and L ( α ) {\displaystyle L(\alpha )} is a linear parameterization of the linear subspace
L = { L = L ′ : x { m } ′ L x { m } = 0 } . {\displaystyle {\mathcal {L}}=\left\{L=L':~x^{\{m\}'}Lx^{\{m\}}=0\right\}.}
The dimension of the vector x { m } {\displaystyle x^{\{m\}}} is given by
σ ( n , m ) = ( n + m − 1 m ) , {\displaystyle \sigma (n,m)={\binom {n+m-1}{m}},}
whereas the dimension of the vector α {\displaystyle \alpha } is given by
ω ( n , 2 m ) = 1 2 σ ( n , m ) ( 1 + σ ( n , m ) ) − σ ( n , 2 m ) . {\displaystyle \omega (n,2m)={\frac {1}{2}}\sigma (n,m)\left(1+\sigma (n,m)\right)-\sigma (n,2m).}
The polynomial h(x) is SOS if and only if there exists a vector α {\displaystyle \alpha } such that
… excerpt ends here. Continue reading the full article.
