Geodesic
The
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 23 (2020) no. 2, pp. 127-142.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider an unstudied optimization problem of summing the elements of the two numerical sequences: $Y$ of length $N$ and $U$ of length $q\leqslant N$. The objective of the optimization problem is to minimize the sum of differences of weighted convolutions of sequences of variable lengths (which are not less than $q$). In each of the differences, the first convolution is the unweighted autoconvolution of the sequence $U$ nonlinearly expanded in time (by repetitions of its elements), and the second one is the weighted convolution of an expanded sequence with a subsequence of $Y$. The number of differences is given. We show that the problem is equivalent to that of approximation of the sequence $Y$ by an element of some exponentially sized set of sequences. Such a set consists of all the sequences of length $N$ which include, as subsequences, a given number $M$ of admissible quasiperiodic (fluctuating) repetitions of the sequence $U$. Each quasiperiodic repetition is generated by the following admissible transformations of the sequence $U$: (1) shifting $U$ in time, so that the differences between consecutive shifts do not exceed $T_{\max} \leqslant N$, (2) variable expansion of $U$ in time consisting in repeating each element of $U$, with variable multiplicities of the repetitions. The optimization objective is minimizing the sum of the squares of element-wise differences. We demonstrate that the optimization problem in combination with the corresponding approximation problem are solvable in polynomial time. Specifically, we show that there exists an algorithm which solves the problems in the time $\mathcal{O}(T^3_{\max}MN$). If $T_{\max}$ is a fixed parameter of the problem, then the algorithm running time is $O(MN)$. In the examples of numerical modeling, we show the applicability of the algorithm to solving applied problems of noise-robust analyzing electrocardiogram-like and photoplethysmogram-like signals. 
@article{SJVM_2020_23_2_a2,
     author = {A. V. Kel'manov and L. V. Mikhailova and P. S. Ruzankin and S. A. Khamidullin},
     title = {The},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {127--142},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2020_23_2_a2/}
}
TY  - JOUR
AU  - A. V. Kel'manov
AU  - L. V. Mikhailova
AU  - P. S. Ruzankin
AU  - S. A. Khamidullin
TI  - The
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2020
SP  - 127
EP  - 142
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2020_23_2_a2/
LA  - ru
ID  - SJVM_2020_23_2_a2
ER  - 
%0 Journal Article
%A A. V. Kel'manov
%A L. V. Mikhailova
%A P. S. Ruzankin
%A S. A. Khamidullin
%T The
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2020
%P 127-142
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2020_23_2_a2/
%G ru
%F SJVM_2020_23_2_a2
A. V. Kel'manov; L. V. Mikhailova; P. S. Ruzankin; S. A. Khamidullin. The. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 23 (2020) no. 2, pp. 127-142. http://geodesic.mathdoc.fr/item/SJVM_2020_23_2_a2/

[1] A. V. Kel'manov, S. A. Khamidullin, “Posterior detection of a given number of identical subsequences in a quasiperiodic sequence”, Comp. Math. and Math. Phys., 41:5 (2001), 762–774 | MR | Zbl

[2] A. V. Kel'manov, S. A. Khamidullin, L. V. Okol'nishnikova, “A posteriori detection of identical subsequences in a quasiperiodic sequence”, Pattern Recognition and Image Analysis, 12:4 (2002), 438–447 | MR

[3] A. V. Kel'manov, S. A. Khamidullin, L. V. Okol'nishnikova, “Aposteriornoe obnaruzhenie odinakovykh podposledovatel'nostei-fragmentov v kvaziperiodicheskoi posledovatel'nosti”, Sib. zhurn. industr. matematiki, 5:2(10) (2002), 94–108 | MR

[4] A. V. Kel'manov, B. Jeon, “A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train”, IEEE Transactions on Signal Processing, 52:3 (2004), 645–656 | DOI | MR | Zbl

[5] J. A. Carter, E. Agol, W. J. Chaplin et al, “Kepler-36: a pair of planets with neighboring orbits and dissimilar densities”, Science, 337:6094 (2012), 556–559 | DOI

[6] J. A. Carter, E. Agol, “The quasiperiodic automated transit search algorithm”, The Astrophysical J., 765:2 (2013), 132 | DOI

[7] G. Voskoboynikova, M. Khairetdinov, “Numerical modeling of posteriori algorithms for the geophysical monitoring”, Communications in Computer and Information Science, 549 (2015), 190–200 | DOI

[8] Stepwards, https://www.stepwards.com/?page_id=24147

[9] D. Zhang, W. Zuo, P. Wang, Computational Pulse Signal Analysis, Springer Nature Singapore Pte Ltd, 2018

[10] R. Rajni, I. Kaur, “Electrocardiogram signal analysis an overview”, Int. J. Comput. Appl., 84:7 (2013), 22–25

[11] https://www.comm.utoronto.ca/b̃iometrics/PPG_Dataset/index.html

[12] K. Shelley, S. Shelley, “Pulse oximeter waveform: photoelectric plethysmography”, Clinical monitoring: practical applications for anesthesia and critical care, eds. C. Lake, R. Hines, C. Blitt, W.B. Saunders Company, Philadelphia PA, 2001, 420–428

[13] M. Elgendi, “On the analysis of fingertip photoplethysmogram signals”, Current Cardiology Reviews, 8:1 (2012), 14–25 | DOI