Weber L, Lenz R (2025)
Publication Language: English
Publication Type: Journal article, Original article
Publication year: 2025
Book Volume: 13
Pages Range: 213556 - 213577
DOI: 10.1109/ACCESS.2025.3640386
Open Access Link: https://ieeexplore.ieee.org/document/11278163
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.
APA:
Weber, L., & Lenz, R. (2025). Accelerating Singular Spectrum Transformation for Scalable Change Point Detection. IEEE Access, 13, 213556 - 213577. https://doi.org/10.1109/ACCESS.2025.3640386
MLA:
Weber, Lucas, and Richard Lenz. "Accelerating Singular Spectrum Transformation for Scalable Change Point Detection." IEEE Access 13 (2025): 213556 - 213577.
BibTeX: Download