Alignment of time series with use of the generalized Legendre's transformation and methods of idempotenty mathematics

Maria V. Kurkina; Куркина Мария Викторовна; Sergey P. Semenov; Семенов Сергей Петрович; Viktor V. Slavsky; Славский Виктор Владимирович; Olga V. Samarina; Самарина Ольга Владимировна; Olga A. Petuhova; Петухова Ольга Анатольевна; Aleksey A. Petrov; Петров Алексей Аверьянович; Anton A. Finogenov; Финогенов Антон Анатольевич; Valeriy A. Samarin; Самарин Валерий Анатольевич

doi:10.17816/byusu2020375-82

Alignment of time series with use of the generalized Legendre's transformation and methods of idempotenty mathematics

Authors: Kurkina M.V.¹, Semenov S.P.¹, Slavsky V.V.¹, Samarina O.V.¹, Petuhova O.A.¹, Petrov A.A.¹, Finogenov A.A.¹, Samarin V.A.¹
Affiliations:
1. Yugra State University
Issue: Vol 16, No 3 (2020)
Pages: 75-82
Section: Math modeling
URL: https://vestnikugrasu.org/byusu/article/view/59631
DOI: https://doi.org/10.17816/byusu2020375-82
ID: 59631

Cite item

Full Text

Abstract
Full Text
About the authors
References
Supplementary files
Statistics

Abstract

Alignment of time series [time-series smoothing] – identification of the main tendency of development (временнóго a trend) by "cleaning" of a time series of the accidental deviations distorting this tendency. At a research of time series of economy (bioinformation science) apply for detection of patterns [1-3].

In this work it is offered to use for this purpose Legendre's transformation well-known in physics and mathematics. Its direct application to poorly regular objects is difficult therefore in work its idempotent analog is defined previously and on its basis the concept of the TRACK for a time series is defined.

In recent years within the international center "Cuofus Li" the new field of mathe-matics – idempotent or "tropical" mathematics gained intensive development that is reflected in works of the academician V.P. Maslov and his pupils: G.L. Litvinov, A.N. Sobolevsky, etc.

The purpose of this work to be beyond duality of the theory of linear vector spaces, using similar concepts of duality of conformally flat Riemannian geometry and of idempotent algebra.

By analogy with the polar transformation of a conformally flat Riemannian metrics entered in E.D. Rodionov and V.V. Slavsky's works the abstract idempotent analog of transformation of Legendre is under construction. In the MATLAB system the program complex for calculation the TRACK of a time series is created. It is in-vestigated its opportunities for digital processing of time series.

Keywords

идемпотентный анализ, временные ряды, конформно-выпуклые функции, преобразование Лежандра, выпуклое и вогнутое замыкание функции

Full Text

Введение

Пусть функция $f : R^{n} \to R$ задана на евклидовом арифметическом пространстве. Преобразованием Юнга – Фенхеля функции $f$ называют функцию $f^{*}$ , где

$f^{*} (ξ) = \underset{x}{s u p} [(ξ, x) - f (x)]$ (1)

Формула (1) есть обобщение классического преобразования Лежандра для достаточно гладких функций $f$ и $f^{*}$ , в этом случае $f$ и $f^{*}$ связаны соотношением

$(x, ξ) = f (x) + f^{*} (ξ)$ , где $ξ = \nabla f (x)$ , $x = \nabla f^{*} (ξ)$

Если ограничиться случаем n=1, то скалярное произведение $(ξ, x)$ есть просто произведение двух чисел, тогда:

$x \cdot ξ = f (x) + f^{*} (ξ)$ , $ξ = \frac{d f (x)}{d x}$ , $x = \frac{d f^{*} (ξ)}{d ξ}$ /

Преобразование Лежандра обладает рядом замечательных свойств. Нас в нашей работе будут интересовать следующие свойства:

неравенство x $ξ \leq f (x) + f^{*} (ξ)$ которое является обобщением неравенства Юнга,
в случае выпуклых функций преобразование Лежандра инволютивно $f^{* *} = f$ ,
в общем случае $f^{* *} \leq f$ и $f^{* *}$ есть выпуклая оболочка (или замыкание) функции $f$ .

Преобразование Лежандра применяется в физике, в теории дифференциальных уравнений, в теории выпуклых множеств [1-18]. Из новых применений преобразования Лежандра можно отметить применение в цифровой обработке сигналов [1-3].

Полярное преобразование конформно-плоской метрики с неотрицательной одномерной кривизной

В данной части мы используем обозначения и результаты работы [5]. Пусть R – числовая прямая, $R^{n + 1}$ – евклидово (n+1) -мерное арифметическое пространство, $M^{n + 2} = R^{n + 1} \times R$ – псевдоевклидово пространство, скалярный квадрат вектора $\vec{w} = [\vec{x}, ζ] \in M^{n + 2}$ в котором равен ${<\vec{w}>}^{2} = | \vec{x} |^{2} - ζ^{2}$ , где $| \vec{x} |^{2}$ – скалярный квадрат вектора $\vec{x} \in R^{n + 1}$ . Обозначим через

$C^{+} = {[\vec{x}, ζ] \in M^{n + 2} : | \vec{x} |^{2} - ζ^{2} = 0, ζ > 0}$ ,

верхнюю часть изотропного конуса в $M^{n + 2}$ . В дальнейшем, если будет ясно из контекста, мы будем обозначать $x^{2}$ через x.

Лемма 1. Пусть на единичной сфере $S^{n} \subset R^{n + 1}$ задана конформно-плоская метрика

$s^{2} = \frac{d x^{2}}{f^{2} (x)}$ , $x \in S^{n} \subseteq R^{n + 1}$ ,

где $f (x)$ функция класса c¹. Тогда определено каноническое изометрическое вложение, задаваемое формулой

$Z : x \in S^{n} \to [\frac{x}{f (x)}, \frac{1}{f (x)}] \in C^{+}$ . (2)

Образ $Z (S^{n}) = F \subseteq C^{+}$ – пространственно подобная n -мерная поверхность. Будем отождествлять конформно-плоскую метрику с поверхностью F. Предположим, что функция достаточно гладкая, тогда поверхность регулярна, и в каждой точке $Z (x) \in F$ определено касательное n -мерное пространство $T_{x} (F)$ . Существует единственный вектор $Z^{*} (x) \in C^{+}$ такой, что

$⟨ Z, Z^{*} ⟩ = - 1$ , $Z^{*} ⊥ T_{x} (F)$ , (3)

где ортогональность понимается относительно скалярного произведения в $M^{n + 2}$ .

Лемма 2. Пусть функция $f (\vec{x})$ , задающая конформно-плоскую метрику, по однородности распространена на все пространство $R^{n + 1}$ . Тогда вектор Z^* явно выражается через $f$ и $\vec{\nabla} f$ в $R^{n + 1}$ :

$Z^{*} (\vec{x}) = [- \vec{\nabla} f + \frac{| \vec{\nabla} f |^{2}}{2 f \vec{x}}, \frac{| \vec{\nabla} f |^{2}}{2 f}]$ , (4)

где $\vec{x} \in S^{n} \subset R^{n + 1}$ , $\vec{\nabla} f$ градиент функции $f$ в пространстве $R^{n + 1}$ .

Определение 1. Если точка $Z \in F$ пробегает поверхность F, то точка Z^* пробегает двойственную поверхность F^*. Соответствующую конформно-плоскую метрику $d {s^{*}}^{2} = \frac{d y^{2}}{{f^{*}}^{2} (y)}$ , $y \in S^{n}$ будем называть полярной к исходной метрике [14]. Сравнивая формулы (2) и (4), имеем:

$[- \vec{\nabla} f + \frac{| \nabla f |^{2}}{2 f} \vec{x}, \frac{| \nabla f |^{2}}{2 f}] \equiv [\frac{y}{f^{*} (y)}, \frac{1}{f^{*} (y)}]$ .

Откуда получаем формулы для перехода к полярной конформно-плоской метрике в параметрическом виде:

$f^{*} (y) = \frac{2 f (x)}{| \nabla f |^{2}}$ , $\vec{y} = \vec{x} - 2 f (x) \frac{\vec{\nabla} f}{| \nabla f |^{2}}$ . (5)

Лемма 3. Пусть $f : R^{n + 1} \to R$ произвольная однородная степени один функция на $R^{n + 1}$ . Отображение $H_{f} : S^{n} \to S^{n}$ , определяемое формулой

$H_{f} : \vec{x} \in S^{n} \to \vec{x} - 2 f (x) \frac{\vec{\nabla} f}{| \nabla f |^{2}} \in S^{n}$ , (6)

сохраняет норму вектора: $| H_{f} (\vec{x}) | = | \vec{x} |$ .

Определение 2. Отображение $H_{f}$ назовем конформным градиентом функции $f$ . Если отображение $H_{f}$ имеет обратное $H_{f}^{- 1}$ , то полярная метрика определяется в явном виде функцией:

$f^{*} (y) = \frac{2 f (x)}{| \nabla f |^{2}} |_{x = H_{f}^{- 1} (y)}$ .

Замечание. Из определения (1) следует двойственность метрики $d s^{2} = \frac{d x^{2}}{f^{2} (x)}$ , $x \in S^{n}$ и метрики $d {s^{*}}^{2} = \frac{d y^{2}}{{f^{*}}^{2} (y)}$ , $y \in S^{n}$ . Поэтому при наличии соответствующей регулярности функции $f^{*} (y)$ будут справедливы равенства:

$f^{*} (y) = \frac{2 f (x)}{| \nabla f (x) |^{2}}$ , $\vec{y} = \vec{x} - 2 f (x) \frac{\vec{\nabla} f (x)}{| \nabla f (x) |^{2}}$ ,

$f (x) = \frac{2 f^{*} (y)}{| \nabla f^{*} (y) |^{2}}$ , $\vec{x} = \vec{y} - 2 f^{*} (y) \frac{\vec{\nabla} f^{*} (y)}{| \nabla f^{*} (y) |^{2}}$ (7)

Определение 3. Одномерная секционная кривизна конформно-плоской метрики $d s^{2} = \frac{d x^{2}}{f^{2} (x)}$ в задается формулой [16-18]:

$K_{1 / 2} (f, x, ξ) = f \frac{d^{2} f}{d ξ^{2}} - \frac{1}{2} | \nabla f |^{2}$ . (8)

здесь $\frac{d^{2} f}{d ξ^{2}}$ – вторая производная функции в точке $x \in R^{n}$ вдоль единичного вектора $ξ$ , $\nabla f$ – градиент функции $f$ в $R^{n}$ . Формула верна как в плоском случае, так и для единичной сферы, в этом случае функция $f : S^{n} \to R$ продолжается по однородности на $R^{n + 1}$ , $x \in S^{n} \subset R^{n + 1}$ , $ξ$ – единичный касательный к сфере в точке x вектор, $\nabla f$ – градиент функции в $R^{n + 1}$ .

Определение 4. Формулу (1) можно распространить на конформно-плоские метрики, определенные на единичной n-мерной сфере $S^{n} \subset R^{n + 1}$ в форме:

$f^{*} (y) = \underset{x_{e} S^{n}}{m a x} \frac{P x - y P^{2}}{2 f (x)}$ , или $h^{*} (y) = \underset{x_{e} S^{n}}{m a x} \frac{P x - y P}{\sqrt{2} h (x)}$ , (9)

здесь $h (x) = \sqrt{f (x)}$ – положительная конформно-выпуклая функция на сфере [6], то есть функция, для которой конформно-плоская метрика $d s^{2} = \frac{d x^{2}}{f^{2} (x)}$ имеет неотрицательную одномерную секционную кривизну. Равносильное условие функции на $h (x)$ имеет вид:

$h (x) \leq \frac{h (x_{2}) ‖ x - x_{1} ‖}{‖ x_{2} - x_{1} ‖} + \frac{h (x_{1}) ‖ x - x_{2} ‖}{‖ x_{2} - x_{1} ‖}$

для произвольных точек $x_{2}, x, x_{1} \in S^{n}$ , $‖ y - x ‖$ – хордовое расстояние между точками на сфере, $h^{*} (y)$ , $y \in S^{n}$ – функция, задающая двойственную или полярную метрику $d s^{*} = \frac{d y}{h^{* 2} (y)}$ . Причем основные свойства (инволютивность и т. д.) сохраняются. В работе [8] было предложено также назвать преобразование (9) преобразованием Лежандра функции $f (x)$ , $x \in S^{n}$ .

Определение 5. Обобщая эти понятия, приходим к определению обобщенного преобразования Лежандра с формулой:

$h^{*} (y_{j}) = \underset{x_{i} \in S^{n}}{m a x} \frac{||y_{j} - x_{i}||}{\sqrt{2} h (x_{i})}$ , (10)

где X – компактное метрическое пространство, A(x, y) неотрицательная непрерывная симметричная функция $(x, y) \in X \times X$ , $A (x, x) \equiv 0$ , $, ℎ (𝑥)$ – положительная непрерывная функция, $h^{*} (y)$ её преобразование Лежандра. Функцию $A (x, y)$ будем называть ядром преобразования.

С вычислительной точки зрения формула (10) имеет дискретный вид;

$h^{*} (y_{j}) = \underset{x_{i} \in S^{n}}{m a x} \frac{||y_{j} - x_{i}||}{\sqrt{2} h (x_{i})}$ , (11)

где {x_i} – конечная сетка точек на сфере. В данной работе предлагается дальнейшее абстрактное обобщение формулы (11) для идемпотентной математики.

Определение 6. Пусть n>1, $R_{n}^{+}$ – множество наборов $f = {f_{i}}$ , i=1, ..., n положительных чисел, $A = ‖ A_{j i} ‖$ $i, j = 1, \dots, n$ – симметричная квадратная матрица неотрицательных чисел с нулевой диагональю. Обозначим через L_A отображение множества $R_{n}^{+}$ в себя $L_{A} : R_{n}^{+} \to R_{n}^{+}$ , определяемое формулой $L_{A} [{f_{i}}] = {f_{j}^{*}}$ , где

$f_{j}^{*} = \underset{i}{m a x} \frac{A_{j i}}{f_{i}}$ . (12)

Замечание. В формуле (12) участвуют только две операции над неотрицательными числами – умножение (деление) и max (min), с помощью функции log это множество чисел можно отождествить с идемпотентным полукольцом $R_{m a x}$ см. [9[, [7].

Теорема 1. Преобразование (12) полукольца обладает основными свойствами классического преобразования Лежандра:

справедливо неравенство $f_{j}^{*} \cdot f_{i} \geq A_{j i}$ ,
$f_{i}^{* * *} = f_{i}^{*}$ $i = 1, \dots, n$ ,
$f_{i}^{* *} = f_{i}^{}$ $i = 1, \dots, n$ .

где ${f_{i}^{*}} = L_{A} [{f_{i}}]$ , ${f_{i}^{* *}} = L_{A} [{f_{i}^{*}}],$ , ${f_{i}^{* * *}} = L_{A} [{f_{i}^{* *}}],$ .

Пример 1. Рассмотрим, как выглядит при , пусть матрица имеет вид:

$A = [\begin{matrix} 0 & a & b \\ a & 0 & c \\ b & c & 0 \end{matrix}]$

Тогда ${f_{i}^{*}} = L_{A} [{f_{i}}]$ , ${f_{i}^{* *}} = L_{A} [{f_{i}^{*}}],$ имеют вид:

$f_{1}^{*} = m a x (\frac{a}{f_{2}}, \frac{b}{f_{3}}), f_{1}^{* *} = m a x (a m i n (\frac{f_{1}}{a}, \frac{f_{3}}{c}), b m i n (\frac{f_{1}}{b}, \frac{f_{2}}{c}))$ ,

$f_{2}^{*} = m a x (\frac{a}{f_{1}}, \frac{c}{f_{3}}), f_{2}^{* *} = m a x (c m i n (\frac{f_{1}}{b}, \frac{f_{2}}{c}), a m i n (\frac{f_{2}}{a}, \frac{f_{3}}{b}))$ ,

$f_{2}^{*} = m a x (\frac{b}{f_{1}}, \frac{c}{f_{2}}), f_{3}^{* *} = m a x (c m i n (\frac{f_{1}}{a}, \frac{f_{3}}{c}), b m i n (\frac{f_{2}}{a}, \frac{f_{3}}{b}))$

Замечание. Как показали численные эксперименты, если матрица A в теореме 1 не обладает требуемыми свойствами, то теорема не верна.

Гипотеза. Теорема 1 справедлива в случае абстрактного полукольца.

Пример 2. Преобразование Лежандра периодического сигнала (временного ряда). Будем трактовать временной ряд как положительную функцию на единичной окружности и сопоставим ей конформно-плоскую метрику (меру) $d s = \frac{d φ}{h^{2} (φ)}$ на окружности S¹, здесь $h (ϕ)$ – периодическая функция. Формула (11) примет вид:

$h^{*} (ψ_{j}) = m a x_{i} \frac{a b s [\sin (\frac{ψ_{j} - φ_{i}}{2})]}{\sqrt{2} h (φ_{i})}$ ,

На рисунках 1, 2 приведены примеры преобразования Лежандра временного ряда P0. На рис. 1 P1=P0^* – нижний «выпуклый» огибающего ряда P0.

Рисунок 1 к примеру 2: $P 0 \geq P 0^{*} = P 1$

Рисунок 2 к примеру 2: $P 2 = {- P 0}^{*} \geq P 0 \geq P 0^{*}$

Код в системе MATLAB к примеру 2 n=1000.

Заключение

Candidate of Physical and Mathematical Sciences, Associate Professor of the Institute of Digital Economy

Russian Federation

References

Applications of Legendre-Fenchel transformation to computer vision problems / A. Handa, R. A. Newcombe, A. Angeli, A. J. Davison // Imperial College London. – URL: http://www.doc.ic.ac.uk/ahanda/ (Date of request: 07.10.2020).
Abadi, M. Legendre Spectrum for texture classification / M. Abadi, E. Grandchamp. – doi: 10.1109/ICOSP.2006.345588 // IEEE Xplore. – URL: https://ieeexplore.ieee.org/document/4129069/;jsessionid=sIMbogTUpBwmSOpZCPcsYfzumJzUh9GmIauZEX9Ta1GDAhBmNXot!794090673 (Date of request: 07.10.2020).
Implementation of the Legendre transform for the muon track segment reconstruction in the ATLAS MDT chambers / M. S. Bachtis [et al.]. – doi: 10.1109/NSSMIC.2007.4436434 // ResearchGate. – URL: https://www.researchgate.net/publication/251849047_Implementation_of_the_Legendre_transform_for_the_Muon_track_segment_reconstruction_in_the_ATLAS_MDT_chambers (Date of request: 07.10.2020).
Владимиров, В. С. Преобразование Лежандра выпуклых функций / В. С. Владимиров. – Текст : непосредственный // Математические заметки. – 1967. – Т. 1, № 6. – С. 448–452.
Родионов, Е. Д. Полярное преобразование конформно-плоских метрик / Е. Д. Родионов, В. В. Славский. – Текст : непосредственный // Математические труды. – 2017. – Т. 20, № 2. – С. 120–138.
Kurkina, M. V. Conformally convex functions and conformally flat metrics of nonnegative curvature / M. V. Kurkina, V. V. Slavsky, E. D. Rodionov // Doklady Mathematics. – 2015. – Vol. 91, № 3. – Р. 287–289.
Литвинов, Г. Л. Идемпотентная математика и интервальный анализ / Г. Л. Литвинов, В. П. Маслов, А. Н. Соболевский. – Текст : непосредственный // Вычислительные технологии. – 2001. – Т. 6, № 6. – С. 47–70.
Куркина, М. В. Об изменении кривизны конформно-плоской метрики при преобразовании Лежандра / М. В. Куркина. – Текст : непосредственный // Известия Алтайского государственного университета. – 2018. – № 4 (102). – С. 88–92.
Sergeev, S. CSR expansions of matrix powers in max algebra / S. Sergeev, H. Schneider // Transactions of the American Mathematical Society. – 2012. – Vol. 364, № 11. – Р. 5969–5994.
Славский, В. В. Конформно плоские метрики ограниченной кривизны на n -мерной сфере. Исследования по геометрии ''в целом'' и математическому анализу. – Новосибирск, 1987. – Т. 9.
Hertrich-Jeromin, U. Introduction to Mobius Differential Geometry. London mathematical society lecture note series. / U. Hertrich-Jeromin. – Cambridge University Press, 2003. – 413 р.
Решетняк, Ю. Г. Теоремы устойчивости в геометрии и анализе / Ю. Г. Решетняк. – 2-е издание, переработанное и дополненное. – Новосибирск : Издательство института математики,1996. – 424 с. – ISBN 5-86134-017-Х. – Текст : непосредственный.
Топоногов, В. А. Дифференциальная геометрия кривых и поверхностей / В. А. Топоногов. – Москва : Физматкнига, 2012. – 223 с. – ISBN 978-5-89155-213-5. – Текст : непосредственный.
Slavskii, V. V. Conformally flat metrics and the geometry of the pseudo-Euclidean space / V. V. Slavskii // Siberian Mathematical Journal. – 1994. – Vol. 35. – № 3. – P. 605–613.
Славский, В. В. Оценка коэффициента квазиконформности области через кривизну квазигиперболической метрики / В. В. Славский. – Текст : непосредственный // Сибирский математический журнал. – 1999. – Т. 40, № 4. – С. 801–818.
Однородные пространства: теория и приложения : монография / В. В. Балащенко, Никоноров, Е. Д. Родионов, В. В. Славский. – Ханты-Мансийск : Полиграфист, 2008. – 279 с. – ISBN 978-5-89846-794-4. – Текст : непосредственный.
Родионов, Е. Д. Одномерная секционная кривизна римановых многообразий / Е. Д. Родионов, В. В. Славский. – Текст : непосредственный // Доклады академии наук. – 2002. – Т. 387, № 4. – С. 454.
Nikonorov, Yu. G. Geometry of homogeneoues Riemannian manifolds / Yu. G. Nikonorov, E. D. Rodionov, V. V. Slavskii // Journal of Mathematical Scieces. – 2007. – Vol. 146, № 6. – P. 6313–6390.