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

DOI:
https://doi.org/10.1090/S0025-5718-1995-1270617-X

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 , then the problem can be solved by a special strictly convex programming calculation. If , then there are 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 monotonic calculations to subranges of data and computer operations, where 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 , and with *k* and 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.

**[1]**R. E. Barlow, D. J. Bartholomew, J. M. Bremner, and H. D. Brunk,*Statistical inference under order restrictions. The theory and application of isotonic regression*, John Wiley & Sons, London-New York-Sydney, 1972. Wiley Series in Probability and Mathematical Statistics. MR**0326887****[2]**I. C. Demetriou,*Data smoothing by piecewise monotonic divided differences*, Ph.D. dissertation, University of Cambridge, England, 1985.**[3]**I. C. Demetriou,*A characterization theorem for the discrete best monotonic approximation problem*, Math. Comp.**55**(1990), no. 191, 191–195. MR**1023046**, https://doi.org/10.1090/S0025-5718-1990-1023046-3**[4]**-,*L2PMA*:*Fortran*77*subroutines for least squares piecewise monotonic data fitting*, Report of the University of Athens, Dept. of Economic Sciences, ICD-93-2, Greece, 1993.**[5]**I. C. Demetriou and M. J. D. Powell,*Least squares smoothing of univariate data to achieve piecewise monotonicity*, IMA J. Numer. Anal.**11**(1991), no. 3, 411–432. MR**1118965**, https://doi.org/10.1093/imanum/11.3.411**[6]**Garth P. McCormick,*Nonlinear programming*, John Wiley & Sons, Inc., New York, 1983. Theory, algorithms, and applications; A Wiley-Interscience Publication. MR**693095****[7]**Tim Robertson, F. T. Wright, and R. L. Dykstra,*Order restricted statistical inference*, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1988. MR**961262**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1995-1270617-X

Keywords:
Data smoothing,
piecewise monotonic approximation,
isotonic,
distance function,
dynamic programming

Article copyright:
© Copyright 1995
American Mathematical Society