I need to fit a low-degree polynomial $p$ (with $\text{deg}(p) \leq k$) to a function $f$ evaluated on the grid $\{0, 1, ... n-1\}$, so as to minimize the $L_\infty$ norm, i.e. minimize $\text{max}_{0 \leq i < n}{\left| f(i) - p(i) \right|}$.
Now, I know that for $L_2$, this can be solved using a system of linear equations (for getting a zero vector as the derivative of the error) - that is the "Least Squares" method. But - the $L_\infty$ error is not a derivable function. I also know that for a continuous interval rather than a finite grid, there's an iterative approximation algorithm - the Remez Algorithm (although I'm not entirely clear about the specifics - I just noticed it.) And I also had a vague hunch which I didn't manage to act on that Chebychev polynomials, each of which being the optimal solution to the problem with $f = 0$ and a fixed leading coefficient 1, might be relevant here somehow.
Anyway, what I'd like to know is:
- Is this problem is essentially combinatorial or essentially numero-analytic?
- Can it be solved in PTIME (assuming operations on real values are O(1))?
- If so, what's the numerical stability features of such a solution (since my n is large-ish)?
- If not, does it admit an efficient (PTIME) approximation scheme?
- If not, how do people deal with it in practice?