Свертка

Чтобы узнать о других значениях, см. «Свертка (значения)» .

Визуальное сравнение свертки, взаимной корреляции и автокорреляции . Для операций с функцией $f$, и приняв высоту $f$ равно 1,0, значение результата в 5 различных точках обозначено заштрихованной областью под каждой точкой. Симметрия $f$ это причина $f\star g$ и $g*f$ в этом примере идентичны.

В математике (в частности, функциональном анализе ) свертка — это математическая операция над двумя функциями ( $f$ и $g$), который создает третью функцию ( $f*g$). Термин «свертка» относится как к функции результата, так и к процессу ее вычисления. Он определяется как интеграл произведения двух функций после того, как одна из них отражается относительно оси Y и смещается. Интеграл оценивается для всех значений сдвига, создавая функцию свертки. Выбор того, какая функция будет отражена и сдвинута перед интегралом, не меняет интегрального результата (см. коммутативность ). Графически это выражает, как «форма» одной функции изменяется другой.

Некоторые особенности свертки аналогичны взаимной корреляции : для вещественнозначных функций непрерывной или дискретной переменной свертка ( $f*g$) отличается от взаимной корреляции ( $f\star g$) только в этом либо $f(x)$ или $g(x)$ отражается относительно оси Y в свертке; таким образом, это взаимная корреляция $g(-x)$ и $f(x)$, или $f(-x)$ и $g(x)$. Для комплекснозначных функций оператор взаимной корреляции является сопряженным оператором свертки.

Свертка имеет приложения, которые включают вероятность , статистику , акустику , спектроскопию , обработку сигналов и изображений , геофизику , инженерное дело , физику , компьютерное зрение и дифференциальные уравнения .

Свертку можно определить для функций в евклидовом пространстве и других группах (как алгебраические структуры ). Например, периодические функции , такие как преобразование Фурье с дискретным временем , могут быть определены на окружности и свернуты с помощью периодической свертки . (См. строку 18 в разделе DTFT § Свойства .) Дискретную свертку можно определить для функций на множестве целых чисел .

Обобщения свертки имеют приложения в области численного анализа и числовой линейной алгебры , а также при разработке и реализации фильтров с конечной импульсной характеристикой при обработке сигналов.

Вычисление обратной операции свертки известно как деконволюция .

Определение

Свертка $f$ и $g$ написано $f*g$, обозначая оператор символом $*$. Он определяется как интеграл произведения двух функций после того, как одна из них отражается относительно оси Y и смещается. По существу, это особый вид интегрального преобразования :

$(f*g)(t):=\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau .$

Эквивалентное определение (см. коммутативность ):

$(f*g)(t):=\int _{-\infty }^{\infty }f(t-\tau )g(\tau )\,d\tau .$

В то время как символ $t$ используется выше, он не обязательно представляет временную область. На каждом $t$формулу свертки можно описать как площадь под функцией $f(\tau )$ взвешенный по функции $g(-\tau )$ сдвинуто на сумму $t$. Как $t$ изменения, весовая функция $g(t-\tau )$ подчеркивает различные части функции ввода $f(\tau )$; Если $t$ является положительным значением, то $g(t-\tau )$ равно $g(-\tau )$ который скользит или смещается вдоль $\tau$-ось вправо (в сторону $+\infty$) по количеству $t$, а если $t$ является отрицательным значением, то $g(t-\tau )$ равно $g(-\tau )$ который скользит или смещается влево (в сторону $-\infty$) по количеству $|t|$.

Для функций $f$, $g$ поддерживается только на $[0,\infty )$ (т. е. ноль для отрицательных аргументов), пределы интегрирования могут быть усечены, что приведет к:

$(f*g)(t)=\int _{0}^{t}f(\tau )g(t-\tau )\,d\tau \quad \ {\text{for }}f,g:[0,\infty )\to \mathbb {R} .$

Многомерную формулировку свертки см. в области определения (ниже).

Обозначения

Общее соглашение об инженерных обозначениях:

$f(t)*g(t)\mathrel {:=} \underbrace {\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau } _{(f*g)(t)},$

который следует интерпретировать осторожно, чтобы избежать путаницы. Например, $f(t)*g(t-t_{0})$ эквивалентно $(f*g)(t-t_{0})$, но $f(t-t_{0})*g(t-t_{0})$ фактически эквивалентно $(f*g)(t-2t_{0})$.

Отношения с другими преобразованиями

Даны две функции $f(t)$ и $g(t)$ с двусторонними преобразованиями Лапласа (двустороннее преобразование Лапласа)

$F(s)=\int _{-\infty }^{\infty }e^{-su}\ f(u)\ {\text{d}}u$

и

$G(s)=\int _{-\infty }^{\infty }e^{-sv}\ g(v)\ {\text{d}}v$

соответственно, операция свертки $(f*g)(t)$ можно определить как обратное преобразование Лапласа произведения $F(s)$ и $G(s)$. Точнее,

${\begin{aligned}F(s)\cdot G(s)&=\int _{-\infty }^{\infty }e^{-su}\ f(u)\ {\text{d}}u\cdot \int _{-\infty }^{\infty }e^{-sv}\ g(v)\ {\text{d}}v\\&=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }e^{-s(u+v)}\ f(u)\ g(v)\ {\text{d}}u\ {\text{d}}v\end{aligned}}$

Позволять $t=u+v$ такой, что

${\begin{aligned}F(s)\cdot G(s)&=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }e^{-st}\ f(u)\ g(t-u)\ {\text{d}}u\ {\text{d}}t\\&=\int _{-\infty }^{\infty }e^{-st}\underbrace {\int _{-\infty }^{\infty }f(u)\ g(t-u)\ {\text{d}}u} _{(f*g)(t)}\ {\text{d}}t\\&=\int _{-\infty }^{\infty }e^{-st}(f*g)(t)\ {\text{d}}t\end{aligned}}$

Обратите внимание, что $F(s)\cdot G(s)$ является двусторонним преобразованием Лапласа $(f*g)(t)$. Аналогичный вывод можно сделать с помощью одностороннего преобразования Лапласа (одностороннее преобразование Лапласа).

Операция свертки также описывает выходные данные (с точки зрения входных данных) важного класса операций, известных как линейные инвариантные во времени (LTI). См. теорию систем LTI, чтобы узнать о выводе свертки как результата ограничений LTI. Что касается преобразований Фурье входных и выходных данных операции LTI, никаких новых частотных составляющих не создается. Существующие лишь изменяются (амплитуда и/или фаза). Другими словами, выходное преобразование представляет собой поточечное произведение входного преобразования с третьим преобразованием (известным как передаточная функция ). См. Теорему о свертке , где описан вывод этого свойства свертки. И наоборот, свертку можно получить как обратное преобразование Фурье поточечного произведения двух преобразований Фурье.

Визуальное объяснение

Выразите каждую функцию через фиктивную переменную. $\tau .$ Отразить одну из функций: $g(\tau )$ → $g(-\tau ).$ Добавьте смещение по времени t , которое позволяет $g(-\tau )$ скользить по $\tau$-ось. Если t — положительное значение, то $g(t-\tau )$ равно $g(-\tau )$ который скользит или смещается вдоль $\tau$-ось вправо (в сторону +∞ ) на величину t . Если t отрицательное значение, то $g(t-\tau )$ равно $g(-\tau )$ который скользит или смещается влево (в сторону -∞ ) на величину | т |. Начните t с −∞ и сдвиньте его до +∞ . Везде, где две функции пересекаются, найдите интеграл от их произведения. Другими словами, в момент времени t вычислите площадь под функцией $f(\tau )$ взвешивается с помощью весовой функции $g(t-\tau ).$ Результирующая форма сигнала (здесь не показана) представляет собой свертку функций f и g . Если $f(t)$ представляет собой единичный импульс , результат этого процесса просто $g(t)$. Формально: $\int _{-\infty }^{\infty }\delta (\tau )g(t-\tau )\,d\tau =g(t)$
В этом примере красный «импульс», $\ g(\tau ),$ это четная функция $(\ g(-\tau )=g(\tau )\ ),$ поэтому свертка эквивалентна корреляции. На снимке этого «фильма» показаны функции $g(t-\tau )$ и $f(\tau )$ (синим цветом) для некоторого значения параметра $t,$ которое условно определяется как расстояние вдоль $\tau$ ось от точки $\tau =0$ к центру красного импульса. Количество желтого цвета – это площадь изделия $f(\tau )\cdot g(t-\tau ),$ вычисляется с помощью интеграла свертки/корреляции. Фильм создается путем постоянного изменения $t$ и пересчитываем интеграл. Результат (показан черным цветом) является функцией $t,$ но отложено на той же оси, что и $\tau ,$ для удобства и сравнения.
В этом изображении $f(\tau )$ может представлять собой реакцию резисторно-емкостной цепи на узкий импульс, возникающий при $\tau =0.$ Другими словами, если $g(\tau )=\delta (\tau ),$ результат свертки просто $f(t).$ Но когда $g(\tau )$ — более широкий импульс (красный), ответ — «размазанная» версия $f(t).$ Это начинается в $t=-0.5,$ потому что мы определили $t$ как расстояние от $\tau =0$ ось к центру широкого импульса (вместо переднего фронта).

Исторические события

Одно из первых применений интеграла свертки появилось в теоремы выводе Даламбера Тейлора в книге «Исследование различных точек, важных для системы мира», опубликованной в 1754 году.

Также выражение типа:

$\int f(u)\cdot g(x-u)\,du$

используется Сильвестром Франсуа Лакруа на странице 505 его книги под названием «Трактат о различиях и рядах» , которая является последним из трех томов энциклопедической серии: Traité du Calcul Differential et du Calcul Integral , Chez Courcier, Paris, 1797–1800. Вскоре после этого операции свертки появляются в работах Пьера Симона Лапласа , Жана-Батиста Жозефа Фурье , Симеона Дени Пуассона и других. Сам этот термин не вошел в широкое употребление до 1950-х или 1960-х годов. До этого его иногда называли Faltung (что означает «складывание по -немецки »), произведение композиции , интеграл суперпозиции и Карсона интеграл . Тем не менее, оно появилось еще в 1903 году, хотя в более старых употреблениях это определение было довольно незнакомым.

Операция:

$\int _{0}^{t}\varphi (s)\psi (t-s)\,ds,\quad 0\leq t<\infty ,$

представляет собой частный случай композиционных произведений, рассмотренный итальянским математиком Вито Вольтеррой в 1913 году.

Круговая свертка

Основная статья: Круговая свертка

Когда функция g _T является периодической с периодом T , то для функций f , таких что f ∗ g _T существует, свертка также является периодической и идентична:

$(f*g_{T})(t)\equiv \int _{t_{0}}^{t_{0}+T}\left[\sum _{k=-\infty }^{\infty }f(\tau +kT)\right]g_{T}(t-\tau )\,d\tau ,$

где t ₀ — произвольный выбор. Суммирование называется периодическим суммированием функции f .

Когда g _T является периодическим суммированием другой функции g , тогда f ∗ g _T называется круговой или циклической сверткой f и g .

А если периодическое суммирование, указанное выше, заменить на f _T , операция называется периодической сверткой f _T и g _T .

Дискретная свертка

Дискретная 2D-анимация свертки

Для комплекснозначных функций f , g, на множестве Z целых чисел, дискретная свертка f определенных и g задается формулой:

$(f*g)[n]=\sum _{m=-\infty }^{\infty }f[m]g[n-m],$

или эквивалентно (см. коммутативность ):

$(f*g)[n]=\sum _{m=-\infty }^{\infty }f[n-m]g[m].$

Свертка двух конечных последовательностей определяется путем расширения последовательностей до функций с конечным носителем на множестве целых чисел. Если последовательности являются коэффициентами двух многочленов , то коэффициенты обычного произведения двух многочленов представляют собой свертку исходных двух последовательностей. Это известно как произведение Коши коэффициентов последовательностей.

Таким образом, когда g имеет конечный носитель в множестве $\{-M,-M+1,\dots ,M-1,M\}$ (представляющий, например, конечную импульсную характеристику ), можно использовать конечное суммирование:

$(f*g)[n]=\sum _{m=-M}^{M}f[n-m]g[m].$

Круговая дискретная свертка

Когда функция $g_{_{N}}$ является периодическим, с периодом $N,$ тогда для функций, $f,$ такой, что $f*g_{_{N}}$ существует, свертка также периодична и идентична :

$(f*g_{_{N}})[n]\equiv \sum _{m=0}^{N-1}\left(\sum _{k=-\infty }^{\infty }{f}[m+kN]\right)g_{_{N}}[n-m].$

Суммирование по $k$ называется периодическим суммированием функции $f.$

Если $g_{_{N}}$ представляет собой периодическое суммирование другой функции, $g,$ затем $f*g_{_{N}}$ известен как круговая свертка $f$ и $g.$

Когда ненулевая длительность обоих $f$ и $g$ ограничены интервалом $[0,N-1],$  $f*g_{_{N}}$ сводится к этим общим формам :

${\begin{aligned}\left(f*g_{N}\right)[n]&=\sum _{m=0}^{N-1}f[m]g_{N}[n-m]\\&=\sum _{m=0}^{n}f[m]g[n-m]+\sum _{m=n+1}^{N-1}f[m]g[N+n-m]\\[2pt]&=\sum _{m=0}^{N-1}f[m]g[(n-m)_{\bmod {N}}]\\[2pt]&\triangleq \left(f*_{N}g\right)[n]\end{aligned}}$         ( Уравнение 1 )

Обозначения $f*_{N}g$ для циклической свертки обозначает свертку по циклической группе целых чисел модулю N. по

Круговая свертка чаще всего возникает в контексте быстрой свертки с помощью алгоритма быстрого преобразования Фурье (БПФ).

Алгоритмы быстрой свертки

Во многих ситуациях дискретные свертки можно преобразовать в круговые свертки, чтобы для реализации вычислений можно было использовать быстрые преобразования со свойством свертки. Например, свертка последовательностей цифр — это операция ядра при умножении многозначных чисел, которую поэтому можно эффективно реализовать с помощью методов преобразования ( Knuth 1997 , §4.3.3.C; von zur Gathen & Gerhard 2003 , §8.2).

Уравнение 1 требует N арифметических операций на выходное значение и N ² операций для N выходов. Это можно значительно уменьшить с помощью любого из нескольких быстрых алгоритмов. Цифровая обработка сигналов и другие приложения обычно используют быстрые алгоритмы свертки, чтобы снизить стоимость свертки до O( N log N сложности ).

Наиболее распространенные алгоритмы быстрой свертки используют быстрого преобразования Фурье алгоритмы (БПФ) на основе теоремы круговой свертки . В частности, круговая свертка двух последовательностей конечной длины находится путем выполнения БПФ каждой последовательности, поточечного умножения и последующего выполнения обратного БПФ. Свертки определенного выше типа затем эффективно реализуются с использованием этого метода в сочетании с нулевым расширением и/или отбрасыванием частей вывода. Другие быстрые алгоритмы свертки, такие как алгоритм Шенхаге – Штрассена или преобразование Мерсенна, использовать быстрые преобразования Фурье в других кольцах . Метод Винограда используется как альтернатива БПФ. Это значительно ускоряет 1D, 2Д, и 3D свертка.

Если одна последовательность намного длиннее другой, нулевое расширение более короткой последовательности и быстрая круговая свертка не являются наиболее эффективным в вычислительном отношении доступным методом. Вместо этого разложение более длинной последовательности на блоки и свертка каждого блока позволяет использовать более быстрые алгоритмы, такие как метод перекрытия-сохранения и метод перекрытия-добавления . Гибридный метод свертки, сочетающий в себе блочный и FIR -алгоритмы, обеспечивает нулевую задержку ввода-вывода, что полезно для вычислений свертки в реальном времени.

Область определения

Свертка двух комплексных функций на R ^д сама по себе является комплексной функцией на R ^д , определяемый:

$(f*g)(x)=\int _{\mathbf {R} ^{d}}f(y)g(x-y)\,dy=\int _{\mathbf {R} ^{d}}f(x-y)g(y)\,dy,$

и корректно определен только в том случае, если f и g затухают на бесконечности достаточно быстро, чтобы интеграл существовал. Условия существования свертки могут быть непростыми, поскольку разрушение g на бесконечности можно легко компенсировать достаточно быстрым спадом f . Таким образом, вопрос о существовании может включать в себя разные условия на f и g :

Компактно поддерживаемые функции

Если f и g — с компактным носителем непрерывные функции , то их свертка существует, а также является непрерывной и компактной ( Hörmander 1983 , Глава 1). В более общем смысле, если одна из функций (скажем, f ) имеет компактный носитель, а другая локально интегрируема , то свертка f ∗ g корректно определена и непрерывна.

Свертка f и g также корректно определена, когда обе функции локально интегрируемы с квадратом на R и поддерживаются на интервале вида [ a , +∞) (или обе поддерживаются на [−∞, a ] ).

Интегрируемые функции

Свертка f и g существует, если f и g — интегрируемые по Лебегу функции в L ¹ ( Р ^д ) , и в этом случае f ∗ g также интегрируема ( Stein & Weiss 1971 , теорема 1.3). Это следствие теоремы Тонелли . Это справедливо и для функций из L ¹ , при дискретной свертке или, в более общем смысле, для свертки на любой группе .

Аналогично, если f ∈ L ¹ ( Р ^д ) и g ∈ L ^п ( Р ^д ) где 1 ≤ p ≤ ∞ , то f * g ∈ L ^п ( Р ^д ), и

$\|{f}*g\|_{p}\leq \|f\|_{1}\|g\|_{p}.$

В частном случае p = 1 это показывает, что L ¹ является банаховой алгеброй относительно свертки (и равенство двух сторон имеет место, если f и g неотрицательны почти всюду).

В более общем смысле, неравенство Юнга подразумевает, что свертка представляет собой непрерывное билинейное отображение между подходящими L ^п пространства. В частности, если 1 ≤ p , q , r ≤ ∞ удовлетворяют:

${\frac {1}{p}}+{\frac {1}{q}}={\frac {1}{r}}+1,$

затем

$\left\Vert f*g\right\Vert _{r}\leq \left\Vert f\right\Vert _{p}\left\Vert g\right\Vert _{q},\quad f\in L^{p},\ g\in L^{q},$

так что свертка является непрерывным билинейным отображением из L ^п × L ^д в Л ^р .Неравенство Юнга для свертки справедливо и в других контекстах (группа кругов, свертка на Z ). Предыдущее неравенство не является точным на действительной прямой: когда 1 < p , q , r < ∞ , существует константа B _{p , q} < 1 такая, что:

$\left\Vert f*g\right\Vert _{r}\leq B_{p,q}\left\Vert f\right\Vert _{p}\left\Vert g\right\Vert _{q},\quad f\in L^{p},\ g\in L^{q}.$

Оптимальное значение B _{p , q} было обнаружено в 1975 г. и независимо в 1976 г. см. неравенство Браскампа – Либа .

Более сильная оценка верна при условии, что 1 < p , q , r < ∞ :

$\|f*g\|_{r}\leq C_{p,q}\|f\|_{p}\|g\|_{q,w}$

где $\|g\|_{q,w}$ это слабый L ^д норма. Свертка также определяет билинейное непрерывное отображение. $L^{p,w}\times L^{q,w}\to L^{r,w}$ для $1<p,q,r<\infty$, в силу слабого неравенства Юнга:

$\|f*g\|_{r,w}\leq C_{p,q}\|f\|_{p,w}\|g\|_{r,w}.$

Функции быстрого распада

Помимо функций с компактным носителем и интегрируемых функций, свертку можно также выполнить с функциями, которые имеют достаточно быстрое затухание на бесконечности. Важная особенность свертки состоит в том, что если f и g оба быстро затухают, то f ∗ g также быстро затухает. В частности, если f и g — быстро убывающие функции , то и свертка f ∗ g тоже . В сочетании с тем фактом, что свертка коммутирует с дифференцированием (см. #Свойства ), отсюда следует, что класс функций Шварца замкнут относительно свертки ( Stein & Weiss 1971 , теорема 3.3).

Распределения

Основная статья: Распределение (математика)

Если f — гладкая функция с компактным носителем , а g — распределение, то f ∗ g — гладкая функция, определенная формулой

$\int _{\mathbb {R} ^{d}}{f}(y)g(x-y)\,dy=(f*g)(x)\in C^{\infty }(\mathbb {R} ^{d}).$

В более общем смысле, можно расширить определение свертки уникальным способом с помощью $\varphi$ то же, что и f выше, так что ассоциативный закон

$f*(g*\varphi )=(f*g)*\varphi$

остается справедливым в случае, когда f — распределение, а g — распределение с компактным носителем ( Hörmander 1983 , §4.2).

Меры

Сверткой любых двух борелевских мер µ и ν ограниченной вариации является мера $\mu *\nu$ определено ( Рудин 1962 )

$\int _{\mathbf {R} ^{d}}f(x)\,d(\mu *\nu )(x)=\int _{\mathbf {R} ^{d}}\int _{\mathbf {R} ^{d}}f(x+y)\,d\mu (x)\,d\nu (y).$

В частности,

$(\mu *\nu )(A)=\int _{\mathbf {R} ^{d}\times \mathbf {R} ^{d}}1_{A}(x+y)\,d(\mu \times \nu )(x,y),$

где $A\subset \mathbf {R} ^{d}$ представляет собой измеримое множество и $1_{A}$ – индикаторная функция $A$.

Это согласуется со сверткой, определенной выше, когда µ и ν рассматриваются как распределения, а также со сверткой L ¹ функции, когда µ и ν абсолютно непрерывны относительно меры Лебега.

Свертка мер также удовлетворяет следующей версии неравенства Юнга

$\|\mu *\nu \|\leq \|\mu \|\|\nu \|$

где норма – это полное изменение меры. Поскольку пространство мер ограниченной вариации является банаховым пространством , свертку мер можно обрабатывать стандартными методами функционального анализа , которые могут не применяться для свертки распределений.

Характеристики

Алгебраические свойства

Смотрите также: Алгебра свертки

Свертка определяет произведение в линейном пространстве интегрируемых функций. Это произведение удовлетворяет следующим алгебраическим свойствам, которые формально означают, что пространство интегрируемых функций с произведением, заданным сверткой, является коммутативной ассоциативной алгеброй без единицы ( Стрихарц 1994 , §3.3). Другие линейные пространства функций, такие как пространство непрерывных функций с компактным носителем, замкнуты относительно свертки и поэтому также образуют коммутативные ассоциативные алгебры.

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

$$f*g=g*f$$ Доказательство: По определению: $$(f*g)(t)=\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau$$ Изменение переменной интегрирования на $u=t-\tau$ результат следующий.

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

$$f*(g*h)=(f*g)*h$$ Доказательство: Это следует из использования теоремы Фубини (т. е. двойные интегралы можно вычислять как повторные интегралы в любом порядке).

Дистрибутивность

$$f*(g+h)=(f*g)+(f*h)$$ Доказательство. Это следует из линейности интеграла.

Ассоциативность со скалярным умножением

$$a(f*g)=(af)*g$$ для любого действительного (или комплексного) числа $a$.

Мультипликативная идентичность

Ни одна алгебра функций не обладает тождеством свертки. Отсутствие идентичности обычно не является серьезным неудобством, поскольку большинство наборов функций, над которыми выполняется свертка, могут быть свернуты с помощью дельта-распределения (унитарный импульс с центром в нуле) или, по крайней мере (как в случае с л ¹ ) допускают приближения к тождеству . Однако линейное пространство распределений с компактным носителем допускает тождество при свертке. Конкретно, $$f*\delta =f$$ где δ — дельта-распределение.

Обратный элемент

Некоторые распределения S имеют обратный элемент S ⁻¹ для свертки, которая тогда должна удовлетворять $$S^{-1}*S=\delta$$ откуда явная формула для S ⁻¹ можно получить.

Множество обратимых распределений образует абелеву группу при свертке.

Комплексное сопряжение

$${\overline {f*g}}={\overline {f}}*{\overline {g}}$$

Обращение времени

Если $q(t)=r(t)*s(t),$ затем $q(-t)=r(-t)*s(-t).$

Доказательство (с использованием теоремы о свертке ):

$q(t)\ {\stackrel {\mathcal {F}}{\Longleftrightarrow }}\ \ Q(f)=R(f)S(f)$

$q(-t)\ {\stackrel {\mathcal {F}}{\Longleftrightarrow }}\ \ Q(-f)=R(-f)S(-f)$

${\begin{aligned}q(-t)&={\mathcal {F}}^{-1}{\bigg \{}R(-f)S(-f){\bigg \}}\\&={\mathcal {F}}^{-1}{\bigg \{}R(-f){\bigg \}}*{\mathcal {F}}^{-1}{\bigg \{}S(-f){\bigg \}}\\&=r(-t)*s(-t)\end{aligned}}$

Связь с дифференциацией

$$(f*g)'=f'*g=f*g'$$ Доказательство:

${\begin{aligned}(f*g)'&={\frac {d}{dt}}\int _{-\infty }^{\infty }f(\tau )g(t-\tau )\,d\tau \\&=\int _{-\infty }^{\infty }f(\tau ){\frac {\partial }{\partial t}}g(t-\tau )\,d\tau \\&=\int _{-\infty }^{\infty }f(\tau )g'(t-\tau )\,d\tau =f*g'.\end{aligned}}$

Связь с интеграцией

Если ${\textstyle F(t)=\int _{-\infty }^{t}f(\tau )d\tau ,}$ и ${\textstyle G(t)=\int _{-\infty }^{t}g(\tau )\,d\tau ,}$ затем $$(F*g)(t)=(f*G)(t)=\int _{-\infty }^{t}(f*g)(\tau )\,d\tau .$$

Интеграция

Если f и g — интегрируемые функции, то интеграл от их свертки на всем пространстве просто получается как произведение их интегралов:

$\int _{\mathbf {R} ^{d}}(f*g)(x)\,dx=\left(\int _{\mathbf {R} ^{d}}f(x)\,dx\right)\left(\int _{\mathbf {R} ^{d}}g(x)\,dx\right).$

Это следует из теоремы Фубини . Тот же результат справедлив, если f и g считать только неотрицательными измеримыми функциями по теореме Тонелли .

Дифференциация

В случае с одной переменной

${\frac {d}{dx}}(f*g)={\frac {df}{dx}}*g=f*{\frac {dg}{dx}}$

где ${\frac {d}{dx}}$ является производной . В более общем смысле, в случае функций нескольких переменных аналогичная формула справедлива с частной производной :

${\frac {\partial }{\partial x_{i}}}(f*g)={\frac {\partial f}{\partial x_{i}}}*g=f*{\frac {\partial g}{\partial x_{i}}}.$

Особым следствием этого является то, что свертку можно рассматривать как операцию «сглаживания»: свертка f и g дифференцируема столько раз, сколько f и g в общей сложности.

Эти тождества выполняются, например, при условии, что f и g абсолютно интегрируемы и хотя бы одно из них имеет абсолютно интегрируемое (L ¹ ) слабая производная, как следствие неравенства свертки Юнга . Например, когда f непрерывно дифференцируема с компактным носителем, а g — произвольная локально интегрируемая функция,

${\frac {d}{dx}}(f*g)={\frac {df}{dx}}*g.$

Эти тождества также справедливы в гораздо более широком смысле в смысле умеренных распределений, если одно из f или g является быстро уменьшающееся умеренное распределение , компактно поддерживаемое умеренное распределение или функция Шварца, а другое — умеренное распределение. С другой стороны, две положительные интегрируемые и бесконечно дифференцируемые функции могут иметь нигде не непрерывную свертку.

В дискретном случае разностный оператор D f ( n ) = f ( n + 1) − f ( n ) удовлетворяет аналогичному соотношению:

$D(f*g)=(Df)*g=f*(Dg).$

Теорема о свертке

Теорема свертки утверждает, что

${\mathcal {F}}\{f*g\}={\mathcal {F}}\{f\}\cdot {\mathcal {F}}\{g\}$

где ${\mathcal {F}}\{f\}$ обозначает Фурье преобразование $f$.

Свертка в других видах преобразований

Версии этой теоремы также справедливы для преобразования Лапласа , двустороннего преобразования Лапласа , Z-преобразования и преобразования Меллина .

Свертка на матрицах

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

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

где $\bullet$ это продукт, который разбивает лицо , $\otimes$ обозначает произведение Кронекера , $\circ$ обозначает произведение Адамара (этот результат представляет собой развитие графического эскиза свойств ).

Это можно обобщить для соответствующих матриц $\mathbf {A} ,\mathbf {B}$:

${\mathcal {W}}\left((\mathbf {A} x)\ast (\mathbf {B} y)\right)=\left(({\mathcal {W}}\mathbf {A} )\bullet ({\mathcal {W}}\mathbf {B} )\right)(x\otimes y)=({\mathcal {W}}\mathbf {A} x)\circ ({\mathcal {W}}\mathbf {B} y)$

от свойств торцевого продукта .

Трансляционная эквивалентность

Свертка коммутирует с переводами, а это означает, что

$\tau _{x}(f*g)=(\tau _{x}f)*g=f*(\tau _{x}g)$

где τ _x f — перевод функции f на x, определяемый формулой

$(\tau _{x}f)(y)=f(y-x).$

Если f — функция Шварца , то τ _x f — это свертка со сдвинутой дельта-функцией Дирака τ _x f = f ∗ τ _x δ . Итак, трансляционная инвариантность свертки функций Шварца является следствием ассоциативности свертки.

Более того, при определенных условиях свертка является наиболее общей инвариантной операцией трансляции. Неформально говоря, имеет место следующее

Предположим, что S — ограниченный линейный оператор, действующий на функции, коммутирующие со сдвигами: S ( τ _x f ) = τ _x ( Sf ) для всех x . Тогда S задается как свертка с функцией (или распределением) g _S ; то есть Sf знак равно грамм _S * ж .

Таким образом, некоторые операции, инвариантные к трансляции, можно представить как свертку. Свертки играют важную роль в изучении стационарных систем , и особенно теории систем LTI . Представляющая функция g _S является импульсной характеристикой преобразования S .

Более точная версия приведенной выше теоремы требует указания класса функций, на которых определена свертка, а также требует дополнительно предположить, что S должен быть непрерывным линейным оператором относительно соответствующей топологии . Известно, например, что каждый непрерывный трансляционно-инвариантный непрерывный линейный оператор на L ¹ — свертка с конечной борелевской мерой . В более общем смысле, каждый непрерывный линейный оператор, инвариантный относительно сдвига, на L ^п при 1 ≤ p < ∞ — это свертка с умеренным распределением, которой преобразование Фурье ограничено. А именно, все они задаются ограниченными множителями Фурье .

Свертки на группах

Если G — подходящая группа, наделенная мерой λ , и если f и g — действительные или комплекснозначные интегрируемые функции на G , то мы можем определить их свертку формулой

$(f*g)(x)=\int _{G}f(y)g\left(y^{-1}x\right)\,d\lambda (y).$

Оно вообще не коммутативно. В типичных интересующих нас случаях G — локально компактная Хаусдорфа топологическая группа , а λ — (левая) мера Хаара . В этом случае, если G не является унимодулярным , свертка, определенная таким образом, не совпадает со сверткой. ${\textstyle \int f\left(xy^{-1}\right)g(y)\,d\lambda (y)}$. Предпочтение одного над другим делается для того, чтобы свертка с фиксированной функцией g коммутировала с левым сдвигом в группе:

$L_{h}(f*g)=(L_{h}f)*g.$

Кроме того, конвенция также необходима для обеспечения соответствия определению совокупности мер, приведенному ниже. Однако при использовании правой меры Хаара вместо левой последний интеграл предпочтительнее первого.

На локально компактных абелевых группах верна версия теоремы о свертке : преобразование Фурье свертки является поточечным произведением преобразований Фурье. Группа окружностей T с мерой Лебега является непосредственным примером. Для фиксированного g в L ¹ ( T ), мы имеем следующий знакомый оператор, действующий в гильбертовом пространстве L ² ( Т ):

$T{f}(x)={\frac {1}{2\pi }}\int _{\mathbf {T} }{f}(y)g(x-y)\,dy.$

Оператор T компактен ​ . Непосредственный расчет показывает, что сопряженное к нему T* является сверткой с

${\bar {g}}(-y).$

По свойству коммутативности, указанному выше, T является нормальным : T * T = TT * . Кроме того, T коммутирует с операторами перевода. Рассмотрим семейство S операторов, состоящее из всех таких сверток и операторов перевода. Тогда S — коммутирующее семейство нормальных операторов. Согласно спектральной теории существует ортонормированный базис { hk _{} ,} который одновременно диагонализует S. , Это характеризует извилины на окружности. В частности, у нас есть

$h_{k}(x)=e^{ikx},\quad k\in \mathbb {Z} ,\;$

именно персонажами Т. которые являются Каждая свертка представляет собой компактный оператор умножения в этом базисе. Это можно рассматривать как версию теоремы о свертке, обсуждавшейся выше.

Дискретным примером является конечная циклическая группа порядка n . Операторы свертки здесь представлены циркулянтными матрицами и могут быть диагонализованы с помощью дискретного преобразования Фурье .

Аналогичный результат верен и для компактных групп (не обязательно абелевых): матричные коэффициенты конечномерных унитарных представлений образуют ортонормированный базис в L ² по теореме Петера-Вейля , и аналог теоремы о свертке продолжает оставаться в силе, наряду со многими другими аспектами гармонического анализа , которые зависят от преобразования Фурье.

Свертка мер

Пусть G — (мультипликативно записанная) топологическая группа.Если µ и ν — конечные борелевские меры на G , то их свертка µ ∗ ν определяется как прямая мера и действия группы может быть записана как

$(\mu *\nu )(E)=\iint 1_{E}(xy)\,d\mu (x)\,d\nu (y)$

для каждого измеримого подмножества E из G . Свертка также является конечной мерой, полная вариация которой удовлетворяет условию

$\|\mu *\nu \|\leq \left\|\mu \right\|\left\|\nu \right\|.$

В случае, когда G с локально компактна (левой) мерой Хаара λ, а µ и ν абсолютно непрерывны относительно λ, так что каждая из них имеет функцию плотности , то свертка µ∗ν также абсолютно непрерывна, и его функция плотности представляет собой просто свертку двух отдельных функций плотности.

Если µ и ν являются вероятностными мерами на топологической группе ( R ,+), то свертка µ ∗ ν представляет собой распределение вероятностей суммы X + Y двух независимых случайных величин X и Y, чьи соответствующие распределения равны µ и ν.

Инфимальная свертка

В выпуклом анализе инфимальная свертка собственных (не тождественных $+\infty$) выпуклые функции $f_{1},\dots ,f_{m}$ на $\mathbb {R} ^{n}$ определяется: $$(f_{1}*\cdots *f_{m})(x)=\inf _{x}\{f_{1}(x_{1})+\cdots +f_{m}(x_{m})|x_{1}+\cdots +x_{m}=x\}.$$Можно показать, что нижняя свертка выпуклых функций выпукла. Более того, он удовлетворяет тождеству, аналогичному тождеству преобразования Фурье традиционной свертки, причем роль преобразования Фурье вместо этого играет преобразование Лежандра : $$\varphi ^{*}(x)=\sup _{y}(x\cdot y-\varphi (y)).$$У нас есть: $$(f_{1}*\cdots *f_{m})^{*}(x)=f_{1}^{*}(x)+\cdots +f_{m}^{*}(x).$$

Биалгебры

Пусть ( X , Δ, ∇, ε , η ) — биалгебра с коумножением Δ, умножением ∇, единицей η и единицей ε . Свертка — это произведение, определенное на алгебре эндоморфизмов End( X ) следующим образом. Пусть φ , ψ ∈ End( X ), то есть φ , ψ : X → X — функции, которые соблюдают всю алгебраическую структуру X , тогда свертка φ ∗ ψ определяется как композиция

$X\mathrel {\xrightarrow {\Delta } } X\otimes X\mathrel {\xrightarrow {\phi \otimes \psi } } X\otimes X\mathrel {\xrightarrow {\nabla } } X.$

Свертка особенно проявляется в определении алгебр Хопфа ( Кассель 1995 , §III.3). Биалгебра является алгеброй Хопфа тогда и только тогда, когда она имеет антипод: эндоморфизм S такой, что

$S*\operatorname {id} _{X}=\operatorname {id} _{X}*S=\eta \circ \varepsilon .$

Приложения

Размытие по Гауссу можно использовать для получения гладкого цифрового изображения полутонового отпечатка в оттенках серого .

Свертка и связанные с ней операции встречаются во многих приложениях в науке, технике и математике.

• Сверточные нейронные сети применяют несколько каскадных ядер свертки с приложениями в машинном зрении и искусственном интеллекте . Хотя на самом деле в большинстве случаев это взаимные корреляции, а не свертки.
• При нейронных сетей без использования обработке изображений
  • При цифровой обработке изображений сверточная фильтрация играет важную роль во многих важных алгоритмах Ядро обнаружения границ и связанных с ними процессах (см. (обработка изображений) ).
  • В оптике расфокусированная фотография представляет собой свертку резкого изображения с функцией линзы. Фотографический термин для этого — боке .
  • В приложениях обработки изображений, таких как добавление размытия.
• В цифровой обработке данных
  • В аналитической химии сглаживающие фильтры Савицкого – Голея используются для анализа спектроскопических данных. Они позволяют улучшить соотношение сигнал/шум с минимальными искажениями спектров.
  • В статистике взвешенное скользящее среднее представляет собой свертку.
• В акустике от объектов , реверберация — это свертка исходного звука с эхом окружающих источник звука.
  • При цифровой обработке сигналов свертка используется для отображения импульсной характеристики реальной комнаты на цифровой аудиосигнал.
  • В электронной музыке свертка — это наложение спектральной на звук или ритмической структуры. Часто эта огибающая или структура взята из другого звука. Свертка двух сигналов — это фильтрация одного через другой.
• В электротехнике свертка одной функции ( входного сигнала ) со второй функцией (импульсной характеристикой) дает на выходе линейную нестационарную систему (LTI). В любой данный момент выходные данные представляют собой совокупный эффект всех предыдущих значений входной функции, при этом самые последние значения обычно имеют наибольшее влияние (выраженное как мультипликативный коэффициент). Функция импульсного отклика определяет этот коэффициент как функцию времени, прошедшего с момента появления каждого входного значения.
• В физике везде, где существует линейная система с « принципом суперпозиции », появляется операция свертки. Например, в спектроскопии уширение линии из-за эффекта Доплера само по себе дает гауссову форму спектральной линии , а одно только уширение столкновений дает лоренцеву форму линии. Когда оба эффекта действуют, форма линии представляет собой свертку гауссовой и лоренцевой функции Фойгта .
  • В флуоресцентной спектроскопии с временным разрешением сигнал возбуждения можно рассматривать как цепочку дельта-импульсов, а измеренную флуоресценцию представляет собой сумму экспоненциального затухания каждого дельта-импульса.
  • В вычислительной гидродинамике модель с моделированием больших вихрей (LES) турбулентности использует операцию свертки, чтобы уменьшить диапазон масштабов длин, необходимых для вычислений, тем самым снижая вычислительные затраты.
• В теории вероятностей распределение вероятностей суммы двух независимых случайных величин представляет собой свертку их индивидуальных распределений.
  • При оценке плотности ядра распределение оценивается по точкам выборки путем свертки с ядром, например изотропным гауссианом.
• В системах планирования лучевой терапии большая часть всех современных кодов расчета применяет алгоритм свертки-суперпозиции .
• В структурной надежности индекс надежности можно определить на основе теоремы о свертке.
  • Определение показателя надежности для функций предельного состояния с ненормальным распределением может быть установлено в соответствии с совместной функцией распределения . Фактически совместную функцию распределения можно получить с помощью теории свертки.
• В гидродинамике сглаженных частиц моделирование гидродинамики рассчитывается с использованием частиц, каждая из которых имеет окружающие ядра. Для любой данной частицы $i$, некоторая физическая величина $A_{i}$ рассчитывается как свертка $A_{j}$ с весовой функцией, где $j$ обозначает соседей частицы $i$: те, которые расположены внутри его ядра. Свертка аппроксимируется суммированием по каждому соседу.
• В дробном исчислении свертка играет важную роль в различных определениях дробного интеграла и дробной производной.

См. также

• Аналоговая обработка сигналов
• Циркулирующая матрица
• Свертка для оптических откликов широкого луча в рассеивающих средах
• Мощность свертки
• Коэффициент свертки
• Свертка Дирихле
• Обобщенное усреднение сигнала
• Список сверток вероятностных распределений
• Теория систем LTI # Импульсный отклик и свертка
• Многомерная дискретная свертка
• Масштабированная корреляция
• Теорема Титчмарша о свертке
• Матрица Теплица (свертки можно рассматривать как матричную операцию Теплица, где каждая строка представляет собой сдвинутую копию ядра свертки)
• Вейвлет-преобразование

Дальнейшее чтение

• Брейсвелл, Р. (1986), Преобразование Фурье и его приложения (2-е изд.), МакГроу – Хилл, ISBN  0-07-116043-4 .
• Дамелин, С.; Миллер, В. (2011), Математика обработки сигналов , Cambridge University Press, ISBN  978-1107601048
• Диггл, П.Дж. (1985), «Метод ядра для сглаживания данных точечного процесса», Журнал Королевского статистического общества, серия C , 34 (2): 138–147, doi : 10.2307/2347366 , JSTOR   2347366 , S2CID   116746157
• Домингес-Торрес, Алехандро (2 ноября 2010 г.). «Происхождение и история свертки». 41 стр. https://slideshare.net/Alexdfar/origin-adn-history-of-convolution . Крэнфилд, Бедфорд MK43 OAL, Великобритания. Проверено 13 марта 2013 г.
• Гасеми, С. Хуман; Новак, Анджей С. (2017), «Индекс надежности ненормального распределения функций предельного состояния», Structural Engineering and Mechanics , 62 (3): 365–372, doi : 10.12989/sem.2017.62.3.365
• Гриншпан, А.З. (2017), «Неравенство для множественных сверток относительно вероятностной меры Дирихле», Успехи в прикладной математике , 82 (1): 102–119, doi : 10.1016/j.aam.2016.08.001
• Хьюитт, Эдвин; Росс, Кеннет А. (1979), Абстрактный гармонический анализ. Том I , Фундаментальные основы математических наук, том. 115 (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN  978-3-540-09434-0 , МР   0551496 .
• Хьюитт, Эдвин; Росс, Кеннет А. (1970), Абстрактный гармонический анализ. Том II: Структура и анализ компактных групп. Анализ локально компактных абелевых групп , The Basic Teachings of the Mathematical Sciences, Volume 152, Berlin, New York: Springer-Verlag , MR   0262773 .
• Хёрмандер, Л. (1983), Анализ линейных операторов в частных производных I , Grundl. Матем. наука., вып. 256, Спрингер, номер домена : 10.1007/978-3-642-96750-4 , ISBN.  3-540-12104-8 , МР   0717035 .
• Кассель, Кристиан (1995), Квантовые группы , Тексты для выпускников по математике, том. 155, Берлин, Нью-Йорк: Springer-Verlag , номер номера : 10.1007/978-1-4612-0783-2 , ISBN.  978-0-387-94370-1 , МР   1321145 .
• Кнут, Дональд (1997), Получисловые алгоритмы (3-е изд.), Ридинг, Массачусетс: Аддисон-Уэсли, ISBN  0-201-89684-2 .
• Наричи, Лоуренс; Бекенштейн, Эдвард (2011). Топологические векторные пространства . Чистая и прикладная математика (Второе изд.). Бока-Ратон, Флорида: CRC Press. ISBN  978-1584888666 . OCLC   144216834 .
• Рид, Майкл; Саймон, Барри (1975), Методы современной математической физики. II. Анализ Фурье, самосопряженность , Нью-Йорк-Лондон: Academic Press Харкорт Брейс Йованович, Издательство, стр. xv+361, ISBN  0-12-585002-6 , МР   0493420
• Рудин, Уолтер (1962), Фурье-анализ групп , Межнаучные трактаты по чистой и прикладной математике, том. 12, Нью-Йорк – Лондон: Interscience Publishers, ISBN.  0-471-52364-Х , МР   0152834 .
• Шефер, Хельмут Х .; Вольф, Манфред П. (1999). Топологические векторные пространства . ГТМ . Том. 8 (Второе изд.). Нью-Йорк, Нью-Йорк: Springer New York Выходные данные Springer. ISBN  978-1-4612-7155-0 . OCLC   840278135 .
• Штейн, Элиас ; Вайс, Гвидо (1971), Введение в анализ Фурье в евклидовых пространствах , Princeton University Press, ISBN  0-691-08078-Х .
• Соболев, В.И. (2001) [1994], «Свертка функций» , Энциклопедия Математики , EMS Press .
• Стрихарц, Р. (1994), Руководство по теории распределения и преобразованиям Фурье , CRC Press, ISBN  0-8493-8273-4 .
• Титчмарш, Э. (1948), Введение в теорию интегралов Фурье (2-е изд.), Нью-Йорк, Нью-Йорк: Chelsea Pub. Co. (опубликовано в 1986 г.), ISBN  978-0-8284-0324-5 .
• Тревес, Франсуа (2006) [1967]. Топологические векторные пространства, распределения и ядра . Минеола, Нью-Йорк: Dover Publications. ISBN  978-0-486-45352-1 . OCLC   853623322 .
• Улудаг, AM (1998), «О возможном ухудшении гладкости при операции свертки», J. Math. Анальный. Прил. , 227 (2): 335–358, doi : 10.1006/jmaa.1998.6091
• фон зур Гатен, Дж.; Герхард, Дж. (2003), Современная компьютерная алгебра , издательство Кембриджского университета, ISBN  0-521-82646-2 .

Внешние ссылки

• Самое раннее использование: запись о Convolution содержит некоторую историческую информацию.
• Свертка , в Книге по анализу данных
• https://jhu.edu/~signals/convolve/index.html Java-апплет визуальной свертки
• https://jhu.edu/~signals/discreteconv2/index.html Java-апплет визуальной свертки для функций дискретного времени
• https://get-the-solution.net/projects/discret-convolution онлайн-калькулятор дискретной свертки
• https://lpsa.swarthmore.edu/Convolution/CI.html Демонстрация свертки и визуализация в javascript
• https://phiresky.github.io/convolution-demo/ Еще одна демонстрация свертки на JavaScript.
• Лекции по обработке изображений: сборник из 18 лекций в формате pdf из Университета Вандербильта. Лекция 7 посвящена двумерной свертке. , Алан Питерс
• https://archive.org/details/Lectures_on_Image_Processing
• Интерактивное руководство по работе с маской ядра свертки
• Свертка в MathWorld
• Процессор импульсной характеристики Freeverb3 : процессор импульсной характеристики с открытой задержкой и плагинами VST.
• CS 178 Стэнфордского университета, Интерактивная Flash-демонстрация показывающая, как работает пространственная свертка.
• Видеолекция на тему свертки. Салмана Кхана
• Пример свертки БПФ для распознавания образов (обработка изображений)
• Интуитивное руководство по свертке. Сообщение в блоге об интуитивной интерпретации свертки.