LMI Characterization for The Convex Hull of TrigonometricCurves and ApplicationsH.D. Tuan∗,T.T.Son†,B.Vo+and T.Q. NguyenAbstract— In this paper, we develop a new linear matrixinequality (LMI) technique, which is practical for solutionsof the general trigonometric semi-infinite linear constraint(TSIC) of competitive orders. Based on the new full LMIcharacterization for the convex hull of a trigonometric curve,it is shown that the semi-infinite optimization problem in-volving TSIC can be solved by LMI optimization problemwith additional variables of dimension just n, the order ofthe the trigonometric curve. Our solution method is veryrobust which allows us to address almost all practical filterdesign problems. Unlike most previous works involving severalcomplex mathematical tools, our derivation arguments arebased on simple results of the convex analysis and some formalelementary transforms. Furthermore, many filter/filterbankdesign problems can be reformulated as the optimization oflinear/convex quadratic objectives over the trigonometric semi-infinite constraints (TSIC). Based on this reformulation, theseproblems can be equivalently reduced to LMI optimizationproblems with the minimal size. Our examples of designingup to 1200-tap filters verifies the viability of our formulation.I. INTRODUCTIONA trigonometric curve is the setCa,b:= {(1, cos t, cos 2t, ..., cos nt)T:cos t ∈ [cos a, cos b] ⊂ [−1, 1]}⊂Rn+1,(1)and its polar is defined asC∗a,b= {u ∈ Rn+1: u, v≥0 ∀ v ∈ Ca,b}. (2)The trigonometric semi-infinite linear constraint (TSIC) invariable x ∈ R¯nAx + d ∈ C∗a,b,A∈ R(n+1)ׯn,d∈ Rn+1(3)includes several interesting interpretations in signal process-ing as a particular case. For instance, the particular casex ∈ C∗π,0(4)means that x =(x0,x1, ..., xn) is a positive real sequence:H(ejω):=nh=0xhcos hω ≥ 0 ∀ ω ∈ [0,π]. (5)∗School of Electrical Engineering and Telecommunication, Univer-sity of New South Wales, UNSW Sydney, NSW 2052, [email protected]†Department of Electrical and Computer Engineering,Toyota Insti-tute of Technology, Hisakata 2-12-1, Nagoya 468-8511, [email protected]+Department of Electrical and Electronic Engineering, Uni-versity of Melbourne, Parkville, Vic 3052, AUSTRALIA-Email:[email protected]Department of Electrical and Computer Engineering, University ofCalifornia in San Diego, 9500 Gilman Dr., La Jolla CA 92093-0407 USA;Email:[email protected] constraint Ax + d ∈ C∗π,0also arises in problems suchas FIR energy compaction filer design, signal-adapted filterbanks etc. (see e.g. [6], [8] and references therein).More generally, peak-error constraints [1] for frequencyresponses of the linear phase filters are the particular casesof (3): given a passband [0,ωp] ⊂ [0,π/2] and stopband[ωs,π], the peak-error constraints in the passband andstopband of a linear phase filerH(z)=z−n[x0+12ni=1xi(zi+ z−i)] (6)which are expressed as|H(ejω) − e−jnω| <δp∀ω ∈ [0,ωp]|H(ejω)| <δs∀ω ∈ [ωs,π](7)are indeedx +(δp− 1)e1∈ C∗ωp,0, −x +(δp+1)e1∈ C∗ωp,0,x + δse1∈ C∗π,ωs, −x + δse1∈ C∗π,ωs,(8)respectively, where e1=(1, 0,..0) ∈ Rn+1.The simplest and traditional treatment for the TSIC con-straints (3) is just to replace it by a finite number of linearconstraints: Ax + d, (1, cos ti, cos 2ti, ..., cos nti)T≥0,cos ti∈ [cos a, cos b],i=0, 1, 2, ...N.(9)Obviously, any feasible solution of these linear constraintsis not guaranteed to be a feasible one of the TSIC con-straints. As mentioned in [6] no matter as such a set offinite grid points {ti,i=0, 1, ..., N} is chosen denseon [b, a], linear constraints (9) cannot bring TSIC (3). Onthe other hand, in the state-space setting for the filter(5), the classical Kalman-Yakubovich-Popov lemma (seee.g. [9]) can reformulate the particular positive constraint(4) into (convex) linear matrix inequality (LMI) constraintinvolving additional Lyapunov symmetric matrix variableof dimension n(2n +1).Quite recently, LMI has been discovered as a powerfultool for handling general TSIC (3) as well. It has beenestablished in [4] that TSIC (3) is characterized by LMI con-straints involving two additional symmetric matrix variablesof dimension (n+1)(n+2)/2 and n(n+1)/2, respectively.Usually the order 2n of the designed FIR filters is not smallin practical applications to attain good frequency response.As a result, the dimension of the corresponding LMIoptimization problem may be very high (with more thanseveral thousands of additional variables), preventing themfrom being efficiently and practically solvable by existingIV - 4250-7803-8874-7/05/$20.00 ©2005 IEEE ICASSP 2005LMI solvers such as [10]. A much more efficient LMItechnique specialized for handling the particular positiveconstraint (4) has been developed in [2]. A numerical resulthas been provided in [2] for order n = 600 (for suchorder n, as m entioned, the corresponding LMI formulation[4] for (4) requires an additional variable of dimension(n + 1)(n +2)/2 = 180901). It has been also shownin [5], [3] that the general TSIC (3) can be equivalentlytransformed to the particular positive real constraint (4).However, as recognized in [5], [3], the trouble there isthat the resulting LMI constraint is ill-posed even for verymoderate order n due the ill-condition of the used transformmatrix. It should be noted that the mentioned LMI basedformulation of [4] with much large dimensional variables isstill to handle with the case n =50. An alternative linearprogramming based method to handle the general TSIC (3)has been developed in [11], which allows to solve it for theorder n up to 100. However, the case of higher order is stillpersistent.In this paper, a new LMI technique is developed in practicalfor solutions of the general TSIC (3) of much more compet-itive orders. Based on the new full LMI characterization forthe convex hull of the trigonometric curve Ca,bdefined by(1), which is also of independent interest, we show that thesemi-infinite optimization problem involving TSIC (3) canbe solved by the LMI optimization problem with additionalvariables of dimension just n. The solution of our methodis very robust and allows us to address almost all practicalfilter design problems. Our derivation arguments are onlybased on simple results of the convex analysis [9] and someformal elementary transforms.The paper is organized as follows. After Section 1,