Discrete piecewise monotonic approximation by a strictly convex distance function
HTML articles powered by AMS MathViewer
- by I. C. Demetriou PDF
- Math. Comp. 64 (1995), 157-180 Request permission
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
- 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, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, London-New York-Sydney, 1972. MR 0326887 I. C. Demetriou, Data smoothing by piecewise monotonic divided differences, Ph.D. dissertation, University of Cambridge, England, 1985.
- I. C. Demetriou, A characterization theorem for the discrete best monotonic approximation problem, Math. Comp. 55 (1990), no. 191, 191–195. MR 1023046, DOI 10.1090/S0025-5718-1990-1023046-3 —, 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.
- 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, DOI 10.1093/imanum/11.3.411
- Garth P. McCormick, Nonlinear programming, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1983. Theory, algorithms, and applications. MR 693095
- 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
Additional Information
- © Copyright 1995 American Mathematical Society
- 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