Least Squares Smoothing of Univariate Data to achieve Piecewise Monotonicity

• Published in: IMA journal of numerical analysis 1991-07, Vol.11 (3), p.411-432
• Main Authors: DEMETRIOU, I. C., POWELL, M. J. D.
• Format: Article
• Language: English
• Subjects: Exact sciences and technology; Mathematics; Numerical analysis; Numerical analysis. Scientific computation; Sciences and techniques of general use
• ISSN: 0272-4979; 1464-3642
• DOI: 10.1093/imanum/11.3.411

If measurements of a univariate function include uncorrelated errors, then it is usual for the first-order divided differences of the measurements to show far more sign changes than the corresponding differences of the underlying function. Therefore we address the problem of making the least sum of squares change to the data so that the piecewise linear interpolant to the smoothed data is composed of at most k monotonic sections, k being a prescribed positive integer. The positions of the joins of the sections are integer variables whose optimal values are determined automatically, which is a combinatorial problem that can have O(nk) local minima, where n is the number of data. Fortunately we find that a dynamic programming procedure can calculate the global minimum of the sum of squares in at most O(n2 + kn log n) computer operations. Further, the complexity reduces to only O(n) when k = 1 or k = 2, this result being well known in the monotonic case (k = 1). Algorithms that achieve these efficiencies are described. They perform well in practice, but a discussion of complexity suggests that there is still room for improvement when k ≽ 3.