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 (
nlsfunction) 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 L1 and L∞ norms”, by Shrager and Hill and “A linear programming algorithm for curve fitting in the L∞ 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
optimfunction 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.
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.