Discrete piecewise monotonic approximation by a strictly convex distance function
Author:
I. C. Demetriou
Journal:
Math. Comp. 64 (1995), 157180
MSC:
Primary 65D10; Secondary 41A29
MathSciNet review:
1270617
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Theory and algorithms are presented for the following smoothing problem. We are given n measurements of a realvalued 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,
LondonNew YorkSydney, 1972. Wiley Series in Probability and Mathematical
Statistics. MR
0326887 (48 #5229)
 [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
(91h:65030), http://dx.doi.org/10.1090/S00255718199010230463
 [4]
, L2PMA: Fortran 77 subroutines for least squares piecewise monotonic data fitting, Report of the University of Athens, Dept. of Economic Sciences, ICD932, 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
(92f:65021), http://dx.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
WileyInterscience Publication. MR 693095
(84i:90131)
 [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
(90b:62001)
 [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, Wiley, Chichester, 1980. MR 0326887 (48:5229)
 [2]
 I. C. Demetriou, Data smoothing by piecewise monotonic divided differences, Ph.D. dissertation, University of Cambridge, England, 1985.
 [3]
 , A characterization theorem for the discrete best monotonic approximation problem, Math. Comp. 55 (1990), 191195. MR 1023046 (91h:65030)
 [4]
 , L2PMA: Fortran 77 subroutines for least squares piecewise monotonic data fitting, Report of the University of Athens, Dept. of Economic Sciences, ICD932, 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), 411432. MR 1118965 (92f:65021)
 [6]
 G. P. McCormick, Nonlinear programming. Theory and applications, Wiley, New York, 1983. MR 693095 (84i:90131)
 [7]
 T. Robertson, F. T. Wright, and R. L. Dykstra, Order restricted statistical inference, Wiley, Chichester, 1988. MR 961262 (90b:62001)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65D10,
41A29
Retrieve articles in all journals
with MSC:
65D10,
41A29
Additional Information
DOI:
http://dx.doi.org/10.1090/S0025571819951270617X
PII:
S 00255718(1995)1270617X
Keywords:
Data smoothing,
piecewise monotonic approximation,
isotonic,
distance function,
dynamic programming
Article copyright:
© Copyright 1995
American Mathematical Society
