Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Discrete piecewise monotonic approximation by a strictly convex distance function

Author: I. C. Demetriou
Journal: Math. Comp. 64 (1995), 157-180
MSC: Primary 65D10; Secondary 41A29
MathSciNet review: 1270617
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Theory and algorithms are presented for the following smoothing problem. We are given n measurements of a real-valued function that have been altered by random errors caused by the deriving process. For a given integer k, some efficient algorithms are developed that approximate the data by minimizing the sum of strictly convex functions of the errors in such a way that the approximated values are made up of at most k monotonic sections. If $ k = 1$, then the problem can be solved by a special strictly convex programming calculation. If $ k > 1$, then there are $ O({n^k})$ possible choices of the monotonic sections, so that it is impossible to test each one separately. A characterization theorem is derived that allows dynamic programming to be used for dividing the data into optimal disjoint sections of adjacent data, where each section requires a single monotonic calculation. It is remarkable that the theorem reduces the work for a global minimum to $ O(n)$ monotonic calculations to subranges of data and $ O(k{s^2})$ computer operations, where $ s - 2$ is the number of sign changes in the sequence of the first divided differences of the data. Further, certain monotonicity properties of the extrema of best approximations with k and $ k - 1$, and with k and $ k - 2$ monotonic sections make the calculation quite efficient. A Fortran 77 program has been written and some numerical results illustrate the performance of the smoothing technique in a variety of data sets.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65D10, 41A29

Retrieve articles in all journals with MSC: 65D10, 41A29

Additional Information

Keywords: Data smoothing, piecewise monotonic approximation, isotonic, distance function, dynamic programming
Article copyright: © Copyright 1995 American Mathematical Society

American Mathematical Society