Polynomial SOS

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),\ldots,g_k(x) of degree m such that h(x) = \sum_{i=1}^k…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 6 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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),\ldots,g_k(x) of degree m such that 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 -norm of its coefficient vector) by a sequence of forms \{f_\epsilon\} that are SOS. h(x) = (x^{\{m\}})^{T}\left(H+L(\alpha)\right)x^{\{m\}} where 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^{\left\{m\right\}})^{T}Hx^{\{m\}} , and L(\alpha) is a linear parameterization of the linear subspace \mathcal{L} = \left\{L=L':~x^{\{m\}'} L x^{\{m\}}=0\right\}. The dimension of the vector x^{\{m\}} is given by \sigma(n,m) = \binom{n+m-1}{m}, whereas the dimension of the vector \alpha is given by \omega(n,2m) = \frac{1}{2}\sigma(n,m)\left(1+\sigma(n,m)\right)-\sigma(n,2m). The polynomial is SOS if and only if there exists a vector \alpha such that H + L(\alpha) is a positive-semidefinite matrix.

This is a linear matrix inequality (LMI), and the existence of \alpha is a convex feasibility problem. The expression h(x)=x^{\{m\}'}\left(H+L(\alpha)\right)x^{\{m\}} was introduced with the name square matricial representation (SMR) in order to establish whether a form is SOS via an LMI. The matrix H + L(\alpha) is also known as a Gram matrix.

Consider m = 2 and the form h(x)=x_1^4-x_1^2x_2^2+x_2^4 of degree 4 in two variables. We have x^{\{m\}} = \begin{pmatrix} x_1^2\\x_1x_2\\x_2^2\end{pmatrix}\!, ~H+L(\alpha) = \begin{pmatrix} 1&0&-\alpha_1\\0&-1+2\alpha_1&0\\-\alpha_1&0&1 \end{pmatrix}\!. Since there exists α such that H+L(\alpha)\ge 0 , namely \alpha=1 , it follows that h(x) is SOS.

Consider m = 2 and the form h(x)=2x_1^4-5x_1^3x_2/2+x_1^2x_2x_3-2x_1x_3^3+5x_2^4+x_3^4 of degree 4 in three variables. We have x^{\{m\}}=\begin{pmatrix}x_1^2\\x_1x_2\\x_1x_3\\x_2^2\\x_2x_3\\x_3^2\end{pmatrix}, ~H+L(\alpha) = \begin{pmatrix} 2&-5/4&0&-\alpha_1&-\alpha_2&-\alpha_3\\ -5/4&2\alpha_1&1/2+\alpha_2&0&-\alpha_4&-\alpha_5\\ 0&1/2+\alpha_2&2\alpha_3&\alpha_4&\alpha_5&-1\\ -\alpha_1&0&\alpha_4&5&0&-\alpha_6\\ -\alpha_2&-\alpha_4&\alpha_5&0&2\alpha_6&0\\ -\alpha_3&-\alpha_5&-1&-\alpha_6&0&1 \end{pmatrix}.

Since H+L(\alpha)\ge 0 for \alpha=(1.18,-0.43,0.73,1.13,-0.37,0.57) , it follows that is SOS. F(x)=\sum_{i=1}^k G_i(x)^{T}G_i(x) . F(x) = \left(x^{\{m\}}\otimes I_r\right)^{T}\left(H+L(\alpha)\right)\left(x^{\{m\}}\otimes I_r\right) where \otimes is the Kronecker product of matrices, H is any symmetric matrix satisfying F(x) = \left(x^{\{m\}}\otimes I_r\right)^{T}H\left(x^{\{m\}}\otimes I_r\right) and L(\alpha) is a linear parameterization of the linear space \mathcal{L}=\left\{L=L^{T}:~\left(x^{\{m\}}\otimes I_r\right)^{T}L\left(x^{\{m\}}\otimes I_r\right)=0\right\}.

The dimension of the vector \alpha is given by \omega(n,2m,r)=\frac{1}{2}r\left(\sigma(n,m)\left(r\sigma(n,m)+1\right)-(r+1)\sigma(n,2m)\right). Then, is SOS if and only if there exists a vector \alpha such that the following LMI holds: H+L(\alpha) \ge 0.

The expression F(x) = \left(x^{\{m\}}\otimes I_r\right)^{T}\left(H+L(\alpha)\right)\left(x^{\{m\}}\otimes I_r\right) was introduced in order to establish whether a matrix form is SOS via an LMI. Consider the free algebra R⟨X⟩ generated by the n noncommuting letters X = (X 1 , ..., X n ) and equipped with the involution , such that fixes R and X 1 , ..., X n and reverses words formed by X 1 , ..., X n . 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 h_1,\ldots,h_k such that f(X) = \sum_{i=1}^{k} h_i(X)^T h_i(X). 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. A complex polynomial p(z_1, \dots, z_n) in variables z_1, \dots, z_n and their conjugates z_1^*, \dots, z_n^* 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 (HSOS) if there are complex polynomials g_1, \dots, g_k , in only the un-conjugated variables z_1, \dots, z_n , such that p(z) = \sum _{i = 1} ^{k} g_i^*(z)g_i(z). A Hermitian square matricial representation of p is a matrix M such that p(z) = (z^{\{m\}})^{*}Mz^{\{m\}} , where (z^{\{m\}})^{*} is the Hermitian transpose of the vector z^{\{m\}} . As first observed by Putinar, there is a choice of the matrix M having certain symmetry properties, which is in fact unique and can be written explicitly.

Thus testing if a Hermitian polynomial is HSOS of degree m can be done by testing if a single, fixed matrix is positive-semidefinite.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374676699 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001374676699 · captured 2026-09-13 · not yet sealed in the ledger · verify the chain · version history

Cite this page as: encyclopegia.org, “Polynomial SOS”, snapshot enwiki-001374676699. https://encyclopegia.org/a/polynomial-sos

Sources cited in this revision

6 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.