PDF(Pubmed)
Abstract：
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.
摘要：
在本文中,提出了利用约束最小二乘将非线性函数和/或离散数据简化为分段多项式的最优逼近算法。在对时间敏感的应用程序或资源有限的嵌入式系统中，近似函数的运行时间与其准确性一样重要。所提出的算法在确保误差低于指定阈值的同时，以最小的计算成本搜索最佳分段多项式（OPP）。这是通过使用具有最佳顺序和间隔数的平滑分段多项式来实现的。计算成本仅取决于多项式复杂度，即，运行时函数调用的顺序和间隔数。在以往的研究中,用户必须决定一个或所有的订单和间隔的数量。相比之下,OPP近似算法决定了两者。对于最佳逼近，对于特定的目标CPU离线，按升序计算了所有可能的分段多项式组合的计算成本，并将其制成表格。对于给定的样本点，通过约束最小二乘法和随机选择方法对每个组合进行优化。之后,检查近似误差是否低于预定值。如果错误是允许的，该组合被选择为最优近似，或者检查了下一个组合。要验证性能，对几个具有代表性的函数进行了检查和分析。
