Свертка - Convolution

Визуальное сравнение свертки, взаимная корреляция, и автокорреляция. Для операций с функцией ж, и принимая высоту ж равно 1.0, значение результата в 5 различных точках указано заштрихованной областью под каждой точкой. Кроме того, симметрия ж это причина ${displaystyle g * f}$ и ${displaystyle fstar g}$ идентичны в этом примере.

В математика (особенно, функциональный анализ ), свертка это математическая операция на двух функции (ж и грамм), которая производит третью функцию (${displaystyle f * g}$), который выражает то, как форма одного изменяется другим. Период, термин свертка относится как к функции результата, так и к процессу ее вычисления. Он определяется как интеграл произведения двух функций после того, как одна перевернута и сдвинута. И интеграл вычисляется для всех значений сдвига, создавая функцию свертки.

Некоторые особенности свертки похожи на взаимная корреляция: для действительных функций от непрерывной или дискретной переменной он отличается от взаимной корреляции (${displaystyle fstar g}$) только в том, что либо ж(Икс) или же грамм(Икс) отражается относительно оси ординат; таким образом, это взаимная корреляция ж(Икс) и грамм(−Икс), или же ж(−Икс) и грамм(Икс).^[A] Для комплексных функций оператор взаимной корреляции - это прилегающий оператора свертки.

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

Свертка может быть определена для функций на Евклидово пространство и другие группы.^{[нужна цитата ]} Например, периодические функции, такой как преобразование Фурье с дискретным временем, можно определить на круг и свернутый периодическая свертка. (См. Строку 18 в DTFT § Свойства.) А дискретная свертка можно определить для функций на множестве целые числа.

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

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

Определение

Свертка ж и грамм написано ж∗грамм, обозначая оператор символом ∗.^[B] Он определяется как интеграл произведения двух функций после обращения и сдвига одной. Таким образом, это особый вид интегральное преобразование:

${displaystyle (f * g) (t) riangleq int _ {- infty} ^ {infty} f (au) g (t- au), d au.}$

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

${displaystyle (f * g) (t) riangleq int _ {- infty} ^ {infty} f (t- au) g (au), d au.}$

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

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

${displaystyle (f * g) (t) = int _ {0} ^ {t} f (au) g (t- au), d au quad {ext {for}} f, g: [0, infty) o mathbb {R}.}$

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

Обозначение

Общепринятое условное обозначение инженерных обозначений:^[2]

${displaystyle f (t) * g (t), riangleq underbrace {int _ {- infty} ^ {infty} f (au) g (t- au), d au} _ {(f * g) (t)} ,}$

который следует толковать осторожно, чтобы избежать путаницы. Например, ж(т)∗грамм(т − т₀) эквивалентно (ж∗грамм)(т − т₀), но ж(т − т₀)∗грамм(т − т₀) фактически эквивалентен (ж∗грамм)(т − 2т₀).^[3]

Производные

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

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

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

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

Одно из первых применений интеграла свертки появилось в Д'Аламбер вывод Теорема Тейлора в Recherches sur différents points important du système du monde, опубликовано в 1754 году.^[4]

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

${displaystyle int f (u) cdot g (x-u), du}$

используется Сильвестр Франсуа Лакруа на странице 505 его книги под названием Трактат о различиях и сериях, который является последним из трех томов энциклопедической серии: Traité du Calcul différentiel et du Calcul intégral, Chez Courcier, Париж, 1797–1800.^[5] Вскоре после этого операции свертки появляются в работах Пьер Симон Лаплас, Жан-Батист Жозеф Фурье, Симеон Дени Пуассон, и другие. Сам термин не получил широкого распространения до 1950-х или 60-х годов. До этого его иногда называли Фальтунг (что значит складывание в Немецкий ), состав продукта, интеграл суперпозиции, и Интеграл Карсона.^[6]Тем не менее, он появился еще в 1903 году, хотя определение довольно незнакомо для более старых применений.^[7][8]

Операция:

${displaystyle int _ {0} ^ {t} varphi (s) psi (t-s), ds, qquad 0leq t$

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

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

Когда функция грамм_Т периодический, с периодом Т, то для функций ж, так что ж ∗ грамм_Т существует, свертка также периодическая и идентична:

${displaystyle (f * g_ {T}) (t) Equiv int _ {t_ {0}} ^ {t_ {0} + T} left [sum _ {k = -infty} ^ {infty} f (au + kT ) ight] g_ {T} (t- au), d au,}$

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

Когда грамм_Т является периодическим суммированием другой функции, грамм, тогда ж ∗ грамм_Т известен как круговой или же циклический свертка ж и грамм.

И если периодическое суммирование выше заменить на ж_Т, операция называется периодический свертка ж_Т и грамм_Т.

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

Для комплексных функций ж, грамм определено на множестве Z целых чисел, дискретная свертка из ж и грамм дан кем-то:^[10]

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

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

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

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

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

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

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

Когда функция грамм_N периодический, с периодом N, то для функций ж, так что ж∗грамм_N существует, свертка также периодическая и идентична:

${displaystyle (f * g_ {N}) [n] эквивалентная сумма _ {m = 0} ^ {N-1} left (sum _ {k = -infty} ^ {infty} {f} [m + kN] ight ) g_ {N} [нм].}$

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

Если грамм_N является периодическим суммированием другой функции, грамм, тогда ж∗грамм_N известен как круговая свертка из ж и грамм.

Когда ненулевые длительности обоих ж и грамм ограничены интервалом [0, N−1],  ж∗грамм_N сводится к этим общим формам:

${displaystyle {egin {align} (f * g_ {N}) [n] & = sum _ {m = 0} ^ {N-1} f [m] g_ {N} [nm] & = sum _ { m = 0} ^ {n} f [m] g [nm] + sum _ {m = n + 1} ^ {N-1} f [m] g [N + nm] & = sum _ {m = 0} ^ {N-1} f [m] g [(nm) _ {mod {N}}] riangleq (f * _ {_ {N}} g) [n] конец {выровнено}}}$

(Уравнение 1)

Обозначение (ж ∗_N грамм) за циклическая свертка обозначает свертку по циклическая группа из целые числа по модулю N.

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

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

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

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

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

Если одна последовательность намного длиннее другой, нулевое расширение более короткой последовательности и быстрая циклическая свертка не являются наиболее эффективными с вычислительной точки зрения доступными методами.^[13] Вместо этого разложение более длинной последовательности на блоки и свёртка каждого блока позволяет использовать более быстрые алгоритмы, такие как Метод перекрытия – сохранения и Метод перекрытия – добавления.^[14] Гибридный метод свертки, сочетающий блочный и FIR алгоритмы обеспечивают нулевую задержку ввода-вывода, что полезно для вычислений свертки в реальном времени.^[15]

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

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

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

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

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

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

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

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

Свертка ж и грамм существует если ж и грамм оба Интегрируемые по Лебегу функции в L¹(р^d), и в этом случае ж∗грамм также интегрируемо (Штайн и Вайс, 1971 г., Теорема 1.3). Это следствие Теорема Тонелли. Это также верно для функций в L¹, при дискретной свертке или, в более общем смысле, для свертка по любой группе.

Аналогично, если ж ∈ L¹(р^d) играмм ∈ L^п(р^d) куда 1 ≤ п ≤ ∞, тогдаж∗грамм ∈ L^п(р^d), и

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

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

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

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

тогда

${displaystyle leftVert f * gightVert _ {r} leq leftVert fightVert _ {p} leftVert gightVert _ {q}, quad fin {mathcal {L}} ^ {p}, gin {mathcal {L}} ^ {q},}$

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

${displaystyle leftVert f * gightVert _ {r} leq B_ {p, q} leftVert fightVert _ {p} leftVert gightVert _ {q}, quad fin {mathcal {L}} ^ {p}, gin {mathcal {L}} ^ {q}.}$

Оптимальное значение B_п,q был открыт в 1975 году.^[16]

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

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

куда ${displaystyle | g | _ {q, w}}$ это слабый L^q норма. Свертка также определяет билинейное непрерывное отображение ${displaystyle L ^ {p, w} imes L ^ {q, w} o L ^ {r, w}}$ за ${displaystyle 1$, в силу слабого неравенства Юнга:^[17]

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

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

В дополнение к функциям с компактным носителем и интегрируемым функциям, функции, которые достаточно быстро затухают на бесконечности, также могут быть свернуты. Важной особенностью свертки является то, что если ж и грамм оба быстро распадаются, затем ж∗грамм также быстро распадается. В частности, если ж и грамм находятся быстро убывающие функции, то свертка ж∗грамм. В сочетании с тем, что свертка коммутирует с дифференцированием (см. #Характеристики ) следует, что класс Функции Шварца замкнуто относительно свертки (Штайн и Вайс, 1971 г., Теорема 3.3).

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

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

${displaystyle int _ {mathbf {R} ^ {d}} {f} (y) g (x-y), dy.}$

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

${displaystyle f * (g * varphi) = (f * g) * varphi}$

остается в силе в случае, когда ж это распределение, а грамм дистрибутив с компактным носителем (Хёрмандер 1983, §4.2).

Меры

Свертка любых двух Борелевские меры μ и ν ограниченная вариация это мера ${displaystyle mu * u}$ определяется (Рудин 1962 )

${displaystyle int _ {mathbf {R} ^ {d}} f (x), d (mu * u) (x) = int _ {mathbf {R} ^ {d}} int _ {mathbf {R} ^ { d}} f (x + y), dmu (x), du (y).}$

Особенно,

${displaystyle (mu * u) (A) = int _ {mathbf {R} ^ {d} imes mathbf {R} ^ {d}} 1_ {A} (x + y), d (mu imes u) (x , y),}$

куда ${displaystyle Asubset mathbf {R} ^ {d}}$ измеримое множество и ${displaystyle 1_ {A}}$ это индикаторная функция из ${displaystyle A}$.

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

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

${displaystyle | mu * u | leq | mu || u |}$

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

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

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

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

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

${displaystyle f * g = g * f}$

Доказательство: по определению

${displaystyle (f * g) (t) = int _ {- infty} ^ {infty} f (au) g (t- au), d au}$

Изменение переменной интегрирования на ${displaystyle u = t- au}$ результат следует.

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

${displaystyle f * (g * h) = (f * g) * h}$

Доказательство: это следует из использования Теорема Фубини (т.е. двойные интегралы могут быть вычислены как итерированные интегралы в любом порядке).

Распределительность

${displaystyle f * (g + h) = (f * g) + (f * h)}$

Доказательство. Это следует из линейности интеграла.

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

${displaystyle a (f * g) = (af) * g}$

для любого действительного (или комплексного) числа ${displaystyle a}$.

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

Никакая алгебра функций не обладает тождеством для свертки. Отсутствие идентичности обычно не является серьезным неудобством, поскольку большинство наборов функций, для которых выполняется свертка, могут быть свернуты с помощью дельта-распределение или, по крайней мере (как в случае L¹) признаться приближения к тождеству. Однако линейное пространство распределений с компактным носителем допускает тождество при свертке. Конкретно,

${displaystyle f * delta = f}$

куда δ - дельта-распределение.

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

Некоторые дистрибутивы S есть обратный элемент S⁻¹ для свертки, которая тогда должна удовлетворять

${displaystyle S ^ {- 1} * S = дельта}$

откуда явная формула для S⁻¹ может быть получено. множество обратимых распределений образует абелева группа под свертку.

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

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

Отношения с дифференциацией

${displaystyle (f * g) '= f' * g = f * g '}$

Доказательство:

${displaystyle {egin {align} (f * g) '& = {frac {d} {dt}} int _ {- infty} ^ {infty} f (au) g (t- au), d au [4pt ] & = int _ {- infty} ^ {infty} f (au) {frac {partial} {partial t}} g (t- au), d au [4pt] & = int _ {- infty} ^ { infty} f (au) g '(t- au), d au = f * g'.end {выровнено}}}$

Отношения с интеграцией

Если ${displaystyle F (t) = int _ {- infty} ^ {t} f (au) d au,}$ и ${displaystyle G (t) = int _ {- infty} ^ {t} g (au), d au,}$ тогда

${displaystyle (F * g) (t) = (f * G) (t) = int _ {- infty} ^ {t} (f * g) (au), d au.}$

Интеграция

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

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

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

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

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

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

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

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

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

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

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

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

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

${displaystyle D (f * g) = (Df) * g = f * (Dg).}$

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

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

${displaystyle {mathcal {F}} {f * g} = kcdot {mathcal {F}} {f} cdot {mathcal {F}} {g}}$

куда ${displaystyle {mathcal {F}} {f}}$ обозначает преобразование Фурье из ${displaystyle f}$, и ${displaystyle k}$ константа, которая зависит от конкретного нормализация преобразования Фурье. Версии этой теоремы верны и для Преобразование Лапласа, двустороннее преобразование Лапласа, Z-преобразование и Преобразование Меллина.

См. Также менее тривиальные Теорема Титчмарша о свертке.

С другой стороны, если ${displaystyle {mathcal {W}}}$ это Матрица преобразования Фурье, тогда

${displaystyle {mathcal {W}} (C ^ {(1)} xast C ^ {(2)} y) = ({mathcal {W}} C ^ {(1)} ullet {mathcal {W}} C ^ {(2)}) (xotimes y) = {mathcal {W}} C ^ {(1)} xcirc {mathcal {W}} C ^ {(2)} y}$,

куда ${displaystyle ullet}$ является продукт, расщепляющий лицо,^{[18][19][20][21][22]} ${displaystyle otimes}$ обозначает Кронекер продукт, ${displaystyle circ}$ обозначает Произведение Адамара (этот результат является развитием считать эскиз характеристики^[23] ).

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

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

${displaystyle au _ {x} (f * g) = (au _ ​​{x} f) * g = {f} * (au _ ​​{x} g)}$

где τ_Иксf - перевод функции ж к Икс определяется

${displaystyle (au _ ​​{x} f) (y) = f (y-x).}$

Если ж это Функция Шварца, то τ_Иксж свертка с преобразованной дельта-функцией Дирака τ_Иксж = ж ∗ τ_Икс δ. Таким образом, трансляционная инвариантность свертки функций Шварца является следствием ассоциативности свертки.

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

• Предположим, что S ограниченный линейный оператор действует на функции, которые коммутируют с переводами: S(τ_Иксж) = τ_Икс(Sf) для всех Икс. потом S дается как свертка с функцией (или распределением) грамм_S; то есть Sf = грамм_S ∗ ж.

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

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

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

Если грамм подходит группа наделен мера λ, а если ж и грамм имеют реальную или комплексную ценность интегрируемый функции на грамм, то их свертку можно определить как

${displaystyle (f * g) (x) = int _ {G} f (y) g (y ^ {- 1} x), dlambda (y).}$

В общем, он не коммутативен. В типичных случаях интереса грамм это локально компактный Хаусдорф топологическая группа и λ является (левым) Мера Хаара. В этом случае, если грамм является унимодулярный, определенная таким образом свертка не совпадает с ${displaystyle extstyle {int f (xy ^ {- 1}) g (y), dlambda (y)}}$. Предпочтение одного перед другим делается так, чтобы свертка с фиксированной функцией грамм коммутирует с левым переводом в группе:

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

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

О локально компактных абелевы группы, версия теорема свертки выполнено: преобразование Фурье свертки - это поточечное произведение преобразований Фурье. В круговая группа Т с мерой Лебега является непосредственным примером. За фиксированный грамм в L¹(Т) имеем следующий знакомый оператор, действующий на Гильбертово пространство L²(Т):

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

Оператор Т является компактный. Прямой расчет показывает, что его сопряженная Т * свертка с

${displaystyle {ar {g}} (- y).}$

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

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

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

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

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

Свертка мер

Позволять грамм - топологическая группа (мультипликативно записанная); если μ и ν конечны Борелевские меры на грамм, то их свертка μ ∗ ν определяется как предварительная мера из групповое действие и может быть записано как

${displaystyle (mu * u) (E) = iint 1_ {E} (xy), dmu (x), du (y)}$

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

${displaystyle | mu * u | leq | mu || u |.}$

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

Если μ и ν равны вероятностные меры на топологической группе (р,+), то свертка μ ∗ ν является распределение вероятностей суммы Икс + Y из двух независимый случайные переменные Икс и Y чьи распределения - это соответственно μ и ν.

Биалгебры

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

${displaystyle X {xrightarrow {Delta}} Xotimes X {xrightarrow {phi otimes psi}} Xotimes X {xrightarrow {abla}} X.}$

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

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

Приложения

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

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

• В обработка изображений

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

В оптика, фотография не в фокусе - это свертка резкого изображения с функцией объектива. Фотографический термин для этого боке.

В приложениях обработки изображений, таких как добавление размытия.

• В цифровой обработке данных

В аналитическая химия, Сглаживающие фильтры Савицкого – Голея используются для анализа спектроскопических данных. Они могут улучшить соотношение сигнал шум с минимальным искажением спектров

В статистика, взвешенный скользящая средняя это свертка.

• В акустика, реверберация свертка исходного звука с эхо от предметов, окружающих источник звука.

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

В электронная музыка свертка - это наложение спектральный или ритмическая структура звука. Часто эта оболочка или структура берется из другого звука. Свертка двух сигналов - это фильтрация одного через другой.^[24]

• В электротехника, свертка одной функции ( входной сигнал ) со второй функцией (импульсной характеристикой) дает выходной сигнал линейная инвариантная во времени система (LTI). В любой данный момент выходные данные представляют собой совокупный эффект всех предшествующих значений входной функции, причем самые последние значения обычно имеют наибольшее влияние (выраженные как мультипликативный коэффициент). Функция импульсной характеристики обеспечивает этот коэффициент как функцию времени, прошедшего с момента появления каждого входного значения.
• В физика, везде, где есть линейная система с "принцип суперпозиции ", появляется операция свертки. Например, в спектроскопия уширение линии из-за эффекта Доплера само по себе дает Гауссовский форма спектральной линии и только коллизионное уширение дает Лоренциан форма линии. Когда действуют оба эффекта, форма линии представляет собой свертку гауссианы и лоренцевы, т.е. Функция Фойгта.

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

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

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

В оценка плотности ядра, распределение оценивается по точкам выборки путем свертки с ядром, например изотропным гауссовым.^[25]

• В системах планирования лечения лучевой терапией большая часть всех современных кодексов расчета включает алгоритм свертки-суперпозиции.^{[требуется разъяснение ]}
• Сверточные нейронные сети применять несколько ядер каскадной свертки с приложениями в машинное зрение и искусственный интеллект. Хотя на самом деле это взаимные корреляции.
• В структурной надежности индекс надежности можно определить на основе теоремы свертки.

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

Смотрите также

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

Примечания

Рекомендации

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

• Bracewell, R. (1986), Преобразование Фурье и его приложения (2-е изд.), McGraw – Hill, ISBN  0-07-116043-4.
• Damelin, S .; Миллер, В. (2011), Математика обработки сигналов, Издательство Кембриджского университета, ISBN  978-1107601048
• Диггл, П. Дж. (1985), "Ядерный метод сглаживания данных точечного процесса", Журнал Королевского статистического общества, серия C, 34 (2): 138–147, Дои:10.2307/2347366, JSTOR  2347366, S2CID  116746157
• Домингес-Торрес, Алехандро (2 ноября 2010 г.). «Происхождение и история свертки». 41 стр. http://www.slideshare.net/Alexdfar/origin-adn-history-of-convolution. Крэнфилд, Бедфорд MK43 OAL, Великобритания. Проверено 13 марта 2013 года.
• Гасеми, С. Хуман; Новак, Анджей С. (2017), "Индекс надежности ненормальных распределений функций предельного состояния", Строительная инженерия и механика, 62 (3): 365–372, Дои:10.12989 / сем.2017.62.3.365
• Гриншпан, А. З. (2017), "Неравенство для множественных сверток относительно вероятностной меры Дирихле", Успехи в прикладной математике, 82 (1): 102–119, Дои:10.1016 / j.aam.2016.08.001
• Хьюитт, Эдвин; Росс, Кеннет А. (1979), Абстрактный гармонический анализ. Vol. я, Grundlehren der Mathematischen Wissenschaften [Основные принципы математических наук], 115 (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN  978-3-540-09434-0, МИСТЕР  0551496.
• Хьюитт, Эдвин; Росс, Кеннет А. (1970), Абстрактный гармонический анализ. Vol. II: Структура и анализ компактных групп. Анализ на локально компактных абелевых группах, Die Grundlehren der Mathematischen Wissenschaften, Band 152, Берлин, Нью-Йорк: Springer-Verlag, МИСТЕР  0262773.
• Хёрмандер, Л. (1983), Анализ линейных дифференциальных операторов в частных производных I, Grundl. Математика. Wissenschaft., 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 Harcourt Brace Jovanovich, Publishers, стр. Xv + 361, ISBN  0-12-585002-6, МИСТЕР  0493420
• Рудин, Вальтер (1962), Фурье-анализ на группах, Международные трактаты по чистой и прикладной математике, 12, Нью-Йорк – Лондон: Interscience Publishers, ISBN  0-471-52364-X, МИСТЕР  0152834.
• Шефер, Гельмут Х.; Вольф, Манфред П. (1999). Топологические векторные пространства. GTM. 8 (Второе изд.). Нью-Йорк, штат Нью-Йорк: Springer New York Выходные данные Springer. ISBN  978-1-4612-7155-0. OCLC  840278135.
• Штейн, Элиас; Вайс, Гвидо (1971), Введение в анализ Фурье на евклидовых пространствах, Издательство Принстонского университета, ISBN  0-691-08078-X.
• Соболев, В. (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.
• Улудаг, А.М. (1998), «О возможном ухудшении гладкости при операции свертки», J. Math. Анальный. Appl., 227 (2): 335–358, Дои:10.1006 / jmaa.1998.6091
• von zur Gathen, J .; Герхард, Дж. (2003), Современная компьютерная алгебра, Издательство Кембриджского университета, ISBN  0-521-82646-2.

внешняя ссылка

• Самое раннее использование: запись о свертке содержит некоторую историческую информацию.
• Свертка, на Краткое руководство по анализу данных
• http://www.jhu.edu/~signals/convolve/index.html Визуальная свертка Java-апплет
• http://www.jhu.edu/~signals/discreteconv2/index.html Java-апплет с визуальной сверткой для функций с дискретным временем
• 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 показывает, как работает пространственная свертка.
• Видео-лекция на тему свертки данный Салман Хан
• Пример свертки БПФ для распознавания образов (обработка изображений)