# A Greedy Graph Search Algorithm Based on Changepoint Analysis for Automatic QRS Complex Detection

arXiv: https://arxiv.org/abs/2102.03538 · HTML: https://mlsanity.com/paper/2102.03538/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 43 references that are in the map.
- First posted on arXiv 6 Feb 2021.

## Builds on (most cited first, 9 of 9)

- [Inter- and intra- patient ECG heartbeat classification for arrhythmia detection: a sequence to sequence deep learning approach](https://mlsanity.com/paper/1812.07421/) (2018)
- [An Iterative Regularized Incremental Projected Subgradient Method for a Class of Bilevel Optimization Problems](https://mlsanity.com/paper/1809.10050/) (2018)
- [Single-modal and Multi-modal False Arrhythmia Alarm Reduction using Attention-based Convolutional and Recurrent Neural Networks](https://mlsanity.com/paper/1909.11791/) (2019)
- [An iterative regularized mirror descent method for ill-posed nondifferentiable stochastic optimization](https://mlsanity.com/paper/1901.09506/) (2019)
- [Multiple Change Point Detection and Validation in Autoregressive Time Series Data](https://mlsanity.com/paper/1912.07775/) (2019)
- [A Graph-constrained Changepoint Detection Approach for ECG Segmentation](https://mlsanity.com/paper/2004.13558/) (2020)
- [A log-linear time algorithm for constrained changepoint detection](https://mlsanity.com/paper/1703.03352/) (2017)
- [Optimization of Passive Chip Components Placement with Self-Alignment Effect for Advanced Surface Mounting Technology](https://mlsanity.com/paper/2001.09612/) (2020)
- [A Graph-Constrained Changepoint Learning Approach for Automatic QRS-Complex Detection](https://mlsanity.com/paper/2102.01319/) (2021)

## Abstract (arXiv)

The electrocardiogram (ECG) signal is the most widely used non-invasive tool for the investigation of cardiovascular diseases. Automatic delineation of ECG fiducial points, in particular the R-peak, serves as the basis for ECG processing and analysis. This study proposes a new method of ECG signal analysis by introducing a new class of graphical models based on optimal changepoint detection models, named the graph-constrained changepoint detection (GCCD) model. The GCCD model treats fiducial points delineation in the non-stationary ECG signal as a changepoint detection problem. The proposed model exploits the sparsity of changepoints to detect abrupt changes within the ECG signal; thereby, the R-peak detection task can be relaxed from any preprocessing step. In this novel approach, prior biological knowledge about the expected sequence of changes is incorporated into the model using the constraint graph, which can be defined manually or automatically. First, we define the constraint graph manually; then, we present a graph learning algorithm that can search for an optimal graph in a greedy scheme. Finally, we compare the manually defined graphs and learned graphs in terms of graph structure and detection accuracy. We evaluate the performance of the algorithm using the MIT-BIH Arrhythmia Database. The proposed model achieves an overall sensitivity of 99.64%, positive predictivity of 99.71%, and detection error rate of 0.19 for the manually defined constraint graph and overall sensitivity of 99.76%, positive predictivity of 99.68%, and detection error rate of 0.55 for the automatic learning constraint graph.