A pruned recursive solution to the multiple change point problem

Eric Ruggieri ()
Additional contact information
Eric Ruggieri: College of the Holy Cross

Computational Statistics, 2018, vol. 33, issue 2, No 20, 1017-1045

Abstract: Abstract Long time series are often heterogeneous in nature. As such, the most appropriate model is one whose parameters are allowed to change through time. The exponential number of solutions to the multiple change point problem requires an efficient algorithm in order to be computationally feasible. Exact Bayesian solutions have at best quadratic complexity in the number of observations, which still can be too slow for very large data sets. Here, a pruned dynamic programming algorithm is proposed to fit a piecewise regression model with unknown break points to a data set. The algorithm removes unessential calculations, reducing the complexity of the most time consuming step of the algorithm from quadratic in the number of observations to quadratic in the average distance between change points. A distance measure is introduced that can be used to determine the divergence of the approximate joint posterior distribution from the exact posterior distribution. Analysis of two real data sets shows that this approximate algorithm produces a nearly identical representation of the joint posterior distribution on the locations of the change points, but with a significantly faster run time than its exact counterpart.

Keywords: Bayesian change point; Dynamic programming; Joint posterior; Kullback–Leibler divergence; Piecewise regression (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00180-017-0756-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:compst:v:33:y:2018:i:2:d:10.1007_s00180-017-0756-9

Ordering information: This journal article can be ordered from
http://www.springer.com/statistics/journal/180/PS2

DOI: 10.1007/s00180-017-0756-9

Access Statistics for this article

Computational Statistics is currently edited by Wataru Sakamoto, Ricardo Cao and Jürgen Symanzik

More articles in Computational Statistics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().