A linear time algorithm for near minimax continuous piecewise linear representations of discrete data

摘要

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∞ 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, tmin, which dictates a lower bound for the distance between opposite-sign slope discontinuities. For reasonable tmin 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.