Least Squares Smoothing of Univariate Data to achieve Piecewise Monotonicity

If measurements of a univariate function include uncorrelatederrors, then it is usual for the first-order divided differencesof the measurements to show far more sign changes than the correspondingdifferences of the underlying function. Therefore we addressthe problem of making the least sum of squares change to thedata so that the piecewise linear interpolant to the smootheddata is composed of at most k monotonic sections, k being aprescribed positive integer. The positions of the joins of thesections are integer variables whose optimal values are determinedautomatically, which is a combinatorial problem that can haveO(n^k) local minima, where n is the number of data. Fortunatelywe find that a dynamic programming procedure can calculate theglobal minimum of the sum of squares in at most O(n² + kn logn) computer operations. Further, the complexity reduces to onlyO(n) when k = 1 or k = 2, this result being well known in themonotonic case (k = 1). Algorithms that achieve these efficienciesare described. They perform well in practice, but a discussionof complexity suggests that there is still room for improvementwhen k 3.