Window Design by Linear ProgrammingThis section, based on a class project by EE graduate student Tatsuki Kashitani, illustrates the use of linprog in Matlab for designing variations on the Chebyshev window (§3.10). In addition, some comparisons between standard linear programming and the Remez exchange algorithm (firpm) are noted.
Linear Programming (LP)If we can get our filter or window design problems in the form
where , , is , etc., then we are done. The linprog function in Matlab Optimization Toolbox solves LP problems. In Octave, one can use glpk instead (from the GNU GLPK library).
LP Formulation of Chebyshev Window DesignWhat we want:
- Symmetric zero-phase window.
- Window samples to be positive.
- Transform to be 1 at DC.
- Transform to be within
in the stop-band.
- And to be small.
zero-phase window, use only the positive-time part :
Stacking inequalities for all ,
DTFT at frequency is given by
By zero-phase symmetry,
So can be expressed as
side-lobe specification can be enforced at frequencies in the stop-band.
We need to obtain many frequency samples per side lobe. Stacking inequalities for all ,
where the optimization variables are . Solving this linear-programming problem should produce a window that is optimal in the Chebyshev sense over the chosen frequency samples, as shown in Fig.3.37. If the chosen frequency samples happen to include all of the extremal frequencies (frequencies of maximum error in the DTFT of the window), then the unique Chebyshev window for the specified main-lobe width must be obtained. Iterating to find the extremal frequencies is the heart of the Remez multiple exchange algorithm, discussed in the next section.
Matlab Signal Processing Toolbox, and still remez in Octave) is normally faster than a linear programming formulation, which can be regarded as a single exchange method [224, p. 140]. Another reason for the speed of firpm is that it solves the following equations non-iteratively for the filter exhibiting the desired error alternation over the current set of extremal frequencies:
where is the weighted ripple amplitude at frequency . ( is an arbitrary ripple weighting function.) Note that the desired frequency-response amplitude is also arbitrary at each frequency sample. FIR filters having more than 300 or so taps and stringent design specifications (such as very narrow pass-bands). Further details on Remez exchange are given in [224, p. 136]. As a result of the non-iterative internal LP solution on each iteration, firpm cannot be used when additional constraints are added, such as those to be discussed in the following sections. In such cases, a more general LP solver such as linprog must be used. Recent advances in convex optimization enable faster solution of much larger problems .
In matrix form,
norm of the derivative to the objective function.
The -norm only cares about the maximum derivative. Large means we put more weight on the smoothness than the side-lobe level. This can be formulated as an LP by adding one optimization parameter which bounds all derivatives.
In matrix form,
Objective function becomes
The result of adding the Chebyshev norm of diff(h) to the objective function to be minimized ( ) is shown in Fig.3.39. The result of increasing to 20 is shown in Fig.3.40.
norm of the derivative to the objective:
Note that the norm is sensitive to all the derivatives, not just the largest. We can formulate an LP problem by adding a vector of optimization parameters which bound derivatives:
In matrix form,
The objective function becomes
See Fig.3.41 and Fig.3.42 for example results.
spectrum-analysis windows made using linear-programming (linprog in matlab) or Remez multiple exchange algorithms (firpm in Matlab). After formulating the Chebyshev window as a linear programming problem, we found we could impose a monotonicity constraint on its shape in the time domain, or various derivative constraints. In Chapter 4, we will look at methods for FIR filter design, including the window method (§4.5) which designs FIR filters as a windowed ideal impulse response. The formulation introduced in this section can be used to design such windows, and it can be used to design optimal FIR filters. In such cases, the impulse response is designed directly (as the window was here) to minimize an error criterion subject to various equality and inequality constraints, as discussed above for window design.4.16
The Ideal Lowpass Filter