Expand description
PELT — Pruned Exact Linear Time change-point detection.
Reference: Killick, Fearnhead & Eckley, Optimal Detection of Changepoints With a Linear Computational Cost, JASA 107 (500), 2012.
PELT solves the optimal-partition DP
F(t) = min_{τ < t} [ F(τ) + C(y_{τ+1..t}) + β ]where C is a segment cost (here L2 on the mean, i.e.
Σ (yᵢ − ȳ)²) and β is the per-change-point penalty. The
pruning step removes candidates τ for which
F(τ) + C(τ+1:t) + K ≥ F(t) — those can never be optimal later —
and gives the algorithm its linear expected-time behaviour under a
Poisson-rate change-point assumption.
K is the cost-reduction constant; for the L2 cost K = 0 is
valid (see Killick et al. §2.2).