Elsevier Science Home
Computer Physics Communications Program Library
Full text online from Science Direct
Programs in Physics & Physical Chemistry
CPC Home

[Licence| Download | New Version Template] adrf_v1_0.zip(66 Kbytes)
Manuscript Title: L1PMA: a Fortran 77 package for best L1 piecewise monotonic data smoothing.
Authors: I.C. Demetriou
Program title: L1PMA
Catalogue identifier: ADRF_v1_0
Distribution format: zip
Journal reference: Comput. Phys. Commun. 151(2003)315
Programming language: Fortran.
Computer: PC Intel Pentium.
Operating system: Windows 98, Windows NT.
Word size: 8
Keywords: Approximation, Data fitting, Divided difference, Dynamic programming, L1 norm, Least absolute deviation, Median, Noise, Peak, Piecewise monotonicity, Smoothing, Turning point, Computational methods.
Classification: 4.9.

Nature of problem:
  • Univariate measurements of an unknown function that contains random errors.
  • Identifying turning points (peakfinding) of a univariate function from noisy measurements of its values.

Solution method:
Data smoothing by minimizing the sum of the absolute values of the errors (best L1 approximation) subject to the condition that the first order divided differences of the smoothed values change sign a prescribed number of times, q say. The smoothed values consist of q+1 monotonic sections, alternately increasing and decreasing, where the optimal turning points are found automatically. In L1 approximation, generally, some gross errors in the data due to outliers are ignored.

Restrictions:
Number of data, n, is not limited in the software package, but is limited to 2000 in the main driver. Complexity of the problem is n**3+O(kn**2).

Unusual features:
Summary
A best L1 piecewise monotonic approximation to n measurements that include random errors is calculated. If k is the number of the monotonic sections, then this calculation can exhibit O(n**k) local minima, because the optimal positions of the turning points are also unknown of the optimization process. However, a dynamic programming algorithm separates the measurements into optimal disjoint sections of adjacent data and applies to each section a single L1 monotonic calculation. The most distinctive feature of the algorithm is that it terminates at a global minimum in at most n**3+O(kn**2) computer operations. The arithmetic operations involved in this calculation are comparisons mainly spent in finding the medians of subranges of data during the monotonic calculations. The software package employs techniques for median and for best L1 monotonic approximation, while full details of these techniques are specified. The package has been applied and tested on a variety of data having substantial differences showing quadratic behavior in n. Some numerical results demonstrate the performance of the method. Further, there is a commentary on the division of the code into subroutines. Driver programs and numerical examples with output are provided to help new users of the method. Besides that piecewise monotonicity is a property of a wide range of functions, an important application of the method is in estimating turning points of a function from some noisy measurements of its value.

Additional comments:
Memory required: O(n), where n is the number of data.

Running time:
CPU time on a PC with an Intel 90 MHz processor operating in Windows 98: About 40 seconds to smooth n=1000 very noisy measurements by requiring up to 15 monotonic sections. For less noisy measurements, the same calculation required about 20 seconds.