Accelerating Singular Spectrum Transformation for Scalable Change Point Detection - Weber, Lucas; Lenz, Richard (IEEE Access, 2025)
The Singular Spectrum Transformation (SST) is a powerful technique for Change Point Detection (CPD) and is widely applied in time series analysis to identify abrupt structural changes. Due to the involvement of the Singular Value Decomposition (SVD), the runtime of the SST cubically grows (O(N3) with the window size N. Therefore, applications building on the SST are often limited to small window sizes. An improved version of the SST, the IKA-SST, removes this bottleneck, but still suffers from similar scaling problems. Utilizing randomized decompositions and a fast matrix product, we reduce the computational complexities of both the SST and the IKA-SST to log-linear (O(N log N)), enabling efficient CPD for large window sizes and high-frequency signals. Focusing on the approximation error, we discuss how randomized decompositions are well-suited to SST-based CPD. By linking the scoring error to the decomposition error via a novel error bound, we provide theoretically grounded arguments that the efficiency gains incur only a small approximation error. We empirically evaluate the improved SST algorithms on a diverse collection of real and synthetic time series. Comparisons with the original algorithms confirm that the speedup, parallelization, and low approximation error translate well from theory to practice. Depending on the application, we measure acceleration factors of up to three orders of magnitude, reducing the wall time from hours to minutes, or even seconds, broadening the applicability of SST-based CPD. To support reproducibility and further applications, we publish our experimental code and reference implementations.
CRIS-Team Scopus Importer:2025-12-19
Keywords: Change Point Detection (CPD); Hankel Matrix Decomposition; Randomized Singular Value Decomposition (rSVD); Signal Processing; Singular Spectrum Analysis (SSA); Singular Spectrum Transformation; SST