PROGRAM SUMMARY
Title of program:
L1PMA
Catalogue identifier:
ADRF
Ref. in CPC:
151(2003)315
Distribution format: zip file
Operating system: Windows 98, Windows NT
Number of bits in a word:
8
Number of lines in distributed program, including test data, etc:
6636
Keywords:
Approximation, Data fitting, Divided difference, Dynamic programming,
L1 norm, Least absolute deviation, Median, Noise, Peak,
Piecewise monotonicity, Smoothing, Turning point,
Computational methods.
Programming language used: Fortran
Computer:
PC Intel Pentium .
Nature of physical 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.
Method of solution:
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).
Typical 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.
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.