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

CREATORVincent Runge, Charles Truong, Simon Querné
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE113 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-02467

Browse the full library · About the Tower of Babel