uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computationally Efficient Off-Line Joint Change Point Detection in Multiple Time Series
Uppsala University, Disciplinary Domain of Science and Technology, Technology, Department of Engineering Sciences, Signals and Systems Group. (Signals & Systems)ORCID iD: 0000-0002-6689-3257
Uppsala University, Disciplinary Domain of Science and Technology, Technology, Department of Engineering Sciences, Signals and Systems Group.
2019 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 67, no 1, p. 149-163Article in journal (Refereed) Published
Abstract [en]

In this paper, a computationally efficient algorithm for Bayesian joint change point (CP) detection (CPD) in multiple time series is presented. The data generation model includes a number of change configurations (CC), each affecting a unique subset of the time series, which introduces correlation between the positions of CPs in the monitored time series. The inference objective is to identify joint changes and the associated CC. The algorithm consists of two stages: First a univariate CPD algorithm is applied separately to each of the involved time series. The outcomes of this step are maximum a posteriori (MAP) detected CPs and posterior distributions of CPs conditioned on the MAP CPs. These outcomes are used in combination to approximate the posterior for the CCs. In the second algorithm stage, dynamic programming is used to find the maxima of this approximate CC posterior. The algorithm is applied to synthetic data and it is shown to be both significantly faster and more accurate compared to a previously proposed algorithm designed to solve similar problems. Also, the initial algorithm is extended with steps from the Maximization-Maximization algorithm which allows the hyperparameters of the data generation model to be estimated jointly with the CCs, and we show that these estimates coincide with estimates obtained from a Markov Chain Monte Carlo algorithm.

Place, publisher, year, edition, pages
2019. Vol. 67, no 1, p. 149-163
National Category
Signal Processing
Identifiers
URN: urn:nbn:se:uu:diva-366291DOI: 10.1109/TSP.2018.2880669ISI: 000451940300002OAI: oai:DiVA.org:uu-366291DiVA, id: diva2:1264096
Available from: 2018-11-19 Created: 2018-11-19 Last updated: 2019-02-23Bibliographically approved
In thesis
1. Change Point Detection with Applications to Wireless Sensor Networks
Open this publication in new window or tab >>Change Point Detection with Applications to Wireless Sensor Networks
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis work we develop a new algorithm for detecting joint changes in statistical behavior of multiple, simultaneously recorded, signals. Such signal analysis is commonly known as multivariate change point (CP) detection (CPD) and is of interest in many scientific and engineering applications.

First we review some of the existing CPD algorithms, where special attention is given to the Bayesian methods. Traditionally, many of the previous works on Bayesian CPD have focused on sampling based methods using Markov Chain Monte Carlo (MCMC). More recent work has shown that it is possible to avoid the computationally expensive MCMC methods by using a technique that is reminiscent of the forward-backward algorithm used for hidden Markov models. We revisit that technique and extend it to a multivariate CPD scenario where subsets of the monitored signals are affected at each CP. The extended algorithm has excellent CPD accuracy, but unfortunately, this fully Bayesian approach quickly becomes intractable when the size of the data set increases.

For large data sets, we propose a two-stage algorithm which, instead of considering all possible combinations of joint CPs as in the fully Bayesian approach, only computes an approximate solution to the most likely combination. In the first stage, the time series are processed in parallel with a univariate CPD algorithm. In the second stage, a dynamic program (DP) is used to search for the combination of joint CPs that best explains the CPs detected by the first stage. The computational efficiency of the second stage is improved by incorporating a pruning condition which reduces the search space of the DP. 

To motivate the algorithm, we apply it to measurements of radio channels in factory environments. The analysis shows that certain subsets of radio channels often experiences simultaneous changes in channel gain.

In addition, a detailed statistical study of the radio channel measurements is presented, including empirical evidence that radio channels exhibit statistical dependencies over long time horizons which implies that it is possible to design predictors of future channel conditions.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2019. p. 102
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1777
Keywords
Change Point Detection, Signal Processing, Dynamic Programming
National Category
Signal Processing
Research subject
Electrical Engineering with specialization in Signal Processing
Identifiers
urn:nbn:se:uu:diva-377640 (URN)978-91-513-0580-6 (ISBN)
Public defence
2019-05-10, Room 80101, Ångströmlaboratoriet, Lägerhyddsvägen 1, Uppsala, 08:30 (English)
Opponent
Supervisors
Available from: 2019-03-21 Created: 2019-02-23 Last updated: 2019-05-07

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Eriksson, MarkusOlofsson, Tomas

Search in DiVA

By author/editor
Eriksson, MarkusOlofsson, Tomas
By organisation
Signals and Systems Group
In the same journal
IEEE Transactions on Signal Processing
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 158 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf