Polynomial SOS


In mathematics, a form h of degree 2m in the real n-dimensional vector x is sum of squares of forms if and only if there exist forms of degree m such that
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 by a sequence of forms that are SOS.

Square matricial representation (SMR)

To establish whether a form is SOS amounts to solving a convex optimization problem. Indeed, any can be written as
where is a vector containing a basis for the space of forms of degree m in x, H is any symmetric matrix satisfying,
and is a linear parameterization of the linear subspace
The dimension of the vector is given by
whereas the dimension of the vector is given by
The polynomial is SOS if and only if there exists a vector such that
is a positive-semidefinite matrix. This is a linear matrix inequality, and the existence of is a convex feasibility problem.
The expression was introduced with the name square matricial representation in order to establish whether a form is SOS via an LMI. The matrix is also known as a Gram matrix.

Examples

  • Consider and the form of degree 4 in two variables. We have Since there exists α such that, namely, it follows that h is SOS.
  • Consider and the form of degree 4 in three variables. We have Since for, it follows that is SOS.

Generalizations and analogs

Matrix SOS

A matrix form F of dimension r and degree 2m in the real n-dimensional vector x is SOS if and only if there exist matrix forms of degree m such that

Matrix SMR

To establish whether a matrix form F is SOS amounts to solving a convex optimization problem. Indeed, similarly to the scalar case any F can be written according to the SMR as
where is the Kronecker product of matrices, H is any symmetric matrix satisfying
and is a linear parameterization of the linear space
The dimension of the vector is given by
Then, is SOS if and only if there exists a vector such that the following LMI holds:
The expression was introduced in order to establish whether a matrix form is SOS via an LMI.

Noncommutative polynomial SOS

Consider the free algebra R⟨''X⟩ generated by the n'' noncommuting letters X = and equipped with the involution, such that fixes R and X1,..., Xn and reverses words formed by X1,..., Xn.
We consider Hermitian noncommutative polynomials f, which are the noncommutative polynomials of the form. When evaluating a Hermitian noncommutative polynomial f on any n-tuple of real matrices of any size r × r produces in a positive semi-definite matrix, f is said to be matrix-positive.
A noncommutative polynomial is SOS if there exists noncommutative polynomials such that
Surprisingly, in the noncommutative scenario a noncommutative polynomial is SOS if and only if it is matrix-positive. Moreover, there exist algorithms available to decompose matrix-positive polynomials in sum of squares of noncommutative polynomials.

Polynomial HSOS

A complex polynomial in variables and their conjugates is Hermitian if it takes on only real values, or equivalently if each term has an equal number of conjugated and un-conjugated variables. It is a hermitian sum-of-squares if there are complex polynomials, in only the un-conjugated variables, such that A Hermitian square matricial representation of is a matrix such that, where is the Hermitian transpose of the vector. As first observed by Putinar, there is a choice of the matrix having certain symmetry properties, which is in fact unique and can be written explicitly. Thus testing if a Hermitian polynomial is HSOS of degree can be done by testing if a single, fixed matrix is positive-semidefinite.