Fast Feature Extraction for Time Series Analysis Using Least-Squares Approximations with Orthogonal Basis Functions

Many efforts have been made during the past decades to investigate the use of orthogonal basis functions in the field of least-squares approximation. Certain bases of orthogonal functions allow for a definition of fast update algorithms for approximations of time series in sliding or growing time windows. In fields such as technical data analytics, temporal data mining, or pattern recognition in time series, appropriate time series representations are needed to measure the similarity of time series or to segment them. This article bridges the gap between mathematical basic research and applications by making fast update techniques for standard polynomials and trigonometric polynomials accessible for time series classification or regression (e.g., forecasting), anomaly or motif detection in time series, etc. This is of utmost importance for online or big data applications. Time series or segments of time series will be represented by features derived from the orthogonal expansion coefficients of the approximating polynomials which capture the essential behavior in the time or spectral domain, i.e. trends and periodic behavior, using standard or trigonometric polynomials. Our experiments show that a reliable computation is possible at a very low runtime compared to a conventional least-squares approach. The algorithms are implemented in Java, C(++), Matlab, and Python and made publicly available.