Fast and Accurate Partial Fourier Transform for Time Series Data
Yong-chan Park, Jun-Gi Jang, U Kang
Abstract
Given a time-series vector, how can we efficiently detect anomalies? A widely used method is to use Fast Fourier transform (FFT) to compute Fourier coefficients, take first few coefficients while discarding the remaining small coefficients, and reconstruct the original time series to find points with large errors. Despite the pervasive use, the method requires to compute all of the Fourier coefficients which can be cumbersome if the input length is large or when we need to perform many FFT operations.
Topics & Concepts
Fast Fourier transformFourier seriesSeries (stratigraphy)Computer scienceFourier transformAlgorithmDiscrete Fourier transform (general)Non-uniform discrete Fourier transformSplit-radix FFT algorithmDiscrete-time Fourier transformPrime-factor FFT algorithmFourier analysisShort-time Fourier transformMathematicsMathematical analysisGeologyPaleontologyAnomaly Detection Techniques and ApplicationsTime Series Analysis and ForecastingImage and Signal Denoising Methods