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

Ioannis C. Demetriou ()
Additional contact information
Ioannis C. Demetriou: University of Athens

A chapter in Approximation and Optimization, 2019, pp 119-134 from Springer

Abstract: Abstract 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.

Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (2)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-030-12767-1_7

Ordering information: This item can be ordered from
http://www.springer.com/9783030127671

DOI: 10.1007/978-3-030-12767-1_7

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().