Nemirovski - Revision history

Ranjelin: /* Semidefinite representable trigonometric polynomial */

Ranjelin — Tue, 08 Nov 2016 00:38:17 GMT

Semidefinite representable trigonometric polynomial

←Older revision		Revision as of 00:38, 8 November 2016
Line 27:		Line 27:


-	Now, the vector <math>p=[p_0;~~\cdots~~;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,	+	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

Ranjelin: /* Semidefinite representable trigonometric polynomial */

Ranjelin — Mon, 05 Dec 2011 06:23:23 GMT

Semidefinite representable trigonometric polynomial

←Older revision		Revision as of 06:23, 5 December 2011
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;\cdots;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

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.

Ranjelin at 20:38, 24 November 2011

Ranjelin — Thu, 24 Nov 2011 20:38:26 GMT

←Older revision		Revision as of 20:38, 24 November 2011
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>

Kwokwah: /* Example */

Kwokwah — Mon, 25 Oct 2010 11:27:42 GMT

Example

←Older revision		Revision as of 11:27, 25 October 2010
Line 54:		Line 54:
	where <math>\zeta\!\triangleq_{\!}\tan(\omega/2)</math>.		where <math>\zeta\!\triangleq_{\!}\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>.

Kwokwah: /* Example */

Kwokwah — Mon, 25 Oct 2010 11:25:51 GMT

Example

←Older revision		Revision as of 11:25, 25 October 2010
Line 49:		Line 49:
	This can be written equivalently in terms of <math>\cos(\omega)\,</math> and <math>\sin(\omega)\,</math>:		This can be written equivalently in terms of <math>\cos(\omega)\,</math> and <math>\sin(\omega)\,</math>:
	For <math>\,N\!=_{\!}3</math>		For <math>\,N\!=_{\!}3</math>
-	<center><math>R(\omega)=r(0) + 2r(1)\cos(\omega) + 2r(2)\cos(\omega)^2 - 2r(2)\sin(\omega)^2\,</math></center>	+	<center><math>R(\omega)=r(0)\,+\,2r(1)\cos(\omega)\,+\,2r(2)\cos(\omega)^2\,-\,2r(2)\sin(\omega)^2\,</math></center>
	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>

Kwokwah: /* Example */

Kwokwah — Mon, 25 Oct 2010 11:22:24 GMT

Example

←Older revision		Revision as of 11:22, 25 October 2010
Line 47:		Line 47:
	[http://www.convexoptimization.com/wikimization/index.php/Filter_design_by_convex_iteration#Minimum_peak_time-domain_response_by_Optimization Minimization of peak time-domain response] in filter design works with the autocorrelation function <math>r\,</math> whose Fourier transform is		[http://www.convexoptimization.com/wikimization/index.php/Filter_design_by_convex_iteration#Minimum_peak_time-domain_response_by_Optimization Minimization of peak time-domain response] in filter design works with the autocorrelation function <math>r\,</math> whose Fourier transform is
	<center><math>R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)</math></center>		<center><math>R(\omega) = r(0)+\!\sum\limits_{n=1}^{N-1}2r(n)\cos(\omega n)</math></center>
-	~~Define~~	+	This can be written equivalently in terms of <math>\cos(\omega)\,</math> and <math>\sin(\omega)\,</math>:
-	~~<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>.	+
	For <math>\,N\!=_{\!}3</math>		For <math>\,N\!=_{\!}3</math>
		+	<center><math>R(\omega)=r(0) + 2r(1)\cos(\omega) + 2r(2)\cos(\omega)^2 - 2r(2)\sin(\omega)^2\,</math></center>
		+	Assign
		+	<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>.
	<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>

Cslaw: /* Example */

Cslaw — Mon, 25 Oct 2010 10:37:11 GMT

Example

←Older revision		Revision as of 10:37, 25 October 2010
Line 49:		Line 49:
	Define		Define
	<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\!\triangleq\!\tan(\omega/2)</math>.
-	For <math>\,N\!=_{\!}2</math>	+	For <math>\,N\!=_{\!}3</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>

Kwokwah: /* Example */

Kwokwah — Mon, 25 Oct 2010 06:19:43 GMT

Example

←Older revision		Revision as of 06:19, 25 October 2010
Line 55:		Line 55:
	<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>.
-	A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness.	+	A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness;
		+	in other words, each and every coefficient of the polynomial in <math>\zeta\,</math> must be nonnegative.
		+
	Transformation of the trigonometric polynomial in <math>\cos(\omega n)\,</math> into a polynomial in <math>\zeta\,</math>can produce coefficients whose dynamic range is quite large. Finite precision numerical computation becomes problematic for large <math>N\,</math>.		Transformation of the trigonometric polynomial in <math>\cos(\omega n)\,</math> into a polynomial in <math>\zeta\,</math>can produce coefficients whose dynamic range is quite large. Finite precision numerical computation becomes problematic for large <math>N\,</math>.

Kwokwah at 06:11, 25 October 2010

Kwokwah — Mon, 25 Oct 2010 06:11:29 GMT

←Older revision		Revision as of 06:11, 25 October 2010
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 ~~esists~~ 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.

Kwokwah: /* Example */

Kwokwah — Mon, 25 Oct 2010 01:36:16 GMT

Example

←Older revision		Revision as of 01:36, 25 October 2010
Line 56:		Line 56:
	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>.
	A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness.		A nonnegative main diagonal is therefore necessary and sufficient for positive semidefiniteness.
-	Transformation of <math>\cos(\omega n)\,</math> into a polynomial in <math>\zeta\,</math>can produce coefficients whose dynamic range is quite large. Finite precision numerical computation becomes problematic for large <math>N\,</math>.	+	Transformation of the trigonometric polynomial in <math>\cos(\omega n)\,</math> into a polynomial in <math>\zeta\,</math>can produce coefficients whose dynamic range is quite large. Finite precision numerical computation becomes problematic for large <math>N\,</math>.