A Decomposition Theorem for the Least Squares Piecewise Monotonic Data Approximation Problem

We consider the problem of calculating the least squares approximation to n measurements that contain random errors of function values subject to the condition that the first differences of the approximated values have at most k − 1 sign changes, where k is a given positive integer. The positions of the sign changes are integer variables whose optimal values are to be determined automatically. Since the number of trials of all possible combinations of positions in order to find an optimal one is of magnitude n k−1, it would not be practicable to consider each one separately. We give a characterization theorem which shows that the problem reduces to partitioning the data into at most k disjoint sets of adjacent data and solving a k = 1 problem for each set (monotonic approximation case). The important computational consequence of this theorem is that it allows dynamic programming to be applied for obtaining the partition and solving the whole problem in only a quadratic number of operations. However, shorter computation times in practice are confirmed by our numerical results. Further, an example is given, which shows that the time required by the dynamic programming method to locate optimally peaks when k = 50 in a NMR spectrum that consists of about 110,000 data points is less than a minute, but the number of trials of all possible combinations would be of magnitude 10250.