# Projecting onto vector space with L-Infinity norm/ minimum absolute value polynomial fitting

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.

-

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.