DUST: A Duality-Based Pruning Method For Exact Multiple Change-Point Detection
Vincent Runge, Charles Truong, Simon Querné · 2025
Read DUST: A Duality-Based Pruning Method For Exact Multiple Change-Point Detection by Vincent Runge, Charles Truong, Simon Querné (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-02467.txt.
Description
Vincent Runge, Charles Truong, and Simon Querné speed up the exact hunt for change points in long time series, in a paper from twenty twenty-five. Dynamic programming finds every shift in a series' behavior, but slowly. Pruning rules that discard hopeless candidates made it fast, yet each existing rule has a blind spot: one fades when changes are sparse, the other suits only simple models.
Their framework, DUST, judges candidates through a dual function weighed against a threshold. Strong duality holds for the pruning problem under mild assumptions. For single-parameter models it pairs one rival's simplicity with the other's speed, and it shines for non-Gaussian data. A mouse monitoring series shows it recovering the true change structure efficiently.
Catalog record
| CREATOR | Vincent Runge, Charles Truong, Simon Querné |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 113 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-02467