Positive trigonometric polynomials and signal processing applications (Q5899432): Difference between revisions

Several results in systems and signal theory can be derived in a unified fashion from polynomial positivity conditions, and handled numerically with semidefinite programming, a broad generalization of linear programming to the cone of positive semidefinite matrices. Results in the area bridge gaps between algebra, geometry, optimization and engineering. Following key contributions by N. Z. Shor (1987), and then later on (2000) by J. B. Lasserre, Y. Nesterov or P. A. Parrilo, the first book on the topic was published in 2005 as a collection of contributions by experts in the field: [\textit{D. Henrion} (ed.) and \textit{A. Garulli} (ed.), Positive polynomials in control. Berlin: Springer.(2005; Zbl 1059.93002)]. This volume focused mainly on control applications of polynomial positivity conditions. The book under review is a new contribution on the topic, with a focus on signal processing applications. As far as this reviewer knows, this is the first self-contained manuscript on this emerging research area, and hence it is a welcome and timely contribution to the technical literature. The book is written by a researcher who has been active in the area since the beginning of the 2000s. The book is technical, aimed mostly at researchers or engineers, even though graduate students with interest in convex optimization and signal processing may find interesting the many numerical examples scattered throughout the text. The book is split into two main parts: chapters 1--4 on theory, chapters 5--8 on applications. The introductory chapters 1 and 2 deal with univariate trigonometric polynomials, that is, polynomials with a complex indeterminate lying on the unit circle. The main observation is that the convex cone of positive univariate trigonometric polynomials is semidefinite representable: it can be formulated as the projection of a linear matrix inequality (LMI). This core result is revisited via standard results on spectral factorization and algebraic Riccati equations, familiar to many researchers in signal processing. Chapter 3 covers multivariate trigonometric polynomials, that is, polynomials with several complex indeterminates lying on the unit circle. The geometry of the cone of multivariate positive polynomials is much more complicated than in the univariate case. Using a similar Gram (quadratic form) representation as in the univariate case, a semidefinite characterization is readily available for the cone \(S_d\) of multivariate polynomials that are sums of squares (SOS) of multivariate polynomials of degree at most \(d\). However, in general, this cone is a strict subset of the cone \(P_d\) of nonnegative polynomials of degree at most \(d\). In other words, there are polynomials in \(P_d\) which are not in \(S_d\). Interestingly, the set \(P^+_d\) of strictly positive polynomials of degree at most \(d\) is included in \(S_f\) for \(f \geq d\) sufficiently large. Moreover, no example is known of a polynomial in \(P_d\) which is not in \(S_f\) for \(f \geq d\) sufficiently large, see the discussion at the bottom of page 70. Therefore, in practice, enforcing a positivity or nonnegativity constraint on a multivariate trigonometric polynomial amounts to enforcing a sufficienty large LMI constraint. In other words, optimization over posivite polynomials boils down to semidefinite programming, for which many primal-dual interior-point solvers have been developed since the mid 1990s. The main limitation is however the performance of currently available solvers, which are prototype software still very far, in terms of stability and computational burden, from commercial professional linear programming solvers. On the positive side, all the numerical examples described later on in the book corroborate the observation that the gap between \(P_d\) and \(S_f\) vanishes very quickly when \(f-d>0\) increases, and hence that it is not necessary to solve very large LMI problems to get results of engineering relevance. Chapter 4 extends the results of chapter 3 to polynomials positive on semialgebraic sets. Standard results on real polynomials positive on compact sets are transposed to trigonometric polynomials. In particular, trigonometric versions of Putinar's theorem (Theorem 4.11) and Stengle's Positivstellensatz (Theorem 4.36) are proposed, characterizing, in terms of polynomial SOS, the nonexistence of a solution to a system of polynomial inequalities and equations. The second part of the book, chapters 5-8, focuses on signal processing applications of trigonometric positive polynomials. The LMI characterization of univariate positivity is used in chapter 5 for finite impulse response (FIR) filter design and in chapter 6 for filter bank design. The design problem, non-convex in the filter parameters, becomes convex LMI in the squared magnitude of the filter. The filter is then recovered by spectral factorization. Chapters 5 and 8 use semidefinite relaxations for bivariate polynomial positivity in the context of 2D FIR and infinite impulse response (IIR) filter design. Filters with 2D passbands and stopbands defined by various curves (circle, ellipse, diamond) can be designed at a low computational cost. Chapter 7 mostly deals with multidimensional stability tests via positive polynomials and convex inner approximations of the non-convex stability region in the polynomial coefficient space. Throughout these application chapters, the techniques and algorithms are generously illustrated by many convincing numerical examples, showing the author's expertise in solving challenging filter design problems. Most welcome are Matlab scripts listed and commented in the book, also available for download from the author's webpage. These scripts illustrate the main computational ingredients behind the methods described in the book. In particular, the author uses SeDuMi as a semidefinite programming solver. SeDuMi (for self-dual minimization) is an implementation of a primal-dual interior-point method originally developed in the end 1990s by J. F. Sturm in close collaboration with the signal processing group of MacMaster University, Canada. This may explain the very good performance of SeDuMi on semidefinite problems arising from signal processing, and the author's preference for SeDuMi over the dozen other semidefinite solvers currently available. As far as computational tools are concerned, the author mentions SOSTOOLS (by Papachristodoulou, Parrilo and Prajna, 2002) as a Matlab package for finding SOS decomposition of real multivariate polynomials. Alternative uncited packages are GloptiPoly (by Henrion and Lasserre, 2002), tailored at global polynomial optimization and generalized problems of moments, and YALMIP (by Johan Löfberg, 2000) which is a general purpose optimization parser with dedicated modules for SOS and moments problems. Many features of GloptiPoly and YALMIP, in particular detection of global optimality, extraction of global optimizers, and positive semidefinite polynomial matrices, are not available in SOSTOOLS. All these packages are user-friendly, well documented and publicly available. On the negative side, even though the book deals with trigonometric positive polynomials, the author very often refers to their real counterparts, much more studied in the technical literature. Several times in the book the author moves from the trigonometric case to the real case and vice-versa (e.g. in chapter 4). Sometimes this introduces some notational difficulty that may confuse the reader. In this reviewer's opinion it may have been more appropriate to gather results on real polynomials into a dedicated section or a chapter, for reference. Another disappointing feature of the book, in this reviewer's opinion, is the total lack of connection with the problem of trigonometric moments, a central component of complex functional analysis. This omission is deliberate, as mentioned by the author in the last paragraph of the preface. However, the nice interplay between sum-of-squares and moments, and the connection with semidefinite programming duality, unveiled to a large extent in [\textit{J. B. Lasserre}, SIAM J. Optim. 11, No. 3, 796--817 (2001; Zbl 1010.90061)], and comprehensively surveyed recently in [M. Laurent. Sums of squares, moment matrices and optimization over polynomials. Preprint CWI Amsterdam, NL, October 2007; cf. Zbl 1163.13021], is much more than of pure mathematical interest. For example, at many places in the manuscript, the author conjectures global optimality without being able to ensure it (see e.g. example 3.18). However, rank patterns in partitions of moment matrices allow to certificate global optimality and the absence of a gap between posivitity and SOS. Also, the meaning of the term relaxation (see the discussion in the footnote on page 77) is much clearer when considering the moment formulation, which is the genuine primal formulation in the context of polynomial minimization. The SOS formulation, about existence of polynomial multipliers, is actually a dual problem. An exhaustive coverage of this duality between SOS and moments, and the use of measure theory in the context of trigonometric polynomial optimization, would however require a significant extension of the book. The author's choice goes to a more succinct, and hence necessarily incomplete, treatment of trigonometric polynomial posivitity. To summarize, Dumitrescu's book is a timely and significant contribution to the technical literature on the use of positive polynomials in convex optimization and engineering, an emerging research area at the border between algebraic geometry, functional analysis and mathematical programming. As far as this reviewer knows, this is the first self-contained manuscript dealing with the topic, and it gathers mostly recent results available in scattered form as conference papers, journal papers and technical reports. This reviewer particularly liked the bibliographical and historical notes ending each chapter, which provide additional non-technical insight. The systematic use of illustrative numerical examples, accompanied by Matlab scripts, allows the inexperienced reader to grasp the essential ideas without having to understand all the mathematical subtelties. In particular, signal processing engineers should benefit a lot from reading the book, which provides them with a powerful and useful methodology to design sophisticated filters with off-the-shelf software. Finally, throughout the book, the author suggests several promising research directions, including for instance alternative bases for representing polynomials and their impact on the numerical behavior of semidefinite programming solvers, or the use of symmetry or sparsity patterns to reduce the overall computational complexity.