×

Separation theorems for the extrema of best piecewise monotonic approximations to successive data. (English) Zbl 1440.90093

Summary: Separation properties of the local extrema of best piecewise monotonic approximations to measurements of a real univariate function are of fundamental importance to the development of efficient algorithms that calculate these approximations. Piecewise monotonic approximation to \(n\) data is expressed as the minimization of some strictly convex function of the data errors subject to the restriction that the piecewise linear interpolant to the approximated values consists of at most \(k\) monotonic sections, where \(k\) is a prescribed positive integer. The major task is to determine automatically the positions of the joins of these sections, which is a combinatorial problem that can require about \(O(n^{k-1})\) combinations in order to find an optimal one. We state theorems which prove the remarkable property that the local maxima of optimal approximations with \(k -1\) monotonic sections are separated by the local maxima of optimal approximations with \(k\) monotonic sections, and local minima are separated similarly. We describe briefly a suitable technique that makes use of this property and gives the global solution in \(O(n^2 + kn \log_2 n)\) computer operations. Some numerical results show large gains in efficiency over existing methods. Further, as an illustration, we apply the technique to 39,082 observations of daily sunspots.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90C27 Combinatorial optimization

Software:

L2WPMA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Davies, L.; Höhenrieder, C.; Krämer, W., Recursive computation of piecewise constant volatilities, Comput. Stat., 11, 3623-3631 (2012) · Zbl 1254.91751
[2] Demetriou, I. C., Discrete piecewise monotonic approximation by a strictly convex distance function, Math. Comput., 64, 157-180 (1995) · Zbl 0824.41019 · doi:10.1090/S0025-5718-1995-1270617-X
[3] Demetriou, I. C., Algorithm 863: L2WPMA, a Fortran 77 package for weighted least-squares piecewise monotonic data approximation, ACM Trans. Math. Softw., 33, 1-19 (2007) · doi:10.1145/1206040.1206046
[4] Demetriou, I.C., Peak estimation of a spectrum from noisy measurements by least squares piecewise monotonic data approximation, in Lecture Notes in Engineering and Computer Science: Proceedings of The International Multiconference of Engineers and Computer Scientists 2018, S.I. Ao, O. Castillo, C. Douglas, D.D. Feng, and A.M. Korsunsky, eds., Hong Kong, 14-16 March, 2018, pp. 51-56.
[5] Demetriou, I. C.; Powell, M. J.D., Least squares smoothing of univariate data to achieve piecewise monotonicity, IMA J. Numer. Anal., 11, 411-432 (1991) · Zbl 0726.65008 · doi:10.1093/imanum/11.3.411
[6] Lazaropoulos, A. G., Best \(####\) piecewise monotonic data approximation in overhead and underground medium-voltage and low-voltage broadband over power lines networks: theoretical and practical transfer function determination, J. Comput. Eng., 6762390, 24 (2016) · doi:10.11.55/2016/6762390
[7] Lu, J., Signal restoration with controlled piecewise monotonicity constraint, in IEEE International Conference on Acoustics, Speech and Signal Processing, 3, Seattle, WA, 12-15 May 1998, pp. 1621-1624.
[8] Royset, J. O.; Wets, R. J.-B., On univariate function identification problems, Math. Programming, 168, 449-474 (2018) · Zbl 1395.90230 · doi:10.1007/s10107-017-1130-y
[9] Sauerland, V.; Löptien, U.; Leonhard, C.; Oschlies, A.; Srivastav, A., Error assessment of biogeochemical models by lower bound methods (NOMMA-1.0), Geosci. Model Dev., 11, 1181-1198 (2018) · doi:10.5194/gmd-11-1181-2018
[10] Scholkmann, F.; Boss, J.; Wolf, M., An efficient algorithm for automatic peak detection in noisy periodic and quasi-periodic signals, Algorithms, 5, 588-603 (2012) · Zbl 07042142 · doi:10.3390/a5040588
[11] Solanki, S. K., Sunspots: An overview, Astron. Astrophys. Rev., 11, 153-286 (2003) · doi:10.1007/s00159-003-0018-4
[12] Sunspot Index and Long-term Solar Observations (SILSO) of the Royal Observatory of Belgium. Available at http://www.sidc.be/silso/home, SILSO data/image, Royal Observatory of Belgium, Brussels, SN_d_tot_V2.0.xlsx (accessed on 5 January 2019).
[13] Weaver, J. B., Applications of monotonic noise reduction algorithms in fMRI, Phase estimation, and contrast enhancement, Int. J. Imaging Syst. Technol., 10, 177-185 (1999) · doi:10.1002/(SICI)1098-1098(1999)10:2<177::AID-IMA8>3.0.CO;2-8
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.