Main content

A Linear Time Algorithm for Near Minimax Continuous Piecewise Linear Representations of Discrete Data

Show full item record

Title: A Linear Time Algorithm for Near Minimax Continuous Piecewise Linear Representations of Discrete Data
Author: Szusz, Emily K.; Willms, Allan R.
Abstract: An algorithm that constructs a continuous piecewise linear representation, subject to a certain slope/segment length constraint, of a given set of data is described. The algorithm yields an optimal or near optimal representation, subject to this constraint, in the $L_{\infty}$ norm and does so in at worst $O(nK)$ time, where $n$ is the number of data points and $K$ the number of segments. The constraint is determined by a user-specified parameter, $t_{\min}$, which dictates a lower bound for the distance between opposite-sign slope discontinuities. For reasonable $t_{\min}$ values, the resulting representation of the data captures the signal and both smooths the noise and provides a measure of it. This representation is useful for applications that require a specified interval for the data values and also allows easy and continuous interpolation of ranges between recorded time points. The algorithm is described, some of its properties are proven, and its capabilities demonstrated with several examples. Comparisons are made with alternative techniques.
URI: http://hdl.handle.net/10214/6589
Date: 2010-08-24
Terms of Use: All items in the Atrium are protected by copyright with all rights reserved unless otherwise indicated.
Citation: SIAM J. Sci. Comput. 32 (5) (2010) 2584-2602.


Files in this item

Files Size Format View Description
Szusz_Willms_SIAMJSciComput_2010.pdf 1.020Mb PDF View/Open Main article - publisher's version

This item appears in the following Collection(s)

Show full item record

http://creativecommons.org/licenses/by-nc-nd/2.5/ca/ Except where otherwise noted, this item's license is described as http://creativecommons.org/licenses/by-nc-nd/2.5/ca/