Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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 proceeding › Conference contribution › Research › peer-review
}
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