Standard

Polynomial-Time Solvability of One Optimization Problem Induced by Processing and Analyzing Quasiperiodic ECG and PPG Signals. / Kel’manov, Alexander; Khamidullin, Sergey; Mikhailova, Liudmila et al.

Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. ed. / Milojica Jaćimović; Michael Khachay; Vlasta Malkova; Mikhail Posypkin. Springer Gabler, 2020. p. 88-101 (Communications in Computer and Information Science; Vol. 1145 CCIS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

Harvard

Kel’manov, A, Khamidullin, S, Mikhailova, L & Ruzankin, P 2020, Polynomial-Time Solvability of One Optimization Problem Induced by Processing and Analyzing Quasiperiodic ECG and PPG Signals. in M Jaćimović, M Khachay, V Malkova & M Posypkin (eds), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Communications in Computer and Information Science, vol. 1145 CCIS, Springer Gabler, pp. 88-101, 10th International Conference on Optimization and Applications, OPTIMA 2019, Petrovac, Montenegro, 30.09.2019. https://doi.org/10.1007/978-3-030-38603-0_7

APA

Kel’manov, A., Khamidullin, S., Mikhailova, L., & Ruzankin, P. (2020). Polynomial-Time Solvability of One Optimization Problem Induced by Processing and Analyzing Quasiperiodic ECG and PPG Signals. In M. Jaćimović, M. Khachay, V. Malkova, & M. Posypkin (Eds.), Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers (pp. 88-101). (Communications in Computer and Information Science; Vol. 1145 CCIS). Springer Gabler. https://doi.org/10.1007/978-3-030-38603-0_7

Vancouver

Kel’manov A, Khamidullin S, Mikhailova L, Ruzankin P. Polynomial-Time Solvability of One Optimization Problem Induced by Processing and Analyzing Quasiperiodic ECG and PPG Signals. In Jaćimović M, Khachay M, Malkova V, Posypkin M, editors, Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. Springer Gabler. 2020. p. 88-101. (Communications in Computer and Information Science). doi: 10.1007/978-3-030-38603-0_7

Author

Kel’manov, Alexander ; Khamidullin, Sergey ; Mikhailova, Liudmila et al. / Polynomial-Time Solvability of One Optimization Problem Induced by Processing and Analyzing Quasiperiodic ECG and PPG Signals. Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers. editor / Milojica Jaćimović ; Michael Khachay ; Vlasta Malkova ; Mikhail Posypkin. Springer Gabler, 2020. pp. 88-101 (Communications in Computer and Information Science).

BibTeX

@inproceedings{25dd8972da984a38a89b90b6cc7efcd4,
title = "Polynomial-Time Solvability of One Optimization Problem Induced by Processing and Analyzing Quasiperiodic ECG and PPG Signals",
abstract = "This paper is devoted to an unexplored discrete optimization problem, which can be interpreted as a problem of least mean squares approximation of some observed discrete-time signal (a numerical time series) by an unobservable quasiperiodic (almost periodic) pulse signal generated by a pulse with a given pattern (reference) shape. Quasiperiodicity is understood, first, in the sense of admissible fluctuations of the interval between repetitions of the reference pulse, and second, in the sense of admissible nonlinear time expansions of its reference shape. Such problems are common in biomedical applications related to monitoring and analyzing electrocardiogram (ECG), photoplethysmogram (PPG), and several other signals. In the optimization model, the number of generated (admissible or approximating) quasiperiodic pulse sequences grows exponentially with the duration of the discrete-time signal (i.e., with the number of points in the time series). The size of the admissible solutions set also grows exponentially. However, despite that exponential growth, we have constructively proved the optimization problem polynomial-time solvability. Namely, we propose an algorithm that finds an optimal solution to the problem in (formula presented) time; where N is the duration of the observed signal (the number of points in the time series), (formula presented) is a positive integer number which bounds the fluctuations of the repetition period. If (formula presented) is a part of the input, then the algorithm{\textquoteright}s running time is (formula presented), i.e., the algorithm is polynomial. If (formula presented) is a fixed parameter (that is typical for applications), then the running-time of the algorithm is (formula presented), i.e., the algorithm is linear in time. Numerical simulation examples demonstrate the robustness of the algorithm in the presence of additive noise.",
keywords = "Discrete optimization problem, ECG, Linear-time algorithm and Pulse train signal processing, Polynomial-time solvability, PPG, Quasiperiodic",
author = "Alexander Kel{\textquoteright}manov and Sergey Khamidullin and Liudmila Mikhailova and Pavel Ruzankin",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 10th International Conference on Optimization and Applications, OPTIMA 2019 ; Conference date: 30-09-2019 Through 04-10-2019",
year = "2020",
month = jan,
day = "1",
doi = "10.1007/978-3-030-38603-0_7",
language = "English",
isbn = "9783030386023",
series = "Communications in Computer and Information Science",
publisher = "Springer Gabler",
pages = "88--101",
editor = "Milojica Ja{\'c}imovi{\'c} and Michael Khachay and Vlasta Malkova and Mikhail Posypkin",
booktitle = "Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers",
address = "Germany",

}

RIS

TY - GEN

T1 - Polynomial-Time Solvability of One Optimization Problem Induced by Processing and Analyzing Quasiperiodic ECG and PPG Signals

AU - Kel’manov, Alexander

AU - Khamidullin, Sergey

AU - Mikhailova, Liudmila

AU - Ruzankin, Pavel

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2020. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020/1/1

Y1 - 2020/1/1

N2 - This paper is devoted to an unexplored discrete optimization problem, which can be interpreted as a problem of least mean squares approximation of some observed discrete-time signal (a numerical time series) by an unobservable quasiperiodic (almost periodic) pulse signal generated by a pulse with a given pattern (reference) shape. Quasiperiodicity is understood, first, in the sense of admissible fluctuations of the interval between repetitions of the reference pulse, and second, in the sense of admissible nonlinear time expansions of its reference shape. Such problems are common in biomedical applications related to monitoring and analyzing electrocardiogram (ECG), photoplethysmogram (PPG), and several other signals. In the optimization model, the number of generated (admissible or approximating) quasiperiodic pulse sequences grows exponentially with the duration of the discrete-time signal (i.e., with the number of points in the time series). The size of the admissible solutions set also grows exponentially. However, despite that exponential growth, we have constructively proved the optimization problem polynomial-time solvability. Namely, we propose an algorithm that finds an optimal solution to the problem in (formula presented) time; where N is the duration of the observed signal (the number of points in the time series), (formula presented) is a positive integer number which bounds the fluctuations of the repetition period. If (formula presented) is a part of the input, then the algorithm’s running time is (formula presented), i.e., the algorithm is polynomial. If (formula presented) is a fixed parameter (that is typical for applications), then the running-time of the algorithm is (formula presented), i.e., the algorithm is linear in time. Numerical simulation examples demonstrate the robustness of the algorithm in the presence of additive noise.

AB - This paper is devoted to an unexplored discrete optimization problem, which can be interpreted as a problem of least mean squares approximation of some observed discrete-time signal (a numerical time series) by an unobservable quasiperiodic (almost periodic) pulse signal generated by a pulse with a given pattern (reference) shape. Quasiperiodicity is understood, first, in the sense of admissible fluctuations of the interval between repetitions of the reference pulse, and second, in the sense of admissible nonlinear time expansions of its reference shape. Such problems are common in biomedical applications related to monitoring and analyzing electrocardiogram (ECG), photoplethysmogram (PPG), and several other signals. In the optimization model, the number of generated (admissible or approximating) quasiperiodic pulse sequences grows exponentially with the duration of the discrete-time signal (i.e., with the number of points in the time series). The size of the admissible solutions set also grows exponentially. However, despite that exponential growth, we have constructively proved the optimization problem polynomial-time solvability. Namely, we propose an algorithm that finds an optimal solution to the problem in (formula presented) time; where N is the duration of the observed signal (the number of points in the time series), (formula presented) is a positive integer number which bounds the fluctuations of the repetition period. If (formula presented) is a part of the input, then the algorithm’s running time is (formula presented), i.e., the algorithm is polynomial. If (formula presented) is a fixed parameter (that is typical for applications), then the running-time of the algorithm is (formula presented), i.e., the algorithm is linear in time. Numerical simulation examples demonstrate the robustness of the algorithm in the presence of additive noise.

KW - Discrete optimization problem

KW - ECG

KW - Linear-time algorithm and Pulse train signal processing

KW - Polynomial-time solvability

KW - PPG

KW - Quasiperiodic

UR - http://www.scopus.com/inward/record.url?scp=85078431800&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-38603-0_7

DO - 10.1007/978-3-030-38603-0_7

M3 - Conference contribution

AN - SCOPUS:85078431800

SN - 9783030386023

T3 - Communications in Computer and Information Science

SP - 88

EP - 101

BT - Optimization and Applications - 10th International Conference, OPTIMA 2019, Revised Selected Papers

A2 - Jaćimović, Milojica

A2 - Khachay, Michael

A2 - Malkova, Vlasta

A2 - Posypkin, Mikhail

PB - Springer Gabler

T2 - 10th International Conference on Optimization and Applications, OPTIMA 2019

Y2 - 30 September 2019 through 4 October 2019

ER -

ID: 23258354