Separation theorems for the extrema of best piecewise monotonic approximations to successive data. (3rd May 2020)

• Record Type: Journal Article
• Authors: Demetriou, I. C.
• Is Part Of: Optimization methods and software. Volume 35:Number 3(2020)
• Page Start: 439
• Page End: 459
• Publication Date: 2020-05-03
• Subjects: Approximation -- data smoothing -- divided difference -- extremum -- monotonic -- peakfinding -- piecewise monotonic -- sunspots -- turning point; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1613653
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: Separation properties of the local extrema of best piecewise monotonic approximations to measurements of a real univariate function are of fundamental importance to the development of efficient algorithms that calculate these approximations. Piecewise monotonic approximation to n data is expressed as the minimization of some strictly convex function of the data errors subject to the restriction that the piecewise linear interpolant to the approximated values consists of at most k monotonic sections, where k is a prescribed positive integer. The major task is to determine automatically the positions of the joins of these sections, which is a combinatorial problem that can require about O ( n k − 1 ) combinations in order to find an optimal one. We state theorems which prove the remarkable property that the local maxima of optimal approximations with k −1 monotonic sections are separated by the local maxima of optimal approximations with k monotonic sections, and local minima are separated similarly. We describe briefly a suitable technique that makes use of this property and gives the global solution in O ( n 2 + k n log 2 ⁡ n ) computer operations. Some numerical results show large gains in efficiency over existing methods. Further, as an illustration, we apply the technique to 39, 082 observations of daily sunspots.