Piecewise linear approximation: Difference between revisions

Revision as of 22:57, 24 November 2021

Authors: Tianhong Tan, Shoudong Zhu (CHEME 6800, 2021 Fall)

Introduction

Currently, approximating a complex non-linear function or smooth curve is very common in industry area. Like the very popular one, piecewise linear approximation, which is applied in a variety of real-world areas, such as signal processing and image processing in electronics information industry, pattern recognition in AI area^[1]. The problem of piecewise linear approximation can be classified by which type of norms applied in approximating process, whether the length of segments is fixed or not and whether the approximation is continuity or discontinuity^[2]. We can use piecewise linear approximation to represent any non-linear or linear function by any accuracy order by any accuracy by adding more nodes or segments until the accuracy is met^[3]. The meaning of piecewise linear approximation's existence is it allow us to transform non-linear problem to be solved by linear formation, which is easier to be executed by machine and the amount of calculation is acceptable^[4].

Theory, Methodology & Algorithms

For a function f(x) in a finite range [x_{1}, x_{n}], one can find n sampling points x1, x2, …, xn to evaluate the function values. Then the f(x) can be approximated by a series of linear segments [(xi, f(xi)), (xi+1, f(xi+1))], where i = 1, 2, …, n – 1. For any given value x’ between xi and xi+1, x’ can be written as the following form:

Numerical Example

Applications

Conclusion

References

↑ G. Manis, G. Papakonstantinou and P. Tsanakas, "Optimal piecewise linear approximation of digitized curves," Proceedings of 13th International Conference on Digital Signal Processing, 1997, pp. 1079-1081 vol.2, doi: 10.1109/ICDSP.1997.628552.
↑ J. G. Dunham, "Optimum Uniform Piecewise Linear Approximation of Planar Curves," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 1, pp. 67-75, Jan. 1986, doi: 10.1109/TPAMI.1986.4767753.
↑ Optimal Piecewise Linear Approximation of Convex Functions A. Imamoto, B. Tang, Member, IAENG, Proceedings of the World Congress on Engineering and Computer Science 2008 WCECS 2008, October 22 - 24, 2008, San Francisco, USA
↑ Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley,1977) http://web.mit.edu/15.053/www/AppliedMathematicalProgramming.pdf

[1] G. Manis, G. Papakonstantinou and P. Tsanakas, "Optimal piecewise linear approximation of digitized curves," Proceedings of 13th International Conference on Digital Signal Processing, 1997, pp. 1079-1081 vol.2, doi: 10.1109/ICDSP.1997.628552.

[2] J. G. Dunham, "Optimum Uniform Piecewise Linear Approximation of Planar Curves," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 1, pp. 67-75, Jan. 1986, doi: 10.1109/TPAMI.1986.4767753.

[3] Optimal Piecewise Linear Approximation of Convex Functions A. Imamoto, B. Tang, Member, IAENG, Proceedings of the World Congress on Engineering and Computer Science 2008 WCECS 2008, October 22 - 24, 2008, San Francisco, USA

[4] Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley,1977) http://web.mit.edu/15.053/www/AppliedMathematicalProgramming.pdf

[1]

[2]

[3]

[4]

@@ Line 3: / Line 3: @@
 Currently, approximating a complex non-linear function or smooth curve is very common in industry area. Like the very popular one, piecewise linear approximation, which is applied in a variety of real-world areas, such as signal processing and image processing in electronics information industry, pattern recognition in AI area<ref>G. Manis, G. Papakonstantinou and P. Tsanakas, "Optimal piecewise linear approximation of digitized curves," Proceedings of 13th International Conference on Digital Signal Processing, 1997, pp. 1079-1081 vol.2, doi: 10.1109/ICDSP.1997.628552.</ref>. The problem of piecewise linear approximation can be classified by which type of norms applied in approximating process, whether the length of segments is fixed or not and whether the approximation is continuity or discontinuity<ref>J. G. Dunham, "Optimum Uniform Piecewise Linear Approximation of Planar Curves," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no. 1, pp. 67-75, Jan. 1986, doi: 10.1109/TPAMI.1986.4767753.</ref>. We can use piecewise linear approximation to represent any non-linear or linear function by any accuracy order by any accuracy by adding more nodes or segments until the accuracy is met<ref> Optimal Piecewise Linear Approximation of Convex Functions A. Imamoto, B. Tang, Member, IAENG, Proceedings of the World Congress on Engineering and Computer Science 2008 WCECS 2008, October 22 - 24, 2008, San Francisco, USA</ref>. The meaning of piecewise linear approximation's existence is it allow us to transform non-linear problem to be solved by linear formation, which is easier to be executed by machine and the amount of calculation is acceptable<ref> Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley,1977) http://web.mit.edu/15.053/www/AppliedMathematicalProgramming.pdf</ref>.
 ==Theory, Methodology & Algorithms==
-For a function f(x) in a finite range [x1, xn], one can find n sampling points x1, x2, …, xn to evaluate the function values. Then the f(x) can be approximated by a series of linear segments [(xi, f(xi)), (xi+1, f(xi+1))], where i = 1, 2, …, n – 1. For any given value x’ between xi and xi+1, x’ can be written as the following form:
+For a function f(x) in a finite range [x_{1}, x_{n}], one can find n sampling points x1, x2, …, xn to evaluate the function values. Then the f(x) can be approximated by a series of linear segments [(xi, f(xi)), (xi+1, f(xi+1))], where i = 1, 2, …, n – 1. For any given value x’ between xi and xi+1, x’ can be written as the following form:
 ==Numerical Example==