Remez Exchange Algorithm
The Remez multiple exchange algorithm works by moving the frequency samples each iteration to points of maximum error (on a denser grid). Remez iterations could be added to our formulation as well. The Remez multiple exchange algorithm (function firpm [formerly remez] in the 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:
![]() |
(4.76) |
where




Convergence of Remez Exchange
According to a theorem of Remez,
is guaranteed to
increase monotonically each iteration, ultimately converging to
its optimal value. This value is reached when all the extremal
frequencies are found. In practice, numerical round-off error may
cause
not to increase monotonically. When this is detected,
the algorithm normally halts and reports a failure to converge.
Convergence failure is common in practice for 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 [22].
Next Section:
Monotonicity Constraint
Previous Section:
LP Standard Form