Home > Research > Publications & Outputs > Detecting changes in slope with an L0 penalty

Research

Associated organisational units

Electronic data

  • 1701.01672v1

    Rights statement: This is an Submitted Manuscript of an article published by Taylor & Francis in Journal of Computational and Graphical Statistics on 20/08/2018, available online: http://www.tandfonline.com/10.1080/10618600.2018.1512868

    Submitted manuscript, 891 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

  • changes-in-slope

    Rights statement: This is an Accepted Manuscript of an article published by Taylor & Francis in Journal of Computational and Graphical Statistics on 20/08/2018, available online: http://www.tandfonline.com/10.1080/10618600.2018.1512868

    Accepted author manuscript, 807 KB, PDF document

    Available under license: CC BY-NC: Creative Commons Attribution-NonCommercial 4.0 International License

Links

Text available via DOI:

Keywords

View graph of relations

Detecting changes in slope with an L0 penalty

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Detecting changes in slope with an L0 penalty. / Fearnhead, Paul; Maidstone, Robert; Letchford, Adam.
In: Journal of Computational and Graphical Statistics, Vol. 28, No. 2, 01.06.2019, p. 265-275.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Fearnhead, P, Maidstone, R & Letchford, A 2019, 'Detecting changes in slope with an L0 penalty', Journal of Computational and Graphical Statistics, vol. 28, no. 2, pp. 265-275. https://doi.org/10.1080/10618600.2018.1512868

APA

Fearnhead, P., Maidstone, R., & Letchford, A. (2019). Detecting changes in slope with an L0 penalty. Journal of Computational and Graphical Statistics, 28(2), 265-275. https://doi.org/10.1080/10618600.2018.1512868

Vancouver

Fearnhead P, Maidstone R, Letchford A. Detecting changes in slope with an L0 penalty. Journal of Computational and Graphical Statistics. 2019 Jun 1;28(2):265-275. Epub 2018 Aug 20. doi: 10.1080/10618600.2018.1512868

Author

Fearnhead, Paul ; Maidstone, Robert ; Letchford, Adam. / Detecting changes in slope with an L0 penalty. In: Journal of Computational and Graphical Statistics. 2019 ; Vol. 28, No. 2. pp. 265-275.

Bibtex

@article{a3aa48cd6fba4ffc9e9b5414ad903456,
title = "Detecting changes in slope with an L0 penalty",
abstract = "While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L 0 penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L 0 penalty is more reliable at estimating changepoint locations than using an L 1 penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online. ",
keywords = "stat.CO, stat.ME, stat.ML",
author = "Paul Fearnhead and Robert Maidstone and Adam Letchford",
note = "This is an Accepted Manuscript of an article published by Taylor & Francis in Journal of Computational and Graphical Statistics on 20/08/2018, available online: http://www.tandfonline.com/10.1080/10618600.2018.1512868 Original version was placed on arXiv.",
year = "2019",
month = jun,
day = "1",
doi = "10.1080/10618600.2018.1512868",
language = "English",
volume = "28",
pages = "265--275",
journal = "Journal of Computational and Graphical Statistics",
issn = "1061-8600",
publisher = "American Statistical Association",
number = "2",

}

RIS

TY - JOUR

T1 - Detecting changes in slope with an L0 penalty

AU - Fearnhead, Paul

AU - Maidstone, Robert

AU - Letchford, Adam

N1 - This is an Accepted Manuscript of an article published by Taylor & Francis in Journal of Computational and Graphical Statistics on 20/08/2018, available online: http://www.tandfonline.com/10.1080/10618600.2018.1512868 Original version was placed on arXiv.

PY - 2019/6/1

Y1 - 2019/6/1

N2 - While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L 0 penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L 0 penalty is more reliable at estimating changepoint locations than using an L 1 penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online.

AB - While there are many approaches to detecting changes in mean for a univariate time series, the problem of detecting multiple changes in slope has comparatively been ignored. Part of the reason for this is that detecting changes in slope is much more challenging: simple binary segmentation procedures do not work for this problem, while existing dynamic programming methods that work for the change in mean problem cannot be used for detecting changes in slope. We present a novel dynamic programming approach, CPOP, for finding the “best” continuous piecewise linear fit to data under a criterion that measures fit to data using the residual sum of squares, but penalizes complexity based on an L 0 penalty on changes in slope. We prove that detecting changes in this manner can lead to consistent estimation of the number of changepoints, and show empirically that using an L 0 penalty is more reliable at estimating changepoint locations than using an L 1 penalty. Empirically CPOP has good computational properties, and can analyze a time series with 10,000 observations and 100 changes in a few minutes. Our method is used to analyze data on the motion of bacteria, and provides better and more parsimonious fits than two competing approaches. Supplementary material for this article is available online.

KW - stat.CO

KW - stat.ME

KW - stat.ML

U2 - 10.1080/10618600.2018.1512868

DO - 10.1080/10618600.2018.1512868

M3 - Journal article

VL - 28

SP - 265

EP - 275

JO - Journal of Computational and Graphical Statistics

JF - Journal of Computational and Graphical Statistics

SN - 1061-8600

IS - 2

ER -