Wir freuen uns, mitteilen zu können, dass unser Paper „Accelerating Singular Spectrum Transformation for Scalable Change Point Detection“ von Lucas Weber und Richard Lenz zur Veröffentlichung in IEEE Access angenommen wurde (Open Access – frei verfügbar: https://doi.org/10.1109/ACCESS.2025.3640386).
Singular Spectrum Transformation (SST) ist eine weit verbreitete Methode zur Change-Point-Detektion (CPD) in Zeitreihen; ihre praktische Anwendung wird jedoch häufig durch die schnell ansteigende Laufzeit bei größeren Fenstergrößen begrenzt.
Der Beitrag zeigt, wie wir die Laufzeit der SST verbessern können, ohne die Ergebnisse des Algorithmus zu verändern. Die Beschleunigung erreichen wir durch eine Verringerung der algorithmischen Komplexität, die im Gegensatz zu konstanten Laufzeitverbesserungen ihren Vorteil mit steigenden Fenstergrößen immer weiter ausbaut.
Konkret senken wir die Laufzeitkomplexität von O(N³) auf O(NlogN) für zwei verbreitete Varianten des Algorithmus (SST und IKA-SST), indem wir zentrale Operationen durch randomisierte Matrixzerlegungen und ein schnelles Hankel-Matrix-Produkt ersetzen.
Unter realen Bedingungen ist die SST nun 100- bis 1000-mal schneller, sodass Läufe, die zuvor Stunden dauerten, in Minuten oder Sekunden abgeschlossen werden können. Im Rahmen einer Fallstudie zeigen wir, wie sich die Laufzeit einer konkreten Anwendung von 22 Stunden auf 22 Minuten verkürzt.
Für interessierte Anwender:
Wir haben Referenzimplementierungen und Experimentcode veröffentlicht und stellen außerdem ein per pip installierbares Paket (changepoynt, https://github.com/Lucew/changepoynt) bereit, um die verbesserten Methoden einfach in praktische Anwendungen zu integrieren.
Über die algorithmischen Beschleunigungen hinaus enthält das Paper eine ausführliche Fehleranalyse: Durch die Herleitung einer expliziten Schranke wird gezeigt, dass der Approximationsfehler im beabsichtigten Anwendungsfall gering ausfällt.
Diese Arbeit wurde von der Siemens Energy AG im Rahmen des Projekts DARTS unterstützt. Zudem danken wir dem Open-Access-Publikationsfonds der Friedrich-Alexander-Universität Erlangen-Nürnberg (FAU-Publikationsfonds) für die Unterstützung.