Piecewise Convex-Concave Approximation in the ` ∞ Norm

Suppose that f ∈ IRn is a vector of n error-contaminated measure-ments of n smooth values measured at distinct and strictly ascending abscissae. The following projective technique is proposed for obtaining a vector of smooth approximations to these values. Find y minimizing ‖y − f‖ ∞ subject to the constraints that the second order consecutive divided differences of the components of y change sign at most q times. This optimization problem (which is also of general geometrical inter-est) does not suffer from the disadvantage of the existence of purely local minima and allows a solution to be constructed in O(nq) opera-tions. A new algorithm for doing this is developed and its effectiveness is proved. Some of the results of applying it to undulating and peaky data are presented, showing that it is economical and can give very good results, particularly for large densely-packed data, even when the errors are quite large. 1