1
$\begingroup$

I've got a set of $m \in \mathbb{N}$ 2D points which I want to represent as a polynomial of degree $n$: $\left \{ \left( x_i, y_i \right) \in \mathbb{R}^2 : i \in \mathbb{Z}, 0 \leq i \lt m \right \}$, with $x_i - x_{i - 1} = d$ being constant. These points happen to be values of a univariate real function, like so: $f(x_i) = y_i$; so one could say that I'm approximating that function with a polynomial, but I only care about the values on the equidistant $x_i$, not on the entire interval $[x_0, x_{m - 1}]$.

I want to find a polynomial that minimizes the maximal error, so my error function is such: $\max_{0 \leq i \lt m} \lvert y_i - p(x_i) \rvert$.

So far I know of two methods of finding "best" polynomials:

  1. The minimax polynomial has minimal error over an entire interval, not just some select points. I already verified that the Remez algorithm leads to suboptimal polynomials for my problem.
  2. Polynomial regression also produces a best polynomial, but I don't know what's the definition of the error that polynomial regression minimizes.

What method should I use for finding my polynomials?

EDIT: This question seems to be related, however it's specifically about the case $n = 1$, so I'm not sure how much it applies to the case of polynomials in general: Linear regression for minimizing the maximum of the residuals

$\endgroup$
5
  • $\begingroup$ The most common error (loss function) used in (discrete) polynomial regression is $\sum_{i=1}^n(y_i-p(x_i))^2$, in which $p(x)$ is a polynomial. $\endgroup$ Mar 30, 2022 at 12:12
  • $\begingroup$ Yeah, I'm not interested in least squares, I want to minimize the maximal error. Similar to this: en.wikipedia.org/wiki/L-infinity $\endgroup$ Mar 30, 2022 at 12:15
  • 1
    $\begingroup$ This link you include in your "EDIT" seems to provide a method to solve your problem, if you note that the constraints $x_{i}-x_{i-1}=d$ is in your data. $\endgroup$ Mar 30, 2022 at 12:34
  • $\begingroup$ @JoséCFerreira I think there's an important difference: that answer is about linear functions instead of polynomials with possibly greater degrees, so it admits a linear programming solution. So I'm still not sure what's the best solution for my problem. $\endgroup$ Mar 30, 2022 at 12:49
  • 2
    $\begingroup$ Linearity is in the parameters $a_i$ you want to find in $p(x)=\sum_{i=1}^ma_ix^i$, and not in $x$. $\endgroup$ Mar 30, 2022 at 13:01

1 Answer 1

1
$\begingroup$

The method in this link suggest you the minimization problem $$\left\{\begin{array}{rl} \min& r\\\\\text{subject to} & r-(y_i-p(x_i))\geq 0\\& r+(y_i-p(x_i))\geq 0 \end{array}\right.$$ by using the modulus definition, in which $$p(x)=\sum_{i=1}^ma_ix^i.$$

You can find some discussions by looking for linear programming minimizers on SearchOnMath. I like to use this tool to solve linear programming minimizers.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .