I'm looking for a way to project a vector (in this case a function on the real line) onto a basis for that space (in this case the set of N-degree polynomials over the domain of a closed interval) with respect to minimizing the L-infinity norm.

Another way you could phrase this is that I'm looking to find the polynomial of degree N which approximates a function with the smallest absolute value distance from that function on a given interval.

When looking to approximate the function using the L2 norm, it was pretty straightforward. I created an orthonormal basis of polynomials, and then I could simply take the dot product with each of these basis vectors to do the projection. But that minimized the mean squared error, which is not as important as the absolute value error for my purposes.

The problem with the L-Infinity norm is that you can't get an orthonormal basis.

I also tried looking at it as a minimization problem, with respect to partial derivatives of the coefficients, but because it involves an absolute value and boundary conditions, you end up with a whole bunch of corner cases, not to mention a larger and larger set of equations to solve for higher degree polynomials.

I've considered just using some machine learning technique to approximate the values, but that's nasty and I'm interested in the math behind it anyway.

EDIT:I have found out that what I am looking for is called the "minimax polynomial", but I'd still be interested in some of the math behind it.


Well, if the function you wish to approximate is the zero function on [-1,1], and you can't use the zero polynomial, then Chebyshev has your answer.

That is the only elegant, analytic result I am aware of. It sounds obscure, but it is very important for the analysis of Krylov subspace methods for solving $Ax = b$, e.g. conjugate gradients.

Then there's the Remez algorithm, which makes use of Chebyshev's Equioscillation Theorem.

| cite | improve this answer | |

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.