Memory-Efficient Centroid Decomposition for Long Time Series
Real-world applications that deal with time series data often rely on matrix decomposition techniques, such as the Singular Value Decomposition (SVD). The Centroid Decomposition (CD) approximates the Singular Value Decomposition, but does not scale to long time series because of the quadratic space complexity of the sign vector computation. In this paper, we propose a greedy algorithm, termed Scalable Sign Vector (SSV), to efficiently determine sign vectors for CD applications with long time series, i.e., where the number of rows (observations) is much larger than the number of columns (time series). The SSV algorithm starts with a sign vector consisting of only 1s and iteratively changes the sign of the element that maximizes the benefit. The space complexity of the SSV algorithm is linear in the length of the time series. We provide proofs for the scalability, the termination, and the correctness of the SSV algorithm. Experiments with real-world hydrological time series and data sets from the UCR repository validate the analytical results and show the scalability of SSV.
Code (1)
Tasks
Time SeriesTime Series AnalysisSimilar Papers 제목 키워드 기반
CNN inference acceleration using dictionary of centroids
It is well known that multiplication operations in convolutional layers of common CNNs consume a lot of time during inference stage. In this article we present a flexible method to decrease both computational complexity …
QuantizationTensor DecompositionCorrelation recurrent units: A novel neural architecture for improving the predictive performance of time-series data
The time-series forecasting (TSF) problem is a traditional problem in the field of artificial intelligence. Models such as Recurrent Neural Network (RNN), Long Short Term Memory (LSTM), and GRU (Gate Recurrent Units) hav…
Time SeriesTime Series AnalysisTime Series ForecastingLSTM-MSNet: Leveraging Forecasts on Sets of Related Time Series with Multiple Seasonal Patterns
Generating forecasts for time series with multiple seasonal cycles is an important use-case for many industries nowadays. Accounting for the multi-seasonal patterns becomes necessary to generate more accurate and meaning…
Time SeriesTime Series AnalysisTimes series averaging from a probabilistic interpretation of time-elastic kernel
At the light of regularized dynamic time warping kernels, this paper reconsider the concept of time elastic centroid (TEC) for a set of time series. From this perspective, we show first how TEC can easily be addressed as…
ClusteringDynamic Time WarpingGeneral ClassificationTime Series+3Solar Flare Prediction Using Long Short-term Memory (LSTM) and Decomposition-LSTM with Sliding Window Pattern Recognition
We investigate the use of Long Short-Term Memory (LSTM) and Decomposition-LSTM (DLSTM) networks, combined with an ensemble algorithm, to predict solar flare occurrences using time-series data from the GOES catalog. The d…