# Nonlinear regression / Curve fitting with L-infinity norm

I am looking into time series data compression at the moment.

The idea is to fit a curve on a time series of n points so that the maximum deviation of any of the points is not greater than a given threshold. In other words, none of the values that the curve takes at the points where the time series is defined should be "further away" than a certain threshold from the actual values.

Till now I have found out how to do nonlinear regression using the least squares estimation method in R (nls function) and other languages, but I haven't found any packages that implement nonlinear regression with the L-infinity norm.

I have found papers on "Non-linear curve fitting in the $L_1$ and $L_{\infty}$ norms", by Shrager and Hill and "A linear programming algorithm for curve fitting in the $L_{\infty}$ norm", by Armstrong and Sklar.

I could try to implement this in R for instance, but I first looking to see if this hasn't already been done and that I could maybe reuse it.

I have found a solution that I don't believe to be "very scientific": I use nonlinear least squares regression to find the starting values of the parameters which I subsequently use as starting points in the R optim function that minimizes the maximum deviation of the curve from the actual points.

The idea is to be able to find out if this type of curve-fitting is possible on a given time series sequence and to determine the parameters that allow it.

-
Function interpolation (in the form of Chebyshev or Bernstein polynomials) may be of interest to you. From Weierstrass’ Theorem, these approaches provide bounds on the L-infinity error of any function over a closed interval. –  Nick Mar 30 '12 at 16:02
Could this be done not with polynomials, but with functions of the form a*sin(b*x), for instance? –  Altfel Mar 31 '12 at 17:32
I only mention the work on polynomial interpolation because I have some experience with it. I THINK the specific type of function you choose is not important as long as the basis functions are orthogonal. Sorry I can't be more help. –  Nick Mar 31 '12 at 20:40