### 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 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.

#### 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