Polynomial SOS

In mathematics, a form (i.e. a homogeneous polynomial) "h"("x") of degree 2"m" in the real "n"-dimensional vector "x" is sum of squares of forms (SOS) if and only if there exist forms formula_1 of degree "m" such that
Every form that is SOS is also a positive polynomial, and although the converse is not always true, Hilbert proved that for "n" = 2, "2m" = 2 or "n" = 3 and 2"m" = 4 a form is SOS if and only if it is positive. The same is also valid for the analog problem on positive "symmetric" forms.
Although not every form can be represented as SOS, explicit sufficient conditions for a form to be SOS have been found. Moreover, every real nonnegative form can be approximated as closely as desired (in the formula_3-norm of its coefficient vector) by a sequence of forms formula_4 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
where formula_6 is a vector containing a base for the forms of degree "m" in "x" (such as all monomials of degree "m" in "x"), the prime ′ denotes the transpose, "H" is any symmetric matrix satisfying
and formula_8 is a linear parameterization of the linear space
The dimension of the vector formula_6 is given by
whereas the dimension of the vector formula_12 is given by
Then, "h"("x") is SOS if and only if there exists a vector formula_12 such that
meaning that the matrix formula_16 is positive-semidefinite. This is a linear matrix inequality (LMI) feasibility test, which is a convex optimization problem. The expression formula_17 was introduced in with the name square matricial representation (SMR) in order to establish whether a form is SOS via an LMI. This representation is also known as Gram matrix.
Generalizations.
Matrix SOS.
A matrix form "F"("x") (i.e., a matrix whose entries are forms) of dimension "r" and degree "2m" in the real "n"-dimensional vector "x" is SOS if and only if there exist matrix forms formula_26 of degree "m" such that
Matrix SMR.
To establish whether a matrix form "F"("x") is SOS amounts to solving a convex optimization problem. Indeed, similarly to the scalar case any "F"("x") can be written according to the SMR as
where formula_29 is the Kronecker product of matrices, "H" is any symmetric matrix satisfying
and formula_8 is a linear parameterization of the linear space
The dimension of the vector formula_12 is given by
Then, "F"("x") is SOS if and only if there exists a vector formula_12 such that the following LMI holds:
The expression formula_37 was introduced in 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" = ("X"1...,"X""n") and equipped with the involution T, such that T fixes "R" and "X"1...,"X""n" and reverse words formed by "X"1...,"X""n".
By analogy with the commutative case, the noncommutative symmetric polynomials "f" are the noncommutative polynomials of the form "f" = "f""T". When any real matrix of any dimension "r x r" is evaluated at a symmetric noncommutative polynomial "f" results in a positive semi-definite matrix, "f" is said to be matrix-positive.
A noncommutative polynomial is SOS if there exists noncommutative polynomials formula_38 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.