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.

  • $\begingroup$ 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. $\endgroup$ – Nick Mar 30 '12 at 16:02
  • $\begingroup$ Could this be done not with polynomials, but with functions of the form asin(bx), for instance? $\endgroup$ – Altfel Mar 31 '12 at 17:32
  • $\begingroup$ 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. $\endgroup$ – Nick Mar 31 '12 at 20:40

For those who may be interested, I have found a paper that proposes a solution to my problem: "A min-max algorithm for non-linear regression models", by A. Tishler and I. Zang.

I have tested it myself, and I get the results I need.


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.