{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:12:49Z","timestamp":1760145169663,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Research Foundation of Korea (NRF)","award":["NRF-2020R1A2C1010891"],"award-info":[{"award-number":["NRF-2020R1A2C1010891"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In this paper, the optimal approximation algorithm is proposed to simplify non-linear functions and\/or discrete data as piecewise polynomials by using the constrained least squares. In time-sensitive applications or in embedded systems with limited resources, the runtime of the approximate function is as crucial as its accuracy. The proposed algorithm searches for the optimal piecewise polynomial (OPP) with the minimum computational cost while ensuring that the error is below a specified threshold. This was accomplished by using smooth piecewise polynomials with optimal order and numbers of intervals. The computational cost only depended on polynomial complexity, i.e., the order and the number of intervals at runtime function call. In previous studies, the user had to decide one or all of the orders and the number of intervals. In contrast, the OPP approximation algorithm determines both of them. For the optimal approximation, computational costs for all the possible combinations of piecewise polynomials were calculated and tabulated in ascending order for the specific target CPU off-line. Each combination was optimized through constrained least squares and the random selection method for the given sample points. Afterward, whether the approximation error was below the predetermined value was examined. When the error was permissible, the combination was selected as the optimal approximation, or the next combination was examined. To verify the performance, several representative functions were examined and analyzed.<\/jats:p>","DOI":"10.3390\/s24123991","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T03:46:29Z","timestamp":1718855189000},"page":"3991","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Optimal Piecewise Polynomial Approximation for Minimum Computing Cost by Using Constrained Least Squares"],"prefix":"10.3390","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-4374-104X","authenticated-orcid":false,"given":"Jieun","family":"Song","sequence":"first","affiliation":[{"name":"Department of Electronic Engineering, Myongji University, Yongin 17058, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bumjoo","family":"Lee","sequence":"additional","affiliation":[{"name":"Department of Electronic Engineering, Myongji University, Yongin 17058, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"ref_1","unstructured":"Nygaard, R., and Haugland, D. (1998, January 15). Compressing ECG signals by piecewise polynomial approximation. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Seattle, WA, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1109\/LSP.2009.2025824","article-title":"Pitch contour stylization using an optimal piecewise polynomial approximation","volume":"16","author":"Ghosh","year":"2009","journal-title":"IEEE Signal Process. Lett."},{"key":"ref_3","unstructured":"Ravuri, S., and Ellis, D.P. (April, January 31). Stylization of pitch with syllable-based linear segments. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, Las Vegas, NV, USA."},{"key":"ref_4","unstructured":"Kim, J.B., and Kim, B.K. (2009, January 10\u201312). The Calibration for Error of Sensing using Smooth Least Square Fit with Regional Split (SLSFRS). Proceedings of the Korea Automatic Control Conference, Jeju Island, Republic of Korea."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Dong, N., and Roychowdhury, J. (2003, January 2\u20136). Piecewise polynomial nonlinear model reduction. Proceedings of the 40th Annual Design Automation Conference, Anaheim, CA, USA.","DOI":"10.1145\/775832.775957"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/0315-0860(74)90033-0","article-title":"Gergonne\u2019s 1815 paper on the design and analysis of polynomial regression experiments","volume":"1","author":"Stigler","year":"1974","journal-title":"Hist. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1145\/362248.362276","article-title":"Least squares piecewise cubic curve fitting","volume":"16","author":"Ferguson","year":"1973","journal-title":"Commun. ACM"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1109\/T-C.1974.224041","article-title":"Segmentation of plane curves","volume":"100","author":"Pavlidis","year":"1974","journal-title":"IEEE Trans. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"43764","DOI":"10.1109\/ACCESS.2020.2976494","article-title":"Fast piecewise polynomial fitting of time-series data for streaming computing","volume":"8","author":"Gao","year":"2020","journal-title":"IEEE Access"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"949","DOI":"10.2514\/1.G003618","article-title":"Piecewise polynomial modeling for control and analysis of aircraft dynamics beyond stall","volume":"42","author":"Cunis","year":"2019","journal-title":"J. Guid. Control Dyn."},{"key":"ref_11","first-page":"876862","article-title":"Models and Algorithms for Optimal Piecewise-Linear Function Approximation","volume":"2015","author":"Eduardo","year":"2015","journal-title":"Math. Probl. Eng."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Gr\u00fctzmacher, F., Beichler, B., Hein, A., Kirste, T., and Haubelt, C. (2018). Time and Memory Efficient Online Piecewise Linear Approximation of Sensor Signals. Sensors, 18.","DOI":"10.3390\/s18061672"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Marinov, M.B., Nikolov, N., Dimitrov, S., Todorov, T., Stoyanova, Y., and Nikolov, G.T. (2022). Linear Interval Approximation for Smart Sensors and IoT Devices. Sensors, 22.","DOI":"10.3390\/s22030949"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Warwicker, J.A., and Rebennack, S. (2024). Efficient continuous piecewise linear regression for linearising univariate non-linear functions. IISE Trans.","DOI":"10.1080\/24725854.2023.2299809"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.ejor.2023.11.017","article-title":"Piecewise linear approximation with minimum number of linear segments and minimum error: A fast approach to tighten and warm start the hierarchical mixed integer formulation","volume":"315","author":"Ploussard","year":"2024","journal-title":"Eur. J. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/j.neucom.2021.01.007","article-title":"Optimal function approximation with ReLU neural networks","volume":"435","author":"Liu","year":"2021","journal-title":"Neurocomputing"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1002\/oca.957","article-title":"An hp-adaptive pseudospectral method for solving optimal control problems","volume":"32","author":"Darby","year":"2011","journal-title":"Optim. Control Appl. Methods"},{"key":"ref_18","unstructured":"M.OWEN (2024, March 20). Cortex-M7 Instruction Cycle Counts, Timings, and Dual-Issue Combinations. Available online: https:\/\/www.quinapalus.com\/cm7cycles.html."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/24\/12\/3991\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T15:01:30Z","timestamp":1760108490000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/24\/12\/3991"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":18,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["s24123991"],"URL":"https:\/\/doi.org\/10.3390\/s24123991","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2024,6,20]]}}}