0
$\begingroup$

I'm reading up on the Remez algorithm(s), and my understanding is we are minimizing the maximum difference between the true and approximate function (over a certain interval) by iteratively changing the coefficients of the polynomial that approximates the function.

However, by doing so, don't we need the exact value of the function, for example at the control points? If so, then would that not defeat the purpose of the algorithm, since often times we approximate the function because we can't evaluate it directly?

Please let me know if my understanding is correct. Thank you.

$\endgroup$
0
$\begingroup$

Keep in mind that the Remez algorithm is a numerical procedure. So instead of a mathematical result (often a transcendental number and therefore not accurately representable in any finite-precision numeric format) only a sufficiently accurate reference is required.

As a consequence, in this context, the true function is commonly represented by a "golden" reference based on an arbitrary-precision library. For example, I typically configure my arbitrary-precision library of choice for 1024 bits to generate double-precision approximations.

Utilizing very high intermediate precision allows the use of straightforward, but numerically sub-optimal, mathematical formulas in the computation of the golden reference. It also alleviates issues with the at times extremely ill-conditioned systems of equations involved in the Remez algorithm. Since the performance of the golden reference is not important, one can also use slow-converging approximations extended to a very high number of terms, or numerical integration, which might be highly impractical in other contexts.

Even so, it can happen that the Remez algorithms fails to converge correctly due to numerical issues. A common case in my experience is when one tries to generate polynomial approximations with dozens of terms using a monomial base.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.