As mentioned in (Reference), one can address problem Equation 1 in two ways depending on how one views the role of the transition band in a CLS problem. The original problem posed by Adams in [1] can be written as follows,

where 0<ωpb<ωsb<π0<ωpb<ωsb<π. From a traditional standpoint this formulation feels familiar. It assigns fixed frequencies to the transition band edges as a number of filter design techniques do. As it turns out, however, one might not want to do this in CLS design.

An alternate formulation to Equation 2 could implicitly introduce a transition frequency ωtbωtb (where ωpb<ωtb<ωsbωpb<ωtb<ωsb); the user only specifies ωtbωtb. Consider

The algorithm at each iteration generates an induced transition band in order to satisfy the constraints in Equation 3. Therefore {ωpb,ωsb}{ωpb,ωsb} vary at each iteration.

Figure 1: Two formulations for Constrained Least Squares problems.

It is critical to point out the differences between Equation 2 and Equation 3. Figure 1.a explains Adams' CLS formulation, where the desired filter response is only specified at the fixed pass and stop bands. At any iteration, Adams' method attempts to minimize the least squares error (ε2ε2) at both bands while trying to satisfy the constraint ττ. Note that one could think of the constraint requirements in terms of the Chebishev error ε∞ε∞ by writing Equation 2 as follows,

In contrast, Figure 1.b illustrates our proposed problem Equation 3. The idea is to minimize the least squared error ε2ε2 across all frequencies while ensuring that constraints are met in an intelligent manner. At this point one can think of the interval (ωpb,ωsb)(ωpb,ωsb) as an induced transition band, useful for the purposes of constraining the filter. Section 2 presents the actual algorithms that solve Equation 3, including the process of finding {ωpb,ωsb}{ωpb,ωsb}.

It is important to note an interesting behavior of transition bands and extrema points in l2l2 and l∞l∞ filters. Figure 2 shows l2l2 and l∞l∞ length-15 linear phase filters (designed using Matlab's firls and firpm functions); the transition band was specified at {ωpb=0.4/π,ωsb=0.5/π}{ωpb=0.4/π,ωsb=0.5/π}. The dotted l2l2 filter illustrates an important behavior of least squares filters: typically the maximum error of an l2l2 filter is located at the transition band. The solid l∞l∞ filter shows why minimax filters are important: despite their larger error across most of the bands, the filter shows the same maximum error at all extrema points, including the transition band edge frequencies. In a CLS problem then, typically an algorithm will attempt to reduce iteratively the maximum error (usually located around the transition band) of a series of least squares filters.

Figure 2: Comparison of l2l2 and l∞l∞ filters.

Another important fact results from the relationship between the transition band width and the resulting error amplitude in l∞l∞ filters. Figure 3 shows two l∞l∞ designs; the transition bands were set at {0.4/π,0.5/π}{0.4/π,0.5/π} for the solid line design, and at {0.4/π,0.6/π}{0.4/π,0.6/π} for the dotted line one. One can see that by widening the transition band a decrease in error ripple amplitude is induced.

Figure 3: Effects of transition bands in l∞l∞ filters.

These two results together illustrate the importance of the transition bandwidth for a CLS design. Clearly one can decrease maximum error tolerances by widening the transition band. Yet finding the perfect balance between a transition bandwidth and a given tolerance can prove a difficult task, as will be shown in Section 2. Hence the relevance of a CLS method that is not restricted by two types of specifications competing against each other. In principle, one should just determine how much error one can live with, and allow an algorithm to find the optimal transition band that meets such tolerance.

Section 1 introduced some important remarks regarding the behavior of extrema points and transition bands in l2l2 and l∞l∞ filters. As one increases the constraints on an l2l2 filter, the result is a filter whose frequency response looks more and more like an l∞l∞ filter.

(Reference) introduced the frequency-varying problem and an IRLS-based method to solve it. It was also mentioned that, while the method does not solve the intended problem (but a similar one), it could prove to be useful for the CLS problem. As it turns out, in CLS design one is merely interested in solving an unweighted, constrained least squares problem. In this work, we achieve this by solving a sequence of weighted, unconstrained least squares problems, where the sole role of the weights is to "constraint" the maximum error of the frequency response at each iteration. In other words, one would like to find weights ww such that

is equivalent to

Hence one can revisit the frequency-varying design method and use it to solve the CLS problem. Assuming that one can reasonably approximate l∞l∞ by using high values of pp, at each iteration the main idea is to use an lplp weighting function only at frequencies where the constraints are exceeded. A formal formulation of this statement is

Assuming a suitable weighting function existed such that the specified tolerances are related to the frequency response constraints, the IRLS method would iterate and assign rather large weights to frequencies exceeding the constraints, while inactive frequencies get a weight of one. As the method iterates, frequencies with large errors move the response closer to the desired tolerance. Ideally, all the active constraint frequencies would eventually meet the constraints. Therefore the task becomes to find a suitable weighting function that penalizes large errors in order to have all the frequencies satisfying the constraints; once this condition is met, we have reached the desired solution.

Figure 4: CLS polynomial weighting function.

One proposed way to find adequate weights to meet constraints is given by a polynomial weighting function of the form

where ττ effectively serves as a threshold to determine whether a weight is dominated by either unity or the familiar lplp weighting term. Figure 4 illustrates the behavior of such a curve.

Figure 5: Original l2l2 guess for CLS algorithm.

Figure 6: CLS design example using mild constraints.

Figure 7: CLS design example using tight constraints.

Figure 8: CLS design example without transition bands.

In practice the method outlined above has proven robust particularly in connection with the specified transition band design. Consider the least squares design in Figure 5 (using a length-21 Type-I linear phase low-pass FIR filter with linear transition frequencies {0.2,0.25}{0.2,0.25}). This example illustrates the typical effect of CLS methods over l2l2 designs; the largest error (in an l∞l∞ sense) can be located at the edges of the transition band. Figures Figure 6 and Figure 7 illustrate design examples using the proposed approach. Figure 6 shows an example of a mild constraint (τ=0.6τ=0.6), whereas Figure 7 illustrates an advantage of this method, associated to a hard constraint (τ=0.3τ=0.3). The method is trying iteratively to reduce the maximum error towards the constraint; however the specified constraint in Figure 7 is such that even at the point where an equiripple response is reached for the specified transition bands the constraint is not met. At this point the method converges to an optimal lplp solution that approximates equiripple as pp increases (the examples provided use p=50p=50).

A different behavior occurs when no transition bands are defined. Departing from an initial l2l2 guess (as shown in Figure 8.a) the proposed IRLS-based CLS algorithm begins weighting frequencies selectively in order to reduce the l∞l∞ error towards the constraints ττ at each iteration. Eventually an equiripple behavior can be observed if the constraints are too harsh (as in Figure 8.b). The algorithm will keep weighting until all frequencies meet the constraints (as in Figure 8.c). The absence of a specified transition band presents some ambiguity in defining valid frequencies for weighting. One cannot (or rather should not) apply weights too close to the transition frequency specified as this would result in an effort by the algorithm to create a steep transition region (which as mentioned previously is counterintuitive to finding an equiripple solution). In a sense, this would mean having two opposite effects working at the same time and the algorithm cannot accommodate both, usually leading to numerical problems.

Figure 9: Definition of induced transition band.

In order to avoid these issues, an algorithm can be devised that selects a subset of the sampled frequencies for weighting purposes at each iteration. The idea is to identify the largest ripple per band at each iteration (the ripple associated with the largest error for a given band) and select the frequencies within that band with errors equal or smaller than such ripple error. In this way one avoids weighting frequencies around the transition frequency. This idea is illustrated in Figure 9.

Figure 10: CLS weights.

The previous example is fundamental since it illustrates the relevance of this method: since for a particular transition band the tightest constraint that one can get is given by the equiripple (or minimax) design (as shown in Section 1), a problem might arise when specifications are tighter than what the minimax design can meet. Adams found this problem (as reported in [1]); his method breaks under these conditions. The method proposed here overcomes an inadequate constraint and relaxes the transition band to meet the constraint.

It is worth noting that the polynomial weighting form works even when no transition bands are specified (this must become evident from Figure 8.c above). However, the user must be aware of some practical issues related to this approach. Figure 10 shows a typical CLS polynomial weighting function. Its "spiky" character becomes more dramatic as pp increases (the method still follows the homotopy and partial updating ideas from previous sections) as shown in Figure 10.b. It must be evident that the algorithm will assign heavy weights to frequencies with large errors, but at pp increases the difference in weighting exaggerates. At some point the user must make sure that proper sampling is done to ensure that frequencies with large weights (from a theoretical perspective) are being included in the problem, without compromising conputational efficiency (by means of massive oversampling, which can lead to ill-conditioning in numerical least squares methods). Also as pp increases, the range of frequencies with signifficantly large weights becomes narrower, thus reducing the overall weighting effect and affecting convergence speed.

Figure 11: CLS envelope weighting function.

A second weighting form can be defined where envelopes are used. The envelope weighting function approach works by assigning a weight to all frequencies not meeting a constraint. The value of such weights are assigned as flat intervals as illustrated in Figure 11. Intervals are determined by the edge frequencies within neighborhoods around peak error frequencies for which constraints are not met. Clearly these neighborhoods could change at each iteration. The weight of the kk-th interval is still determined by our typical expression,

where ωk+ωk+ is the frequency with largest error within the kk-th interval.

Envelope weighting has been applied in practice with good results. It is particularly effective at reaching high values of pp without ill-conditioning, allowing for a true alternative to minimax design. Figure 12 shows an example using τ=0.4τ=0.4; the algorithm managed to find a solution for p=500p=500. By specifying transition bands and unachievable constraints one can produce an almost equiripple solution in an efficient manner, with the added flexibility that milder constraints will result in CLS designs.

Figure 12: CLS design example using envelope weights.

This chapter presented two problems with similar effects. On one hand, (Reference) illustrated the fact (see (Reference)) that as pp increases towards infinity, an lplp filter will approximate an l∞l∞ one. On the other hand, (Reference) presented the constrained least squared problem, and introduced IRLS-based algorithms that produce filters that approximate equiripple behavior as the constraint specifications tighten.

A natural question arises: how do these methods compare with each other? In principle it should be possible to compare their performances, as long as the necessary assumptions about the problem to be solved are compatible in both methods. Figure 13 shows a comparison of these algorithms with the following specifications:

Some conclusions can be derived from Figure 13. Even though at the extremes of the curves they both seem to meet, the CLS curve lies just below the lplp curve for most values of pp and ττ. These two facts should be expected: on one hand, in principle the CLS algorithm gives an l2l2 filter if the constraints are so mild that they are not active for any frequency after the first iteration (hence the two curves should match around p=2p=2). On the other hand, once the constraints become too harsh, the fixed transition band CLS method basically should design an equiripple filter, as only the active constraint frequencies are lplp-weighted (this effects is more noticeable with higher values of pp). Therefore for tight constraints the CLS filter should approximate an l∞l∞ filter.

The reason why the CLS curve lies under the lplp curve is because for a given error tolerance (which could be interpreted as for a given minimax error

It is important to note that both curves are not drastically different. While the CLS curve represents optimality in an l2-l∞l2-l∞ sense, not all the problems mentioned in this work can be solved using CLS filters (for example, the magnitude IIR problem presented in (Reference)). Also, one of the objectives of this work is to motivate the use of lplp norms for filter design problems, and the proposed CLS implementations (which absolutely depends on IRLS-based lplp formulations) are good examples of the flexibility and value of lplp IRLS methods discussed in this work.

Figure 13: Comparison between CLS and lplp problems.