Nemirovski

From Wikimization

(Difference between revisions)
Jump to: navigation, search
(Example)
Current revision (17:38, 7 November 2016) (edit) (undo)
(Semidefinite representable trigonometric polynomial)
 
(3 intermediate revisions not shown.)
Line 27: Line 27:
-
Now, the vector <math>p=[p_0;\cdots;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq\!2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D\!+\!1</math> such that,
+
Now, the vector <math>p=[p_0; . . . ;p_{2D}]</math> of coefficients of a polynomial of degree <math>\leq2D</math> come from nonnegative polynomial if and only if there exists a positive semidefinite matrix <math>\,Y</math> of size <math>\,D\!+\!1</math> such that,
identically in <math>t\,</math>, one has
identically in <math>t\,</math>, one has
-
<center><math>p_0+p_1t+\cdots+p_{2D}t^{2D}=\,[1,t,t^2,\cdots,t^D]Y[1;t;t^2;\cdots;t^D]</math></center>
+
<center><math>p_0+p_1t+...+p_{2D}t^{2D}=\,[1,t,t^2,...,t^D]Y[1;t;t^2;...;t^D]</math></center>
(this is an immediate corollary of the fact that a polynomial which is nonnegative on the entire axis is sum of squares of other polynomials). Thus, <math>\,p</math> comes from a nonnegative polynomial if and only if
(this is an immediate corollary of the fact that a polynomial which is nonnegative on the entire axis is sum of squares of other polynomials). Thus, <math>\,p</math> comes from a nonnegative polynomial if and only if
Line 39: Line 39:
-
The bottom line is that <math>\,q</math> is a vector of coefficients, nonnegative on a given segment, of a trigonometric polynomial if and only if there exists a positive semidefinitite matrix <math>\,Y</math> such that <math>\,Bq=A(Y)</math> for certain known matrix <math>\,B</math> and linear map <math>Y\!\mapsto\!A(Y)</math>. In other words, the system of constraints <math>Bq\!=\!A(Y),~Y\!\succeq0</math> expresses equivalently the fact that the trigonometric polynomial with coefficients <math>\,q</math> is nonnegative on a given segment.
+
The bottom line is that <math>\,q</math> is a vector of coefficients, nonnegative on a given segment, of a trigonometric polynomial if and only if there exists a positive semidefinitite matrix <math>\,Y</math> such that <math>\,Bq=A(Y)</math> for certain known matrix <math>\,B</math> and linear map <math>Y\!\mapsto\!A(Y)</math>. In other words, the system of constraints <math>Bq\!=\!A(Y),\,\,Y\!\succeq0</math> expresses equivalently the fact that the trigonometric polynomial with coefficients <math>\,q</math> is nonnegative on a given segment.
Line 52: Line 52:
Assign
Assign
<center><math>\cos(\omega)=\frac{1-\zeta^2}{1+\zeta^2}~,\quad \sin(\omega)=\frac{2\zeta}{1+\zeta^2}</math></center>
<center><math>\cos(\omega)=\frac{1-\zeta^2}{1+\zeta^2}~,\quad \sin(\omega)=\frac{2\zeta}{1+\zeta^2}</math></center>
-
where <math>\zeta\!\triangleq_{\!}\tan(\omega/2)</math>.
+
where <math>\zeta\!=_{\!}\tan(\omega/2)</math>.
<center><math>\,R(\omega)=\frac{r(0)+2r(1)+2r(2)~+~(2r(0)-12r(2))\zeta^2~+~(r(0)-2r(1)+2r(2))\zeta^4}{(1+\zeta^2)^2}</math></center>
<center><math>\,R(\omega)=\frac{r(0)+2r(1)+2r(2)~+~(2r(0)-12r(2))\zeta^2~+~(r(0)-2r(1)+2r(2))\zeta^4}{(1+\zeta^2)^2}</math></center>
-
Because the denominator is positive for any <math>N\,</math>, a constraint <math>R(\omega)\!\geq_{\!}0~\,\forall\,\omega\!\in\![-\pi,\pi]</math>, for example, may concern itself only with the numerator which can be factored and stated as an equivalent semidefinite constraint: <math>\forall\,\zeta\!\in_{\!}[-\infty,\infty]</math>
+
Because the denominator is positive for any <math>N\,</math>, a constraint <math>R(\omega)\!\geq_{\!}0~\,\forall\,\omega\!\in\![-\pi,\pi]</math>, for example, may concern itself only with the numerator which can be factored and stated as an equivalent semidefinite constraint: <math>\forall\,\zeta\!\in_{\!}(-\infty,\infty)</math>
<center><math>\mathbf{[}\,1~~\zeta~~\zeta^2\,\mathbf{]}\left[\begin{array}{ccc}r(0)+2r(1)+2r(2)&&\mathbf{0}\\&2r(0)-12r(2)\\\mathbf{0}&&r(0)-2r(1)+2r(2)\end{array}\right]\left[\begin{array}{c}1\\\zeta\\\zeta^2\end{array}\right]\succeq\,0</math></center>
<center><math>\mathbf{[}\,1~~\zeta~~\zeta^2\,\mathbf{]}\left[\begin{array}{ccc}r(0)+2r(1)+2r(2)&&\mathbf{0}\\&2r(0)-12r(2)\\\mathbf{0}&&r(0)-2r(1)+2r(2)\end{array}\right]\left[\begin{array}{c}1\\\zeta\\\zeta^2\end{array}\right]\succeq\,0</math></center>
This matrix is diagonal because there are no odd powers of <math>\zeta\,</math>.
This matrix is diagonal because there are no odd powers of <math>\zeta\,</math>.

Current revision

Semidefinite representable trigonometric polynomial

Hello Arkadi

Regarding page 5 from: Nemirovski lecture

I am trying to understand how the trigonometric polynomial is semidefinite representable simultaneously in both variables LaTeX: \,\phi and LaTeX: \,x.

Are you sampling the interval from LaTeX: \,0 to LaTeX: \,\pi/2?

Jon Dattorro


The answer is no, there is no necessity to sample LaTeX: \,\Delta.


The construction is like this. The nonnegativity of a trigonometric polynomial on a segment is equivalent to the nonnegativity of an algebraic polynomial on another segment since LaTeX: \,\sin(k\phi) and LaTeX: \,\cos(k\phi) are rational functions of LaTeX: \tan(\phi/2)\,; you take this LaTeX: \,\tan as your new variable and get rid of denominators (they are powers of LaTeX: 1+\tan^2(\phi/2)\, which does not affect positivity of the polynomial).


Now, nonnegativity of an algebraic polynomial on a segment reduces to nonnegatiivity of another algebraic polynomial on the entire axis. Indeed, w.l.o.g. we can assume that the segment in question is LaTeX: \,[-1,1], and nonnegativity of LaTeX: \,p(t) on this segment is equivalent to the nonnegativity of LaTeX: \,p(2t/(1+t^2)) on the entire axis, and you again can get rid of denominators.


The bottom line is that nonnegativity of trigonometric polynomial of degree LaTeX: D\, on a given segment is equivalent to nonnegativity of another polynomial, of degree not exceeding a known bound LaTeX: \,2D, on the entire axis. The crucial fact is that the coefficients of the resulting polynomial, as follows from the construction, are affine functions of the coefficients of the initial polynomial.


Now, the vector LaTeX: p=[p_0; . . . ;p_{2D}] of coefficients of a polynomial of degree LaTeX: \leq2D come from nonnegative polynomial if and only if there exists a positive semidefinite matrix LaTeX: \,Y of size LaTeX: \,D\!+\!1 such that, identically in LaTeX: t\,, one has

LaTeX: p_0+p_1t+...+p_{2D}t^{2D}=\,[1,t,t^2,...,t^D]Y[1;t;t^2;...;t^D]

(this is an immediate corollary of the fact that a polynomial which is nonnegative on the entire axis is sum of squares of other polynomials). Thus, LaTeX: \,p comes from a nonnegative polynomial if and only if

LaTeX: p_{\ell\,}=\!\sum_{i+j=\ell}Y_{ij}   for all LaTeX: \ell

where LaTeX: [Y_{ij}]_{0\leq i,j\leq D} is positive semidefinite.


The bottom line is that LaTeX: \,q is a vector of coefficients, nonnegative on a given segment, of a trigonometric polynomial if and only if there exists a positive semidefinitite matrix LaTeX: \,Y such that LaTeX: \,Bq=A(Y) for certain known matrix LaTeX: \,B and linear map LaTeX: Y\!\mapsto\!A(Y). In other words, the system of constraints LaTeX: Bq\!=\!A(Y),\,\,Y\!\succeq0 expresses equivalently the fact that the trigonometric polynomial with coefficients LaTeX: \,q is nonnegative on a given segment.


Note that this construction is due to Yurii Nesterov.

Example

Minimization of peak time-domain response in filter design works with the autocorrelation function LaTeX: r\, whose Fourier transform is

LaTeX: R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)

This can be written equivalently in terms of LaTeX: \cos(\omega)\, and LaTeX: \sin(\omega)\,: For LaTeX: \,N\!=_{\!}3

LaTeX: R(\omega)=r(0)\,+\,2r(1)\cos(\omega)\,+\,2r(2)\cos(\omega)^2\,-\,2r(2)\sin(\omega)^2\,

Assign

LaTeX: \cos(\omega)=\frac{1-\zeta^2}{1+\zeta^2}~,\quad \sin(\omega)=\frac{2\zeta}{1+\zeta^2}

where LaTeX: \zeta\!=_{\!}\tan(\omega/2).

LaTeX: \,R(\omega)=\frac{r(0)+2r(1)+2r(2)~+~(2r(0)-12r(2))\zeta^2~+~(r(0)-2r(1)+2r(2))\zeta^4}{(1+\zeta^2)^2}

Because the denominator is positive for any LaTeX: N\,, a constraint LaTeX: R(\omega)\!\geq_{\!}0~\,\forall\,\omega\!\in\![-\pi,\pi], for example, may concern itself only with the numerator which can be factored and stated as an equivalent semidefinite constraint: LaTeX: \forall\,\zeta\!\in_{\!}(-\infty,\infty)

LaTeX: \mathbf{[}\,1~~\zeta~~\zeta^2\,\mathbf{]}\left[\begin{array}{ccc}r(0)+2r(1)+2r(2)&&\mathbf{0}\\&2r(0)-12r(2)\\\mathbf{0}&&r(0)-2r(1)+2r(2)\end{array}\right]\left[\begin{array}{c}1\\\zeta\\\zeta^2\end{array}\right]\succeq\,0

This matrix is diagonal because there are no odd powers of LaTeX: \zeta\,. A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness; in other words, each and every coefficient of the polynomial in LaTeX: \zeta\, must be nonnegative.

Transformation of the trigonometric polynomial in LaTeX: \cos(\omega n)\, into a polynomial in LaTeX: \zeta\,can produce coefficients whose dynamic range is quite large. Finite precision numerical computation becomes problematic for large LaTeX: N\,.

Personal tools