Skip to content Skip to navigation

Connexions

You are here: Home » Content » Constrained Approximation and Mixed Criteria

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

    • External bookmarks
  • E-mail the authors

Recently Viewed

This feature requires Javascript to be enabled.

Constrained Approximation and Mixed Criteria

Module by: Daniel Williamson, C. Sidney Burrus

Trade-off of Error Measures and Design Specifications

In many filter design problems, more than one criterion is important. For example, both L2L2 and L∞L∞ may be of interest in one filter. Often one is posed as a constraint and the other as an optimized variable. Indeed, because L2L2 approximation minimizes the error energy and because Parseval's theorem states that an optimal L2L2 frequency domain approximation is also an optimal L2L2 time domain approximation, an L∞L∞ constrained minimum L2L2 error approximation seems a good practical approach. To see how this might have advantages, it is informative to examine the relationship of the L2L2 error to the L∞L∞ error as the constraint is varied from tight to loose Entry 66, Entry 2 in Figure 1. From this one can see just how sensitive one error is to the other and how the traditional designs are extremes on this diagram.

Figure 1: The Squared Error vs. the Chebyshev Error for the Constrained Least Squared Error FIR Filter
figCLS2.png

Another trade-off is the error in a Chebyshev design as a function of the transition band location. There are certain locations of transition band or band edges that give much lower ripple size than others. Rabiner has examined that relation Entry 56, Entry 55.

Constrained Least Squares Design

There are problems where the peak error or Chebyshev error is important. This can be minimized directly using the Remez exchange algorithm but, in many cases, is better controlled by use of a peak error constraint on the basic least squared error formulation of the problem Entry 2, Entry 6, Entry 66, Entry 5. An efficient algorithm for minimizing the constrained least squared error uses Lagrange multipliers Entry 41, Entry 40 and the Kuhn-Tucker conditions Entry 66, Entry 65.

Similar to the Chebyshev design problem, there are two formulations of the problem: one where there is a well defined transition band separating the desired signal spectrum (passband) from the noise or interfering signal spectrum (stopband) and the second where there is a well defined frequency that separates the pass and stopband but no well defined transition band.

The first case would include situations with signals residing in specified bands separated by “guard bands" such as commercial radio and TV transmissions. It also includes cases where due to multirate sampling, certain well defined bands are aliased into other well defined bands. The Parks-McClellan and Shpak-Antoniou Chebyshev designs address this case for the Chebyshev error. Adams' method Entry 2, Entry 1, Entry 3, Entry 6, Entry 61, Entry 5 described below applies to the constrained least squares design with a specified transition band.

The second case would include signals with known spectral support with additive white or broad-band noise. In these cases there is no obvious transition band or “don't care" band. The Hoffstetter-Oppenheim-Siegel and the method of (Reference) address this case for a Chebyshev design. The method in section below applies to the constrained least squares design Entry 66 without a specified transition band.

The Lagrangian

To pose the constrained least squared error optimization problem, we use a Lagrange multiplier formulation. First define the Lagrangian as

L = P ∫ 0 π ( A ( ω ) - A d ( ω ) ) 2 d ω + ∑ i μ i A ( ω i ) - [ A d ( ω i ) ± T ( ω i ) ] L = P ∫ 0 π ( A ( ω ) - A d ( ω ) ) 2 d ω + ∑ i μ i A ( ω i ) - [ A d ( ω i ) ± T ( ω i ) ] (1)

where the μiμi are the necessary number of Langrange multipliers and PP is a scale factor that can be chosen for simplicity later. The first term in (Equation 1) is the integral squared error of the frequency response to be minimized and the second term will be zero when the equality constraints are satisfied at the frequencies, ωiωi. The function T(ω)T(ω) is the constraint function in that A(ω)A(ω) must satisfy

A d ( ω ) + T ( ω ) ≥ A ( ω ) ≥ A d ( ω ) - T ( ω ) . A d ( ω ) + T ( ω ) ≥ A ( ω ) ≥ A d ( ω ) - T ( ω ) . (2)

Necessary conditions for the minimization of the integral squared error are that the derivative of the Lagrangian with respect to the filter parameters a(n)a(n) defined in ((Reference)) and to the Lagrange multipliers μiμi be zero Entry 69.

The derivatives of the Lagrangian with respect to a(n)a(n) are

d L d a ( n ) = P ∫ 0 π 2 ( A ( ω ) - A d ( ω ) ) d A d a d ω + ∑ i μ i d A d a ω i d L d a ( n ) = P ∫ 0 π 2 ( A ( ω ) - A d ( ω ) ) d A d a d ω + ∑ i μ i d A d a ω i (3)

where from ((Reference)) we have for n=1,2,⋯,Mn=1,2,⋯,M

d A ( ω ) d a ( n ) = cos ( ω n ) d A ( ω ) d a ( n ) = cos ( ω n ) (4)

and for n=0n=0

d A ( ω ) d a ( 0 ) = K . d A ( ω ) d a ( 0 ) = K . (5)

For n=1,2,⋯,Mn=1,2,⋯,M this gives

d L d a ( n ) = 2 P ∫ A ( ω ) cos ( ω n ) d ω - ∫ A d ( ω ) cos ( ω n ) d ω + ∑ i μ i cos ( ω i n ) d L d a ( n ) = 2 P ∫ A ( ω ) cos ( ω n ) d ω - ∫ A d ( ω ) cos ( ω n ) d ω + ∑ i μ i cos ( ω i n ) (6)

and for n=0n=0 gives

d L d a ( 0 ) = 2 P K ∫ A ( ω ) d ω - ∫ A d ( ω ) d ω + ∑ i μ i K . d L d a ( 0 ) = 2 P K ∫ A ( ω ) d ω - ∫ A d ( ω ) d ω + ∑ i μ i K . (7)

Using ((Reference)) for n=1,2,⋯,Mn=1,2,⋯,M, we have

d L d a ( n ) = π P a ( n ) - a d ( n ) + ∑ i μ i cos ( ω i n ) = 0 d L d a ( n ) = π P a ( n ) - a d ( n ) + ∑ i μ i cos ( ω i n ) = 0 (8)

and for n=0n=0

d L d a ( 0 ) = 2 π P K 2 a ( 0 ) - a d ( 0 ) + K ∑ i μ i = 0 . d L d a ( 0 ) = 2 π P K 2 a ( 0 ) - a d ( 0 ) + K ∑ i μ i = 0 . (9)

Choosing P=1/πP=1/π gives

a ( n ) = a d ( n ) - ∑ i μ i cos ( ω i n ) a ( n ) = a d ( n ) - ∑ i μ i cos ( ω i n ) (10)

and

a ( 0 ) = a d ( 0 ) - 1 2 K ∑ i μ i a ( 0 ) = a d ( 0 ) - 1 2 K ∑ i μ i (11)

Writing (Equation 10) and (Equation 11) in matrix form gives

a = a d - H μ . a = a d - H μ . (12)

where HH is a matrix with elements

h ( n , i ) = cos ( ω i n ) h ( n , i ) = cos ( ω i n ) (13)

except for the first row which is

h ( 0 , i ) = 1 2 K h ( 0 , i ) = 1 2 K (14)

because of the normalization of the a(0)a(0) term. The ad(n)ad(n) are the cosine coefficients for the unconstrained approximation to the ideal filter which result from truncating the inverse DTFT of Ad(ω)Ad(ω).

The derivative of the Lagrangian in (Equation 1) with respect to the Lagrange multipliers μiμi, when set to zero, gives

A ( ω i ) = A d ( ω i ) ± T ( ω i ) = A c ( ω i ) A ( ω i ) = A d ( ω i ) ± T ( ω i ) = A c ( ω i ) (15)

which is simply a statement of the equality constraints.

In terms of the filter's cosine coefficients a(n)a(n), from ((Reference)), this can be written

A c ( ω i ) = ∑ n a ( n ) cos ( ω i n ) + K a ( 0 ) A c ( ω i ) = ∑ n a ( n ) cos ( ω i n ) + K a ( 0 ) (16)

and as matrices

A c = G a A c = G a (17)

where AcAc is the vector of frequency response values which are the desired response plus or minus the constraints evaluated at the frequencies in the constraint set. The frequency response must interpolate these values. The matrix GG is

g ( i , n ) = cos ( ω i n ) g ( i , n ) = cos ( ω i n ) (18)

except for the first column which is

g ( i , 0 ) = K . g ( i , 0 ) = K . (19)

Notice that if K=1/2K=1/2, the first rows and columns are such that we have GT=HGT=H.

The two equations (Equation 12) and (Equation 17) that must be satisfied can be written as a single matrix equation of the form

I H G 0 a μ = a d A c I H G 0 a μ = a d A c (20)

or, if K=1/2K=1/2, as

I G T G 0 a μ = a d A c I G T G 0 a μ = a d A c (21)

which have as solutions

μ = ( G H ) - 1 ( G a d - A c ) a = a d - H μ μ = ( G H ) - 1 ( G a d - A c ) a = a d - H μ (22)

The filter corresponding to the cosine coefficients a(n)a(n) minimize the L2L2 error norm subject the equality conditions in (Equation 17).

Notice that the term in (Equation 22) of the form GadGad is the frequency response of the optimal unconstrained filter evaluated at the constraint set frequencies. Equation (Equation 22) could, therefore, be written

μ = ( G H ) - 1 ( A u - A c ) μ = ( G H ) - 1 ( A u - A c ) (23)

The Constrained Weighted Least Squares Design of FIR Filters

Combining the weighted least squared error formulation with the constrained least squared error gives the general formulation of this class of problems.

We now modify the Lagrangian in (Equation 1) to allow a weighted squared error giving

L = 1 π ∫ 0 π W ( ω ) ( A ( ω ) - A d ( ω ) ) 2 d ω + ∑ i μ i A ( ω i ) - A d ( ω i ) ± T ( ω i ) L = 1 π ∫ 0 π W ( ω ) ( A ( ω ) - A d ( ω ) ) 2 d ω + ∑ i μ i A ( ω i ) - A d ( ω i ) ± T ( ω i ) (24)

with a corresponding derivative of

d L d a ( n ) = 2 π ∫ W ( ω ) ( A ( ω ) - A d ( ω ) d A d a d ω + ∑ i μ i d A d a ω i d L d a ( n ) = 2 π ∫ W ( ω ) ( A ( ω ) - A d ( ω ) d A d a d ω + ∑ i μ i d A d a ω i (25)

The integral cannot be carried out analytically for a general weighting function, but if the weight function is constant over each subband, ((Reference)) can be written

d L d a ( n ) = 2 π ∑ k ∫ ω k ω k + 1 W k ( ∑ m = 1 M a ( m ) cos ( ω m ) + K a ( 0 ) - A d ( ω ) ) cos ( ω n ) d ω + ∑ i μ i d A d a ω i d L d a ( n ) = 2 π ∑ k ∫ ω k ω k + 1 W k ( ∑ m = 1 M a ( m ) cos ( ω m ) + K a ( 0 ) - A d ( ω ) ) cos ( ω n ) d ω + ∑ i μ i d A d a ω i (26)

which after rearranging is

= ∑ m = 1 M 2 π ∑ k W k ∫ ω k ω k + 1 ( cos ( ω m ) cos ( ω n ) ) d ω a ( m ) = ∑ m = 1 M 2 π ∑ k W k ∫ ω k ω k + 1 ( cos ( ω m ) cos ( ω n ) ) d ω a ( m ) (27)
- 2 π ∑ k W k ∫ ω k ω k + 1 A d ( ω ) cos ( ω n ) d ω + ∑ i μ i cos ( ω i n ) = 0 - 2 π ∑ k W k </