Convergence of Remez Exchange

Chapter Contents:

Search Spectral Audio Signal Processing

Book Index | Global Index

Would you like to be notified by email when Julius Orion Smith III publishes a new entry into his blog?

In theory, $\delta$ 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 $\delta$ not to increase monotonically. When this is detected, the algorithm 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 cite[p. 136]RabinerAndGold.
As a result of the non-iterative internal LP solution on each iteration, remez 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 [21].

Previous: Remez Exchange Algorithm
Next: Monotonicity Constraint

About the Author: Julius Orion Smith III
Julius Smith's background is in electrical engineering (BS Rice 1975, PhD Stanford 1983). He is presently Professor of Music and Associate Professor (by courtesy) of Electrical Engineering at Stanford's Center for Computer Research in Music and Acoustics (CCRMA), teaching courses and pursuing research related to signal processing applied to music and audio systems. See http://ccrma.stanford.edu/~jos/ for details.

Sign in