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

Cover Page

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.


Full Text

Введение

Пусть функция f:RnR задана на евклидовом арифметическом пространстве. Преобразованием Юнга – Фенхеля функции f называют функцию f*, где

f*(ξ)=supx[(ξ, x) -f(x)] (1)

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

(x,ξ)=f(x)+f*(ξ), где ξ=f(x),  x=f*(ξ)

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

xξ=f(x)+f*(ξ)ξ=df(x)dx, x=df*(ξ)dξ/

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

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

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

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

В данной части мы используем обозначения и результаты работы [5]. Пусть R – числовая прямая, Rn+1 – евклидово (n+1) -мерное арифметическое пространство, Mn+2=Rn+1×R – псевдоевклидово пространство, скалярный квадрат вектора w=[x,ζ]Mn+2 в котором равен w2=|x|2-ζ2, где |x|2 – скалярный квадрат вектора xRn+1. Обозначим через

C+={[x,ζ]Mn+2:|x|2-ζ2=0, ζ>0},

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

Лемма 1. Пусть на единичной сфере SnRn+1 задана конформно-плоская метрика

s2=dx2f2(x)xSnRn+1,

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

Z:xSn[xf(x), 1f(x)]C+. (2)

Образ Z(Sn)=FC+ – пространственно подобная n -мерная поверхность. Будем отождествлять конформно-плоскую метрику с поверхностью F. Предположим, что функция  достаточно гладкая, тогда поверхность  регулярна, и в каждой точке Z(x)F определено касательное n -мерное пространство Tx(F). Существует единственный вектор Z*(x)C+ такой, что

Z,Z*=-1, Z*Tx(F), (3)

где ортогональность понимается относительно скалярного произведения в Mn+2.

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

Z*(x)=[-f+|f|22fx, |f|22f], (4)

где xSnRn+1, f градиент функции f в пространстве Rn+1.

 Определение 1. Если точка ZF пробегает поверхность F, то точка Z* пробегает двойственную поверхность F*. Соответствующую конформно-плоскую метрику ds*2=dy2f*2(y), ySn будем называть полярной к исходной метрике [14]. Сравнивая формулы (2) и (4), имеем:

-f+|f|22fx, |f|22fyf*(y), 1f*(y).

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

f*(y)=2f(x)|f|2, y=x-2f(x)f|f|2. (5)

Лемма 3. Пусть f:Rn+1R произвольная однородная степени один функция на Rn+1. Отображение Hf:SnSn, определяемое формулой

Hf:xSnx-2f(x)f|f|2Sn, (6)

сохраняет норму вектора: |Hf(x)|=|x|.

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

f*(y)=2f(x)|f|2|x=Hf-1(y).

Замечание. Из определения (1) следует двойственность метрики ds2=dx2f2(x), xSn и метрики ds*2=dy2f*2(y), ySn. Поэтому при наличии соответствующей регулярности функции f*(y) будут справедливы равенства:

f*(y)=2f(x)|f(x)|2, y=x-2f(x)f(x)|f(x)|2,

f(x)=2f*(y)|f*(y)|2, x=y-2f*(y)f*(y)|f*(y)|2(7)

Определение 3. Одномерная секционная кривизна конформно-плоской метрики ds2=dx2f2(x) в  задается формулой [16-18]:

K1/2(f,x,ξ)=fd2fdξ2-12|f|2. (8)

здесь d2fdξ2 – вторая производная функции в точке xRn вдоль единичного вектора ξ, f – градиент функции f в Rn. Формула верна как в плоском случае, так и для единичной сферы, в этом случае функция f:SnR продолжается по однородности на Rn+1, xSnRn+1ξ – единичный касательный к сфере в точке x вектор, f – градиент функции в Rn+1.

Определение 4. Формулу (1) можно распространить на конформно-плоские метрики, определенные на единичной  n-мерной сфере SnRn+1 в форме:

f*(y)=maxxeSnPx-yP22f(x), или h*(y)=maxxeSnPx-yP2h(x), (9)

здесь h(x)=f(x) – положительная конформно-выпуклая функция на сфере [6], то есть функция, для которой конформно-плоская метрика ds2=dx2f2(x) имеет неотрицательную одномерную секционную кривизну. Равносильное условие функции на h(x) имеет вид:

h(x)h(x2)x-x1x2-x1+h(x1)x-x2x2-x1

для произвольных точек x2, x, x1Sn, y-x  – хордовое расстояние между точками на сфере, h*(y), ySn – функция, задающая двойственную или полярную метрику ds*=dyh*2(y). Причем основные свойства (инволютивность и т. д.) сохраняются. В работе [8] было предложено также назвать преобразование (9) преобразованием Лежандра функции f(x), xSn.

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

h*(yj)=maxxiSnyj-xi2h(xi), (10)

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

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

h*(yj)=maxxiSnyj-xi2h(xi), (11)

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

Определение 6. Пусть n>1, Rn+ – множество наборов f={fi}, i=1, ..., n положительных чисел, A=Aji i, j=1, , n – симметричная квадратная матрица неотрицательных чисел с нулевой диагональю. Обозначим через LA отображение множества Rn+ в себя LA:Rn+Rn+, определяемое формулой LA[{fi}]={fj*}, где

fj*=maxiAjifi. (12)

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

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

  • справедливо неравенство fj*fiAji,
  • fi***=fi* i=1, , n,
  • fi**=fi i=1, , n.

где {fi*}=LA[{fi}], {fi**}=LA[{fi*}],{fi***}=LA[{fi**}],.

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

A=0aba0cbc0

Тогда {fi*}=LA[{fi}]{fi**}=LA[{fi*}], имеют вид:

f1*=max af2, bf3, f1**=max a minf1a, f3c, b minf1b,f2c,

f2*=maxaf1,cf3, f2**=max c minf1b, f2c, a minf2a, f3b,

f2*=maxbf1, cf2, f3**=maxc minf1a, f3c, b minf2a, f3b

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

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

Пример 2. Преобразование Лежандра периодического сигнала (временного ряда). Будем трактовать временной ряд как положительную функцию на единичной окружности и сопоставим ей конформно-плоскую метрику (меру) ds=dφh2(φ) на окружности S1, здесь h(ϕ) – периодическая функция. Формула (11) примет вид:

h*(ψj)=maxiabssinψj-φi22h(φi),

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

 

Рисунок 1 к примеру 2: P0P0*=P1

   

Рисунок 2 к примеру 2: P2=-P0*P0P0*

 

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

Заключение

В данной работе по аналогии с полярным преобразованием конформно-плоской метрики (Родионов Е. Д., Славский В. В.) и классическим преобразованием Лежандра строится идемпотентный аналог преобразования Лежандра. Приведена программа в системе MATLAB, реализующая численное преобразование временных рядов. В дальнейшем предполагается использовать её возможности при цифровой обработке сигналов и изображений и в задачах распознавания временных рядов.

About the authors

Maria V. Kurkina

Yugra State University

Author for correspondence.
Email: mavi@inbox.ru

Russian Federation

Candidate of Technical Sciences, Associate Professor of the Institute of Digital Economy

Sergey P. Semenov

Yugra State University

Email: semenovsp@bk.ru

Russian Federation

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

Viktor V. Slavsky

Yugra State University

Email: slavsky2004@mail.ru

Russian Federation

Doctor of Physical and Mathematical Sciences, Professor of the Institute of Digital Economy

Olga V. Samarina

Yugra State University

Email: samarina_ov@mail.ru

Russian Federation

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

Olga A. Petuhova

Yugra State University

Email: oa_petuhova@mail.ru

Russian Federation

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

Aleksey A. Petrov

Yugra State University

Email: a_petrov@ugrasu.ru

Russian Federation

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

Anton A. Finogenov

Yugra State University

Email: aafin@ya.ru

Russian Federation

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

Valeriy A. Samarin

Yugra State University

Email: vals_11111@mail.ru

Russian Federation

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

References

  1. 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).
  2. 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).
  3. 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).
  4. Владимиров, В. С. Преобразование Лежандра выпуклых функций / В. С. Владимиров. – Текст : непосредственный // Математические заметки. – 1967. – Т. 1, № 6. – С. 448–452.
  5. Родионов, Е. Д. Полярное преобразование конформно-плоских метрик / Е. Д. Родионов, В. В. Славский. – Текст : непосредственный // Математические труды. – 2017. – Т. 20, № 2. – С. 120–138.
  6. 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.
  7. Литвинов, Г. Л. Идемпотентная математика и интервальный анализ / Г. Л. Литвинов, В. П. Маслов, А. Н. Соболевский. – Текст : непосредственный // Вычислительные технологии. – 2001. – Т. 6, № 6. – С. 47–70.
  8. Куркина, М. В. Об изменении кривизны конформно-плоской метрики при преобразовании Лежандра / М. В. Куркина. – Текст : непосредственный // Известия Алтайского государственного университета. – 2018. – № 4 (102). – С. 88–92.
  9. 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.
  10. Славский, В. В. Конформно плоские метрики ограниченной кривизны на n -мерной сфере. Исследования по геометрии ''в целом'' и математическому анализу. – Новосибирск, 1987. – Т. 9.
  11. Hertrich-Jeromin, U. Introduction to Mobius Differential Geometry. London mathematical society lecture note series. / U. Hertrich-Jeromin. – Cambridge University Press, 2003. – 413 р.
  12. Решетняк, Ю. Г. Теоремы устойчивости в геометрии и анализе / Ю. Г. Решетняк. – 2-е издание, переработанное и дополненное. – Новосибирск : Издательство института математики,1996. – 424 с. – ISBN 5-86134-017-Х. – Текст : непосредственный.
  13. Топоногов, В. А. Дифференциальная геометрия кривых и поверхностей / В. А. Топоногов. – Москва : Физматкнига, 2012. – 223 с. – ISBN 978-5-89155-213-5. – Текст : непосредственный.
  14. 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.
  15. Славский, В. В. Оценка коэффициента квазиконформности области через кривизну квазигиперболической метрики / В. В. Славский. – Текст : непосредственный // Сибирский математический журнал. – 1999. – Т. 40, № 4. – С. 801–818.
  16. Однородные пространства: теория и приложения : монография / В. В. Балащенко, Никоноров, Е. Д. Родионов, В. В. Славский. – Ханты-Мансийск : Полиграфист, 2008. – 279 с. – ISBN 978-5-89846-794-4. – Текст : непосредственный.
  17. Родионов, Е. Д. Одномерная секционная кривизна римановых многообразий / Е. Д. Родионов, В. В. Славский. – Текст : непосредственный // Доклады академии наук. – 2002. – Т. 387, № 4. – С. 454.
  18. 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.

Supplementary files

Supplementary Files Action
1.
Figure 1

Download (35KB) Indexing metadata
2.
Figure 2

Download (42KB) Indexing metadata

Statistics

Views

Abstract - 50

PDF (Russian) - 29

Cited-By


Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2020 Kurkina M.V., Semenov S.P., Slavsky V.V., Samarina O.V., Petuhova O.A., Petrov A.A., Finogenov A.A., Samarin V.A.

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies