Свёртка (математический анализ)

Свёртка, конволюция — операция в функциональном анализе, которая при применении к двум функциям $f$ и $g$ возвращает третью функцию, соответствующую взаимнокорреляционной функции $f(x)$ и $g(-x)$ . Операцию свёртки можно интерпретировать как «схожесть» одной функции с отражённой и сдвинутой копией другой. Понятие свёртки обобщается для функций, определённых на произвольных измеримых пространствах, и может рассматриваться как особый вид интегрального преобразования. В дискретном случае свёртка соответствует сумме значений $f$ с коэффициентами, соответствующими смещённым значениям $g$ , то есть $(f*g)(x)=f(1)g(x-1)+f(2)g(x-2)+f(3)g(x-3)+\dots$

Свёртка двух прямоугольных импульсов: в результате даёт треугольный импульс.

Свёртка прямоугольного импульса (входного сигнала) с импульсным откликом RC цепи

Определение

Пусть $f,g:\mathbb {R} ^{n}\to \mathbb {R}$ — две функции, интегрируемые относительно меры Лебега на пространстве $\mathbb {R} ^{n}$ . Тогда их свёрткой называется функция $f*g:\mathbb {R} ^{n}\to \mathbb {R}$ , определённая формулой

(f*g)(x)\

{\stackrel {\mathrm {def} }{=}}\ \int \limits _{\mathbb {R} ^{n}}f(y)\,g(x-y)\,dy=\int \limits _{\mathbb {R} ^{n}}f(x-y)\,g(y)\,dy.

В частности, при $n=1$ формула принимает вид

(f*g)(x)\

{\stackrel {\mathrm {def} }{=}}\ \int \limits _{-\infty }^{\infty }f(y)\,g(x-y)\,dy=\int \limits _{-\infty }^{\infty }f(x-y)\,g(y)\,dy.

Свёртка $(f*g)(x)$ определена при почти всех $x\in {\mathbb {R} ^{n}}$ и интегрируема.

В случае, когда $x\in \mathbb {R}$ , а функции $f(x),~g(x)$ определены на промежутке $[0,+\infty )$ , свёртку можно записать в виде

(f*g)(x)\

{\stackrel {\mathrm {def} }{=}}\ \int \limits _{0}^{x}f(y)\,g(x-y)\,dy=\int \limits _{0}^{x}f(x-y)\,g(y)\,dy.

Впервые интегралы, являющиеся свёрткой двух функций, встречаются в трудах Леонарда Эйлера (1760-е годы); позднее свёртка появляется у Лапласа, Лакруа, Фурье, Коши, Пуассона и других математиков. Обозначение свёртки функций при помощи звёздочки впервые предложил Вито Вольтерра в 1912 году на своих лекциях в Сорбонне (опубликованы годом позже)[1].

Свойства

Коммутативность:

f*g=g*f

.

Ассоциативность:

f*(g*h)=(f*g)*h

.

Линейность (дистрибутивность по сложению и ассоциативность с умножением на скаляр):

(f_{1}+f_{2})*g=f_{1}*g+f_{2}*g

,

f*(g_{1}+g_{2})=f*g_{1}+f*g_{2}

,

(af)*g=a(f*g)=f*(ag),\quad \forall a\in \mathbb {R}

.

Правило дифференцирования:

\mathrm {D} (f*g)=\mathrm {D} f*g=f*\mathrm {D} g

,

где $\mathrm {D} f$ обозначает производную функции $f$ по любой переменной.

Преобразование Лапласа:

{\mathcal {L}}\{f(x)*g(x)\}={\mathcal {L}}\{f(x)\}\cdot {\mathcal {L}}\{g(x)\}

.

Свойство фурье-образа:

{\mathfrak {F}}[f*g]={\mathfrak {F}}[f]\cdot {\mathfrak {F}}[g]

,

где ${\mathfrak {F}}[]$ обозначает преобразование Фурье функции.

Если ${\mathcal {W}}$ является матрицей дискретного преобразования Фурье, то:

{\mathcal {W}}(C^{(1)}x\ast C^{(2)}y)=({\mathcal {W}}C^{(1)}\bullet {\mathcal {W}}C^{(2)})(x\otimes y)={\mathcal {W}}C^{(1)}x\circ {\mathcal {W}}C^{(2)}y

,

где $\bullet$ — символ торцевого произведения матриц[2][3][4][5][6], $\otimes$ обозначает произведение Кронекера, $\circ$ — символ произведения Адамара (тождество является следствием свойств отсчётного скетча[7]).

Пример

График функции

{\color {Red}g(x)}

— количество выпавшего снега в килограммах на начало часа.

Пусть стоит задача вычислить, как будет изменяться количество снега на каком-либо участке земли в зависимости от времени. Решение этой задачи можно разделить на два этапа:

построить модель выпадения снега и модель таяния снега.
каким-то образом соединить эти две модели в одну.
График ${\color {Blue}f(x)}$ зависимости количества нерастаявшего снега от времени прошедшего с момента его выпадения.

Задачи первого этапа решаются путём наблюдений и опытов, а задачи второго этапа — свёрткой получившихся на первом этапе моделей.

Пусть в результате решения задачи на первом этапе было построено две зависимости (математические модели):

зависимость количества выпавшего снега от текущего времени ${\color {Red}g(t)}$ ,
зависимость доли нерастаявшего снега от времени, прошедшего с момента его выпадения ${\color {Blue}f(\tau )}$ .

Если бы снег не начинал таять, количество всех выпавших осадков $G$ можно было бы посчитать путём сложения в дискретном случае:

G=\sum _{t=0}^{T}g(t)

,

или путём интегрирования в случае непрерывном:

G=\int \limits _{0}^{T}g(t)\,dt

.

Но в данном случае таяние снега имеет место и, более того, оно зависит не только от текущего общего количества снега, но и от того, в какой момент времени выпал этот конкретный объём снега. Так снег, выпавший две недели назад, может уже испариться, в то время как снег, выпавший полчаса назад, ещё будет лежать и даже не начнёт подтаивать.

Получается, что для снега, выпавшего в разное время, нужно построить свою модель таяния и как-то сложить все эти модели вместе.

Для этих целей и можно использовать понятие математической свёртки. Пусть в момент времени $t$ рассматривается снег, который выпал в момент времени $\tau$ , тогда

$\tau$ — время выпадения снега. Например, 13:00;
${\color {Red}g(\tau )}$ — количество выпавшего в момент ${\tau }$ снега. Например, 7 кг;
$t$ — момент времени, для которого нам нужно узнать состояние выпавшего в $\tau$ снега. Например, 15:00;
$t-\tau$ — количество времени, прошедшее с момента выпадения до момента расчёта оставшейся доли снега. То есть 15:00 − 13:00;
${\color {Blue}f(t-\tau )}$ — доля снега, которая не растаяла после того, как пролежала $t-\tau$ часов.

Нужно для каждого количества ${\color {Red}g(\tau )}$ снега, выпавшего в момент времени $\tau$ , сложить множество моделей $f(t-\tau )$ в одну функцию. Если это сделать, получится сумма в дискретном случае:

w(t)=\sum \limits _{\tau =0}^{t}g(\tau )f(t-\tau ),

или интеграл в непрерывном:

w(t)=\int \limits _{\tau =0}^{t}g(\tau )f(t-\tau )d\tau .

Графически функция $w(t)$ изображена ниже, где разными цветами представлены вклады каждой кучи снега из графика ${\color {Red}g(x)}$ .

График функции

w(t)

, где разным цветом представлен вклад каждой кучи снега (цвета вкладов соответствуют цветам куч выпавшего снега на графике

{\color {Red}g(x)}

выше)

Функция $w(t)$ полностью моделирует поведение снега, выпавшего согласно модели ${\color {Red}g(x)}$ . Так, на графике выше видно, что общее количество снега увеличивается тремя скачками, но снег начинает таять сразу, не дожидаясь выпадения других осадков.

Свёртка на группах

Пусть $G$ — группа, оснащённая мерой $m$ , и $f,g:G\to \mathbb {R}$ — две функции, определённые на $G$ . Тогда их свёрткой называется функция

f*g(x)=\int \limits _{G}f(y)\,g\left(xy^{-1}\right)\,m(dy),\quad \forall x\in G.

Свёртка мер

Пусть есть борелевское пространство $(\mathbb {R} ,{\mathcal {B}}(\mathbb {R} ))$ и две меры ${\displaystyle \mu ,\nu$ . Тогда их свёрткой называется мера

\mu *\nu (A)=\mu \otimes \nu \left(\{(x,y)\in \mathbb {R} ^{2}\mid x+y\in A\}\right),\quad \forall A\in {\mathcal {B}}(\mathbb {R} ),

где $\mu \otimes \nu$ обозначает произведение мер $\mu$ и $\nu$ .

Свойства

Пусть $\mu ,\nu$ абсолютно непрерывны относительно меры Лебега $m$ . Обозначим их производные Радона — Никодима:

f_{\mu }={\frac {d\mu }{dm}},\quad f_{\nu }={\frac {d\nu }{dm}}.

Тогда $\mu *\nu$ также абсолютно непрерывна относительно $m$ , и её производная Радона — Никодима $f_{\mu *\nu }={\frac {d\mu *\nu }{dm}}$ имеет вид

f_{\mu *\nu }=f_{\mu }*f_{\nu }.

Если $\mu ,\nu$ — вероятностные меры, то $\mu *\nu$ также является вероятностной мерой.

Свёртка распределений

Если $\mathbb {P} ^{X},\mathbb {P} ^{Y}$ — распределения двух независимых случайных величин $X$ и $Y$ , то

\mathbb {P} ^{X+Y}=\mathbb {P} ^{X}*\mathbb {P} ^{Y},

где $\mathbb {P} ^{X+Y}$ — распределение суммы $X+Y$ . В частности, если $X,Y$ абсолютно непрерывны и имеют плотности $f_{X},f_{Y}$ , то случайная величина $X+Y$ также абсолютно непрерывна и её плотность имеет вид:

f_{X+Y}=f_{X}*f_{Y}.

См. также

Примечания

Domínguez A. A History of the Convolution Operation // IEEE Pulse. — 2015. — Vol. 6, no. 1. — P. 38—49.
Slyusar, V. I. (December 27, 1996). “End products in matrices in radar applications” (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53.
Slyusar, V. I. (1997-05-20). “Analytical model of the digital antenna array on a basis of face-splitting matrix products” (PDF). Proc. ICATT-97, Kyiv: 108—109.
Slyusar, V. I. (1997-09-15). “New operations of matrices product for applications of radars” (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74.
Slyusar, V. I. (March 13, 1998). “A Family of Face Products of Matrices and its Properties” (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379—384. DOI:10.1007/BF02733426.
Slyusar, V. I. (2003). “Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels” (PDF). Radioelectronics and Communications Systems. 46 (10): 9—17.
(2013) «Fast and scalable polynomial kernels via explicit feature maps» in SIGKDD international conference on Knowledge discovery and data mining., Association for Computing Machinery. DOI:10.1145/2487575.2487591.

Литература

Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа, — М.: Наука, 2004 (7-е изд.).
Ширяев А. Н. Вероятность, — М.: Наука. 1989.
Напалков В. В. Уравнения свертки в многомерных пространствах. — М., Наука, 1982. — Тираж 3500 экз. — 240 с.

Ссылки

Java-Applet
Java-Applet
Линейная и циклическая свертка (рус.). Дата обращения: 15 ноября 2010.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Domínguez A. A History of the Convolution Operation // IEEE Pulse. — 2015. — Vol. 6, no. 1. — P. 38—49.

[slyusar-2] Slyusar, V. I. (December 27, 1996). “End products in matrices in radar applications” (PDF). Radioelectronics and Communications Systems.– 1998, Vol. 41; Number 3: 50—53.

[slyusar1-3] Slyusar, V. I. (1997-05-20). “Analytical model of the digital antenna array on a basis of face-splitting matrix products” (PDF). Proc. ICATT-97, Kyiv: 108—109.

[DIPED-4] Slyusar, V. I. (1997-09-15). “New operations of matrices product for applications of radars” (PDF). Proc. Direct and Inverse Problems of Electromagnetic and Acoustic Wave Theory (DIPED-97), Lviv.: 73—74.

[slyusar2-5] Slyusar, V. I. (March 13, 1998). “A Family of Face Products of Matrices and its Properties” (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379—384. DOI:10.1007/BF02733426.

[general-6] Slyusar, V. I. (2003). “Generalized face-products of matrices in models of digital antenna arrays with nonidentical channels” (PDF). Radioelectronics and Communications Systems. 46 (10): 9—17.

[ninh-7] (2013) «Fast and scalable polynomial kernels via explicit feature maps» in SIGKDD international conference on Knowledge discovery and data mining., Association for Computing Machinery. DOI:10.1145/2487575.2487591.