Open AccessOn Complexity of Adaptive Splines
Publication year - 2020
Publication title -
international journal of circuits, systems and signal processing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.156
H-Index - 13
ISSN - 1998-4464
DOI - 10.46300/9106.2020.14.78
Subject(s) - compression (physics) , a priori and a posteriori , algorithm , piecewise , mathematics , flow (mathematics) , mathematical optimization , piecewise linear function , spline (mechanical) , interpolation (computer graphics) , computer science , artificial intelligence , geometry , mathematical analysis , motion (physics) , philosophy , materials science , structural engineering , epistemology , engineering , composite material
The paper discusses various methods of adaptive spline approximations for the flow of function values. It is considered an adaptive compression algorithm, which, for a priori given , has the properties 1) the complexity of the algorithm is proportional to the length of the original flow, 2) by the piecewise linear interpolation of the compression result, it is possible to restore the original flow with an accuracy of 3) the compression result is close to optimal and has 0(M) of arithmetic operations. The effectiveness of this approach is demonstrated on rapidly changing initial flows of numerical information in the digital experiment . In addition, the paper presents an exact two-sided estimate for the number 0(M2 ) of arithmetic operations for the optimal solution of the problem of compressing an informational numerical flow of length M with the possibility of recovering this flow with a predetermined accuracy. Provided that the original flow is convex, a compression algorithm is developed with an accurate twosided estimate of the number 0(Mlog2M) and with the possibility of recovery with a prescribed accuracy.