A binary search algorithm for univariate data approximation and estimation of extrema by piecewise monotonic constraints

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

Journal of Global Optimization, 2022, vol. 82, issue 4, No 3, 726 pages

Abstract: Abstract The piecewise monotonic approximation problem makes the least changes to n univariate noisy data so that the piecewise linear interpolant to the new values is composed of at most k monotonic sections. The term “least changes” is defined in the sense of a global sum of strictly convex functions of changes. The main difficulty in this calculation is that the extrema of the interpolant have to be found automatically, but the number of all possible combinations of extrema can be $${\mathcal {O}}(n^{k-1})$$ O ( n k - 1 ) , which makes not practicable to test each one separately. It is known that the case $$k=1$$ k = 1 is straightforward, and that the case $$k>1$$ k > 1 reduces to partitioning the data into at most k disjoint sets of adjacent data and solving a $$k=1$$ k = 1 problem for each set. Some ordering relations of the extrema are studied that establish three quite efficient algorithms by using a binary search method for partitioning the data. In the least squares case the total work is only $${\mathcal {O}}(n \sigma +k\sigma \log _2\sigma )$$ O ( n σ + k σ log 2 σ ) computer operations when $$k \ge 3$$ k ≥ 3 and is only $${\mathcal {O}}(n)$$ O ( n ) when $$k=1$$ k = 1 or 2, where $$\sigma -2$$ σ - 2 is the number of sign changes in the sequence of the first differences of the data. Fortran software has been written for this case and the numerical results indicate superior performance to existing algorithms. Some examples with real data illustrate the method. Many applications of the method arise from bioinformatics, energy, geophysics, medical imaging, and peak finding in spectroscopy, for instance.

Keywords: Algorithm; Approximation; Binary search; Combinatorial problem; Data smoothing; Divided difference; Dynamic programming; Fortran; Least squares; Monotonic fit; Peak finding; Piecewise monotonicity; Raman spectra; Spectroscopy; Sunspots; Unemployment data; 41A29; 65D10; 65K05; 65Y20 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-021-01042-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jglopt:v:82:y:2022:i:4:d:10.1007_s10898-021-01042-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-021-01042-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().