Efficient Large-Scale Filter/Filterbank Design via LMI Characterization of Trigonometric Curves

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 55, NO. 9, SEPTEMBER 2007

4393

Efficient Large-Scale Filter/Filterbank Design via LMI Characterization of Trigonometric Curves Hoang Duong Tuan, Tran Thai Son, Ba-Ngu Vo, and Truong Q. Nguyen

Abstract—Many filter and filterbank design problems can be posed as the optimization of linear or convex quadratic objectives over trigonometric semi-infinite constraints. Recent advances in design methodology are based on various linear matrix inequality (LMI) characterizations of the semi-infinite constraints, and semidefinite programming (SDP) solutions. Despite these advances, the design of filters of several hundredth order, which typically arise in multicarrier communication and signal compression, cannot be accommodated. This hurdle is due mainly to the large number of additional variables incurred in the LMI characterizations. This paper proposes a novel LMI characterization of the semi-infinite constraints that involves additional variables of miminal dimensions. Consequently, the design of high-order filters required in practical applications can be achieved. Examples of designs of up to 1200-tap filters are presented to verify the viability of the proposed approach.

a linear TSIC in the filter coefficients [19], [32]

(2)

(more precisely, (2) leads to two linear TSICs [16]). More general constraints [1], [2], [37] involving bounds on the frequency response of the FIR filter are also expressible in in the terms of linear TSIC. Imposing a passband ripple of passband , and a stopband attenuation of in is equivalent to the following linear TSICs the stopband

Index Terms—Filter and filter bank, semidefinite programming, trigonometric polynomial.

(3)

I. INTRODUCTION ILTER and filter bank design invariably involves spectral mask constraints or -norm criteria that result in optimization problems with trigonometric semi-infinite constraints (TSIC) [17], [20], [21], [34]. A simple example of a TSIC is the positive real constraint in the variable

F

The linear TSICs in (1)–(3) are instances of a more general class of linear TSIC that can be conveniently described in terms of a trigonometric curve and its polar. Let (4)

(1)

then the trigonometric curve

is defined as (5)

Other examples of TSIC can be found in the design of linear -norm of a linear phase phase FIR filters. Constraining the FIR filter to be less than some bound can be expressed as

and its polar

is given by (6)

Manuscript received October 11, 2004; revised March 5, 2006. This work was supported by the Australian Research Council by Grant ARC Discovery Project 0556174. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Henrique S. Malvar. H. D. Tuan is with the School of Electrical Engineering and Telecommunication, University of New South Wales, UNSW Sydney, NSW 2052, Australia (e-mail: [email protected]). T. T. Son is with the Department of Electrical and Computer Engineering, Toyota Institute of Technology, Nagoya 468-8511, Japan (e-mail: [email protected]). B.-N. Vo is with the Department of Electrical and Electronic Engineering, University of Melbourne, Parkville, Vic 3052, Australia (e-mail: [email protected]. au). T. Q. Nguyen is with the Department of Electrical and Computer Engineering, University of California in San Diego, La Jolla, CA 92093 USA (e-mail: [email protected]). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TSP.2007.896285

A linear TSIC in the variable as

can be written compactly

(7) In general, the constraint (7) arises in problems such as FIR energy compaction filter design, signal-adapted filter banks etc. (see, e.g., [17], [20], [21], [34], [6], [38], [39], and references therein) Observe that in terms of the polar of trigonometric curve, the positive real constraint (1) corresponds to the special case

1053-587X/$25.00 © 2007 IEEE Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

(8)

4394

the

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 55, NO. 9, SEPTEMBER 2007

-norm constraint (2) corresponds to

and the frequency mask constraints (3) correspond to

(9) Traditionally, there are a number of approaches to generic semiinfinite program (SIP), which involve some forms of approximations [16], [27]. The simplest treatment [20] for the TSIC (7) is to discretize the parameter , and impose the following finite number of linear constraints:

(10) Clearly, a feasible point of (10) is not necessarily a feasible point of the TSIC (7). Moreover, no matter how fine the finite grid is chosen, the linear constraints (10) cannot characterize the TSIC (7) exactly [17], [34]. A modification of this discretizing method has been also presented in [38]. In the last decade, the discipline of filter (and filterbank) design has experienced significant progress, brought about by the machinery of semidefinite programming (SDP). The key in these advances lies in the exact characterization of TSIC by linear matrix inequality (LMI) constraints, which converts an SIP into an SDP. However, the equivalent SDP has much higher dimension than the original SIP, which consequently limits these approaches to the design of only moderate-sized filters. Driven by the practical requirements of multicarrier communication and signal/image compression, the challenge lies in the development of efficient methods for dealing with designs of high-order filters. For the special case of positive real constraint (8), an equivalent LMI constraint involving an additional symmetric Lyacan be obtained punov matrix variable of dimension using a state-space representation for the filter and the classical Kalman-Yakubovich-Popov lemma [7], [26], [12]. A much more efficient LMI characterization of the positive real constraint (8) has been developed in [4] that can handle problems with of up to 600. It has also been shown in [15], [5] that the general TSIC (7) can be equivalently transformed to the positive real constraint (8). However, the resulting LMI constraint is ill-posed even for moderate values of due to the ill-conditioning of the transformation used [15], [5]. Recently, it has been established in [10] that the more general TSIC (7) can also be characterized by LMI constraints. This characterization involves two additional symmetric matrix and , revariables of dimensions spectively. As a result, the dimension of the corresponding SDP may grow beyond the capability of state-of-the-art primal-dual

interior point algorithms for the solutions of the SDP such as [31]. In particular, to handle the positive real constraint (8) with , this LMI formulation requires one additional variable of dimension . In this paper, we develop a new LMI technique capable of handling general linear TSIC (7) of much more competitive orders. Our key contribution is a novel LMI characterization of the (5). Based on this convex hull of the trigonometric curve result, SIPs involving the TSIC (7) can be converted to SDPs with additional variables of only dimension . This low-dimensional LMI characterization enables most high-order designs that arise from practical applications to be addressed in an efficient manner. Moreover, our derivation is based on simple arguments from convex analysis [28], in contrast to the approach of [10] which is based on lengthy mathematical derivations. The remainder of the paper is organized as follows: In Section II, the LMI characterization for the convex hull of the trigonometric curve (5) is developed. This result is used in Section III to derive LMI based solutions for optimization problems involving the TSIC (7). Applications to filter-bank and filter design problems are discussed in Sections IV and V, respectively. Some concluding remarks and future directions are outlined in Section VI. II. TRIGONOMETRIC MARKOV-LUKACS THEOREM AND CONVEX HULL This section develops an LMI characterization for the convex hull of the trigonometric curve defined by (5). We begin with a recap of the Markov-Lucacs theorem for characterizing nonnegative polynomials, which will be used to establish an analogous result for trigonometric polynomials. This result allows an LMI characterization of the convex hull of trigonometric curves to be derived. First some notations are in order: the standard notation denotes a (symmetric) positive semidefinite matrix1; of the matrices and is given the inner product , note that for . by its convex hull (conic hull), deFor a given set , is the smallest convex set noted by (cone) in that contains . The polar set of is the cone . It is straightforward to and if is a closed see that . convex cone then Let (11) then, the th-order moment matrix is a itive semidefinite matrix defined by [18]

-pos-

(12)

The role of moment matrices is shortly clarified in the following theorem. 1The dimension of the space of all n

2 n-symmetric matrices is n(n + 1)=2.

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

TUAN et al.: EFFICIENT LARGE-SCALE FILTER/FILTERBANK DESIGN

Theorem 1 (Markov-Lucacs Theorem) [22]: Any algebraic that is nonnegative on polynomial admits the representation (13), shown at the bottom of the page. Note that the matrix in the above representations is of size while the matrix is of size or . From here on, means the largest integer not exceeding . The original Markov-Lucacs if and Theorem (see, e.g., [18]) states that only if it admits the representation (14), shown at the bottom of the page. Clearly, as

4395

is

and accordingly, the matrix by the variable change created from

(16) i.e.,

. It is straightforward to show that

Define also (17)

(14) is a particular case of (13) (for ). On the other hand, the right-hand side (RHS) of (13) is a polynoso it must admit the mial in , which is nonnegative on representations like (14). Therefore, (13) is equivalent to (14). Comparing terms with the same power in on both sides of (13) results in a linear relationship between the vector of and the matrices coefficients of the algebraic polynomial , subsequently, the semi-infinite constraint is converted into an LMI constraint [22]. The general TSIC (7) can be equivalently described by an LMI in a similar manner through our trigonometric version of the Markov-Lucacs theorem. To show this, we define the th of size as moment trigonometric matrix the positive semidefinite matrix (15), at the bottom of the page,

and accordingly created from

is by the variable change (16), i.e., : see (61) in Appendix I. Naturally,

. The role of the introduced trigonometric moment matrices for trigonometric polynomials is similar to that of moment matrices for algebraic polynomials in the above Markov-Lucacs theorem: Theorem 2 (Trigonometric Markov-Lucacs Theorem): Any that is nonnegatrigonometric polynomial admits the representation (18), shown at the tive on bottom of the page, where

(19)

(13)

(14)

(15)

(18)

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

4396

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 55, NO. 9, SEPTEMBER 2007

Proof: Each term braic polynomial in

is the th-order Chebyshev alge[25], i.e.

(for the closed form of see [33]). Hence, there exists a unique invertible linear transformation taking to , i.e., there is a unique nonsingular square matrix such that

In fact, from the above representation of can be seen to be lower triangular with all nonzero diagonal elements and is thus nonsingular. Therefore, from the definition of and , we have

Suppose that . As algebraic polynomial in 1 there are matrices

can be expressed as a th-order , by the Markov-Lucacs Theorem and such that

A special case of Theorem 2 is the following corollary. is positive Corollary 1: A sequence if the trigonometric polyreal, i.e., nomial admits the representation (20), at the bottom of the page. Like the mentioned case for algebraic polynomials, on both by comparing terms with the same “power” sides of (18) one can easily obtain an equivalent new LMI constraint characterization for the trigonometric semi-infinite con[see Theorem 4 in straint Appendix II with the definitions (63), (64)]. Corollary 1 provides a new version of the Kalman-Yakubovich-Popov lemma for a positive real sequence of finite length. One can see that our derivation arguments are transparent with the help of the introduced trigonometric moment matrices. Moreover, the size of and in representations (18), (20), are matrices and (for even) or (for odd) versus in the LMI formulation of [10], i.e., we have substantially reduced the additional variables in the LMI characterization. However, such size is still high for practical applications and we will see later that such drawback can be avoided through the LMI characteri, to be derived shortly. zation for the convex hull of the set First, using the variable change (16) on both sides of (16) leads to the following result. admits the representation Lemma 1: If then for every (18) for some matrices , see the equation at the bottom of the page, where

This implies (21) From this result, the LMI characterization for the convex hull follows. Theorem 3: For the variables define the following LMI constraint: of

which is the RHS of (18) by (17). , from the Markov-Lucacs Theorem 1 it folFor lows that:

(22)

which can be shown equivalent to (18) by an analogous argument.

defined by (5) is fully Then, the convex hull of the set characterized by the LMI constraints: (23)

(20)

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

TUAN et al.: EFFICIENT LARGE-SCALE FILTER/FILTERBANK DESIGN

Consequently, the conic hull of

4397

is defined by

III. OPTIMIZATION APPLICATION A. Linear Objective Optimization

Proof: Suppose that is the set defined by the right . side of (23), and we have to show that is convex as it is described by LMIs. For any The set , it is obvious that, see the equations at the bottom of the page. Hence, and so by the definition of the convex hull. . It remains to show the inverse inclusion , we denote by its support funcFor any set in tion [28]

We will see later in Section IV that the linear phase QMF bank design belongs to the class of optimization of a linear objective subject to TSICs (7)

(24) which is the same as subject to

Suppose that

(26)

. For every

and according to Theorem 2 there are that the following representation holds

and

such

Using Lemma 1 gives

Since

and also , it follows that: . Consequently

(25)

and and

where and is the polar cone of . From Theorem 1 each in (26) is characterized by an LMI and of high diconstraint involving additional variables mension [see the constraint (69) in Appendix II], so (25)–(26) is in fact an SDP. On the other hand, by Theorem 3, each is characterized by an LMI without any additional variable involved, so we now use the convex duality theory to reduce the dimension of (26) as an LMI. We also develop an efficient method to derive the optimal solution of (25) and (26) from its dual program. The reader is also referred to [8] and [13] for efficient and robust implementations of the dual interior-point methods for SDPs. Using the Lagrange multiplier, (25), (26) is rewritten as

for

(27) Based on the convex duality (see, e.g., [28]) and Theorem 3, the dual problem of (27) is actually an SDP

Hence,

, or equivalently [28].

is proved analogously. The proof is The case complete. An immediate and interesting application of the above Theorem 3 is that a nonconvex optimization problem like can be equivalently solved by the SDP . On the other hand, as it is obvious , Theorem 3 allows us to handle the that general TSIC (7) by an LMI constraint with additional variables of minimal dimensions as we see in the next section.

subject to

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

(28)

4398

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 55, NO. 9, SEPTEMBER 2007

Let and be a feasible solution of the problems (25), (26), and (28), respectively. Correspondingly, and such that by Theorem 1 there are matrices

RHS of (18) (29)

Thus, based on (69), the optimal solution of (26) is retrieved of SDP (28) by the following from the optimal solution steps. of the null spaces of ei• Compute any bases for , or ther for . • To obtain the optimal solution of (25), (26) based on the , solve either the linear representation (63), (64) of program

Then, by (29) and Lemma 1, it is easy to compute the gap between feasible values shown in (30) at the bottom of the page, which is nonnegative in view of (22). The optimal solution and of the SDP (25), (26) and its dual (28) must satisfy the following complementary condition to make the dual gap zero. • For

(31) (36) (32) for under the following decompositions of

and

, or the linear program

:

(33) • For

(34)

(37) (35) under decompositions (33).

for

.

(30)

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

TUAN et al.: EFFICIENT LARGE-SCALE FILTER/FILTERBANK DESIGN

4399

B. Convex Quadratic Objective Optimization For the peak-error constrained filter design problem (see Section V), instead of the linear objective in (26), we have to deal with the convex quadratic objective subject to (26)

the gap between feasible values of (38) and (40) is easily computed

(38)

, which by Theorem 1 is actually subject to (69)

(39)

Then its dual becomes (40), as shown at the bottom of the page, which can be rewritten either as a linear conic optimization [31] for the most efficient computation, or more directly, as the SDP

(42) For any feasible solution and , one has , so the optimal solution of (38) and (40) must satisfy the complementary condition (43) (44)

(41) Notice that for every

It appears that must satisfy the overdetermined conditions (43) and (44). However, it can be easily shown that (43)–(44) are necessary and sufficient (Kuhn-Tucker condition) for the opti. Therefore, the optimal solution of (38) is dimality of rectly retrieved from the optimal solution of (40) by (44), which is merely equivalent to the solution of the following linear equation system in : (45) Thus, the optimal solution of the semi-infinite program (38) can be easily found from the program (40) involving totally scalar variables.

(40)

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

4400

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 55, NO. 9, SEPTEMBER 2007

IV. LINEAR PHASE QUADRATURE MIRROR FILTER (QMF) BANK DESIGN A. Optimization Formulation QMF bank is a very important class of digital filter banks because of its potential applications in subband coding [35], [36], [30] and spread spectrum signal processing for intercept communication [24]. The starting point is the two-channel QMF bank design problem, which can be formulated as follows (see Fig. 1). and , design two (synGiven two analysis filters thesis) filters and such that

Fig. 1. QMF filter bank with 2 analysis and 2 synthesis channels.

or, in short

(50)

(46) (47) Now, it is also true that [32] It is well known that (46)–(47) deal with the perfect reconstruction of the filter bank in the absence of the noises: (46) is the distortion-free condition while (47) is the aliasing-free one. to if necessary, without loss By changing of generality we can set . Thus, a natural optimization formulation for handling constraints (46), (47) is as follows [11]:

subject to

(51)

where

are vectors such that

(48)

where denotes the standard -norm, i.e., we try to minimize the distortion effect while preserving the aliasing-free condition. and are linear phase filters with even Suppose that orders and , under the assumption , so they are expressed as

Then, the constraint (47) is written as [32]

(52) Let of matrix

be any basis for the null space . Then instead of (50) we use (53)

and accordingly (51) and (48) (for

) are rewritten as

(54)

(49) Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

(55)

TUAN et al.: EFFICIENT LARGE-SCALE FILTER/FILTERBANK DESIGN

4401

TABLE I DATA OF PROBLEM (60) IN THE SIMULATION EXAMPLES WITH ! = 2k AND

! = 2k

design a linear phase filter (2) such that the weighted-square error under the peak-error constraints (3) is minimized:

(58)

Fig. 2. Frequency responses of linear phase filters in

H

Clearly, the objective function in (58) is a convex quadratic function in the filter coefficients , where optimization.

where (59) Thus, with , we obtain the following optimization formulation, which is a particular case of (26), [32]

For , in view of the equivalence between (3) and (9), the equivalent form of (58) is the following particular case of (38):

(56) (57) (60) where and

is the unit vector in .

with 1 at the first component

B. Simulation In this simulation, the analysis filters are taken from Example 4.1 of [23]. With the delay equal , the orders of synthesis and are equal 56 and 54 , filters respectively. The corresponding LMI formulation [10] requires two symmetric matrix variables of size 39 39, which in total are equivalent to 1560 scalar variables. Based on Theorem 1, another LMI formulation for (56)–(57) still requires four symmetric matrix variables of size 20 20, which in total are equivalent to 840 scalar variables. However, the corresponding LMI optimization problem (28) in this case is still of a moderate size , which with 72 scalar variables, gives the value given by the linear prois better than the value gramming based algorithm [32]. This also means that the reconstruction error is almost zero. The frequency responses for all filters are shown in Fig. 2, which look very similar to others given in [23] and [32] very much. V. FIR FILTER DESIGN Generally, a peak-constrained least-squares errors (PCLS) low-pass filter design problem can be formulated as follows and stopband , we wish to [2]: given a passband

As aforementioned, (60) is solved by its dual (41), and after that its solution is calculated by (43) and (44). Moreover, for high-order filter design, we can avoid the calculation for the inverse matrix in (44) by alternatively solving the linear equation system (45) in . A. Simulation Equation (60) is considered for different specifications given and in Table I. Note that are the passband and stopband ripples measured in decibels; the and is set to 2 and 2000, respectively. Fig. 3 value of shows the frequency responses of the designed 401-tap filter. The corresponding optimal value of (41) is equal to 0.06, and . The the left-hand side (LHS) of (43) is about coefficients of the designed filter is calculated by (44). As de, and the scribed in Table I, the passband is set to . We can see from Fig. 3 stopband is equal to that the filter frequency response in the passband is perfectly equal to 0 db, and its value in the stopband is less than db. This means that the result of the designed filter strongly satisfies the peak constraints. The result of our proposed method is compared with that of the Parks-McClellan (PM) method in the same conditions of filter order and passband-stopband constraints. We can see from Fig. 3 that the filter frequency response of the proposed method is better than that of the PM method.

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

4402

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 55, NO. 9, SEPTEMBER 2007

Fig. 3. Frequency response of the linear phase 401-tap FIR filter.

Fig. 4. Frequency response of the 1201-tap linear phase FIR filter.

Therefore, the result of the designed filter strongly satisfies the peak constraints. In practice, we may like to design an FIR filter that has the size of transition band, the ripples in passband and the frequency response of stopband as small as possible. As a result, we increase the order of filter to satisfy the designed constraints, but the tradeoff is the complexity of computation. This tradeoff in our method is mitigated greatly because the number of variables in our proposed method is equal to the number of coefficients of our designed filter. Similarly, Fig. 4 presents the frequency responses of the 1201-tap filter. The corresponding optimal value of (41) is equal to 0.2, and the LHS of (43) is equal . In this case, the values of and are set to to 0.1 and 0.105, respectively. Consequently, the transition is almost vertical.

the design of biorthogonal cosine-modulated filter bank with about channels and with length of about for asymmetric digital subscriber line (ADSL) in high bandwidth communication, the design of antenna pattern are under way. Our approach also applies to multidimensional filter design as will be addressed in an another paper. APPENDIX I ANALYTICAL FORMULA OF THE MATRICES

AND

In (17) and after we have defined the matrices and , which, in fact, have the following analytical expressions in (61) at the bottom of the page. In general, for any , matrix is of dimension and defined by (62) and (63) at the top of the next page, -symmetric matrices given as with

VI. CONCLUDING REMARKS LMI optimization is a very useful tool for filter/filter-bank design problems. Until now, the applicability of LMI has been limited due to the high dimensional nature of the artificial variables in LMI formulations for such problems. In this paper, we have developed an LMI formulation of moderate size for such problems, which makes LMI not only useful but also powerful. More advanced applications of our results in problems such as

(64) where

is the Kronecker delta function ( whenever ).

and

(61)

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

TUAN et al.: EFFICIENT LARGE-SCALE FILTER/FILTERBANK DESIGN

4403

(62)

(63)

(68)

(69)

APPENDIX II AN EQUIVALENT STATEMENT OF THEOREM 2 AND CONSEQUENCE

REFERENCES

We can easily see that Theorem 2 provides LMI characterization for the semi-infinite constraint through the following simple argument. For convenience, we also make

(65) Define the

-symmetric matrices

(66) and accordingly

[1] J. W. Adams, “New optimal window,” IEEE Trans. Signal Process., vol. 39, pp. 1753–1769, 1991. [2] J. W. Adams and J. L. Sullivan, “Peak-constrained least squares optimization,” IEEE Trans. Signal Process., vol. 46, pp. 306–321, 1998. [3] A. N. Akansu and R. A. Haddad, Mutiresolution Signal Decomposition: Transforms, Subbands, Wavelets. New York: Academic, 2001. [4] B. Alkire and L. Vandenberge, “Handling nonnegative constraints in spectral estimation,” in Proc. 34th Asilomar Conf. Signals, Syst., Comput., 2000, pp. 202–206. [5] B. Alkire and L. Vandenberge, “Interior-point methods for magnitude filter design,” in Proc. 26th IEEE Int. Conf. Acoust., Speech, Signal Process., 2001. [6] B. Alkire and L. Vandenberge, “Convex optimization problems involving finite autocorrelation sequences,” Math. Programm., Ser. A, vol. 93, pp. 331–359, 2002. [7] B. D. O. Anderson and S. Vongpanitlerd, Network Analysis and Synthesis: A Modern System Theory Approach. Englewood Cliffs, NJ: Prentice-Hall, 1973. [8] S. J. Benson, Y. Ye, and X. Zhang, “Solving large-scale sparse semidefinite programs for combinatorial optimization,” SIAM J. Optimiz., vol. 10, pp. 443–461, 2000. [9] S. Boyd, V. Balakrishnan, and P. Kabamba, “A bisection method for norm of a transfer matrix and related problem,” computing the Mathematics of Contr., Signal, Syst., vol. 2, pp. 207–219, 1989. [10] T. Davidson, Z. Q. Luo, and J. F. Sturn, “Linear matrix inequality formulation of spectral mask constraints with applications to FIR filter design,” IEEE Trans. Signal Process., vol. 50, pp. 2702–2715, 2002. opti[11] T. Chen and B. Francis, “Design of multirate filter banks by mization,” IEEE Trans. Signal Process., vol. 43, pp. 2822–2830, 1995. [12] B. Dumitrescu, I. Tabus, and P. Stoica, “On the parameterization of positive real sequences and MA parameter estimation,” IEEE Trans. Signal Process., vol. 49, pp. 2630–2639, 2001. [13] M. Fukuda, M. Kojima, and M. Shida, “Lagragian dual interior-point methods for semi-definite programs,” SIAM J. Optimiz., vol. 12, pp. 1007–1031, 2002. [14] P. Gahinet, A. Nemirovski, A. Laub, and M. Chilali, LMI Control Toolbox. New York: The Math. Works Inc., 1995. [15] Y. Genin, Y. Hachez, Yu. Nesterov, and P. Van Dooren, “Convex optimization over positive polynomials and filter design,” in Proc. 2000 UKACC Int. Conf. Control, 2000, Cambridge Univ.. [16] R. Hettich and K. Kortanek, “Semi-infinite programming: Theory methods and applications,” SIAM Rev., vol. 35, pp. 380–429, 1993. [17] A. Kirac and P. P. Vaidyanathan, “Theory and design of optimum FIR compaction filters,” IEEE Trans. Signal Process., vol. 46, pp. 903–919, 1998.

H

H

(67) then the equivalent formulation of Theorem 2 is the following theorem. Theorem 4: The trigonometric polynomial of degree less than is nonnegative on if and only if there are positive semidefinite matrices and such that is shown in (68) at the top of the unit vector in with 1 at th the page. Define component. Then by Theorem 4, (26) is actually the following LMI constraint in (69) at the top of the page.

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.

4404

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 55, NO. 9, SEPTEMBER 2007

[18] M. Krein and A. Nudel’man, “The Markov moment problem and extremal problems,” Transl. Math. Monographs, vol. 50, 1977. [19] J. H. McClellan and T. W. Parks, “A unified approach to the design of optimal FIR linear phase digital filters,” IEEE Trans. Circuit Theory, vol. CT-20, pp. 697–701, 1973. [20] P. Moulin, M. Anitescu, K. Kortanek, and F. A. Potra, “The role of linear semi-infinite programming in signal adapted QMF bank design,” IEEE Trans. Signal Process., vol. 45, pp. 2160–2174, 1997. [21] P. Moulin and M. K. Mihcak, “Theory and design of signal-adapted FIR paraunitary filterbanks,” IEEE Trans. Signal Process., vol. 46, pp. 920–929, 1998. [22] Y. Nesterov, “Squared functional systems and optimization problems,” in High Performance Optimization, H. Frenk, Ed. Boston, MA: Kluwer Academic, 2000, pp. 405–440. [23] T. Q. Nguyen and P. P. Vaidyanathan, “Two-channel perfect-reconstruction FIR QMF structures which yield linear-phase analysis and synthesis filters,” IEEE Trans. Acoust. Signal Process., vol. 37, pp. 676–690, 1989. [24] R. S. Orr, T. C. Farrell, and G. E. Prescott, “Transform-based low probability of intercept communication,” in Wavelet, Subband and Block Transforms in Communications and Multimedia, A. N. Akansu and M. J. Medley, Eds. Boston, MA: Kluwer Academic, 1999, pp. 91–139. [25] J. G. Proakis and D. G. Manolakis, Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1996. [26] A. Rantzer, “On the Kalman-Yakubovich-Popov lemma,” Syst. Contr. Lett., vol. 28, pp. 7–10, 1996. [27] R. Reemtsen and J.-J. Ruckman, Eds., Semi-Inifinite Programming. Dordrecht, Germany: Kluwer Academic, 1998. [28] T. Rockafellar, Convex Analysis. Princeton, NJ, 1970. [29] A. K. Soman, P. P. Vaidyanathan, and T. Q. Nguyen, “Linear phase paraunitary filter banks: Theory, factorizations and designs,” IEEE Trans. Signal Process., vol. 41, pp. 3480–3496, 1993. [30] G. Strang and T. Q. Nguyen, Wavelets and Filter Banks. Wellesley, MA: Wellesley-Cambridge Press, 1996. [31] J. Sturm, “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,” Optimiz. Methods Software, vol. 11–12, pp. 625–653, 1999. [32] H. D. Tuan, L. H. Nam, H. Tuy, and T. Q. Nguyen, “Multicriterion optimized QMF bank design,” IEEE Trans. Signal Process., vol. 51, pp. 2582–2591, 2003. [33] H. D. Tuan, T. T. Son, H. Tuy, and T. Q. Nguyen, “New linear programming based filter design,” IEEE Trans. Cicruits Syst. II, Digit. Signal Process., vol. 52, pp. 276–281, 2005. [34] J. Tuqan and P. P. Vaidyanathan, “A state-space approach to the design of globally optimal FIR energy compaction filters,” IEEE Trans. Signal Process., vol. 48, pp. 2822–2838, 2000. [35] P. P. Vaidyanathan, Multirate Systems and Filter Banks. Englewood Cliffs, NJ: Prentice-Hall, 1993. [36] M. Vetterli and J. Kovacevic, Wavelets and Subband Coding. Englewood Cliffs, NJ: Prentice-Hall, 1995. [37] B. Vo, A. Cantoni, and K. L. Teo, Filter Design with Time Domain Mask Constraints: Theory and Applications. Boston, MA: Kluwer Academic, 2001. [38] S. Wu, S. Boyd, and L. Vandenberge, “FIR filter design via spectral factorization and convex optimization,” in Applied and Computational Control, Signals and Circuits, ser. Springer International Series in Engineering and Computer Science, B. Datta, Ed. Berlin, Germany: Springer, ch. 5, pp. 215–245. [39] M. R. Wilbur, T. Davidson, and J. P. Reilly, “Efficient design of oversampled NPR GDFT filter banks,” IEEE Trans. Signal Process., vol. 52, pp. 1947–1963, 2004.

Hoang Duong Tuan was born in Hanoi, Vietnam. He received the diploma and the Ph.D. degree, both in applied mathematics, from Odessa State University, Ukraine, in 1987 and 1991, respectively. From 1991 to 1994, he was a Researcher with Optimization and Systems division, Vietnam National Center for Science and Technologies. He spent nine academic years in Japan as an Assistant Professor with the Department of Electronic-Mechanical Engineering, Nagoya University, from 1994 to 1999, and then as an Associate Professor with the Department of Electrical and Computer Engineering, Toyota Technological Institute, Nagoya, from 1999 to 2003. Presently, he is an Associate Professor with the School of Electrical Engineering and Telecommunications, the University of New South Wales, Sydney, Australia. His research interests include theoretical developments and applications of optimization-based methods in many areas of control, signal processing, and communication.

Tran Thai Son received the Bachelor’s degree in science from the Department of Information Technology, the University of Natural Sciences, HCM city, Vietnam, in 1997, and the Ph.D. degree in engineering from the Department of Electrical and Computer Engineering, Toyota Technological Institute, Japan, in 2005. Currently, he is a Postdoctoral Fellow with the Department of Electrical and Computer Engineering, Toyota Technological Institute, Japan. His research interests include filtering, image processing, and pattern recognition.

Ba-Ngu Vo was born in Saigon, Vietnam. He received the B.Sc./B.E. degree (with first class honors) and the Ph.D. degree in 1994 and 1997, respectively. He is currently an Associate Professor with the Department of Electrical and Electronic Engineering, University of Melbourne, Melbourne, Australia. His research interests are stochastic geometry, random sets, multitarget tracking, optimization, and signal processing.

Truong Q. Nguyen received the B.S., M.S., and Ph.D. degrees in electrical engineering from the California Institute of Technology, Pasadena, in 1985, 1986, and 1989, respectively. He was with the Massachusetts Institute of Technology Lincoln Laboratory, Cambridge, from June 1989 to July 1994, as a member of Technical Staff. Since August 1994 to July 1998, he was with the Electrical and Computer Engineering Department, University of Wisconsin, Madison. He was with Boston University, Boston, MA, from 1996 to 2001, and is currently with the Electrical and Computer Engineering Department, University of California at San Diego. His research interests are in the theory of wavelets and filter banks and applications in image and video compression, telecommunications, bioinformatics, medical imaging and enhancement, and analog/digital conversion. He is the coauthor (with Prof. Gilbert Strang) of a popular textbook, Wavelets and Filter Banks (Cambridge, U.K.: Wellesley-Cambridge Press, 1997) and the author of several matlab-based toolboxes on image compression, electrocardiogram compression, and filter bank design. He also holds a patent on an efficient design method for wavelets and filter banks and several patents on wavelet applications including compression and signal analysis. Prof. Nguyen received the IEEE TRANSACTIONS IN SIGNAL PROCESSING Paper Award (Image and Multidimensional Processing area) for the paper he cowrote with Prof. P. P. Vaidyanathan on linear-phase perfect-reconstruction filter banks in 1992. He received the NSF Career Award in 1995 and is currently the Series Editor (Digital Signal Processing) for Academic Press. He served as Associate Editor for the IEEE TRANSACTIONS ON SIGNAL PROCESSING from 1994 to 1996 and for the IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS from 1996 to 1997.

Authorized licensed use limited to: Univ of Calif San Diego. Downloaded on February 24, 2009 at 15:24 from IEEE Xplore. Restrictions apply.