Свертка

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

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

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

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

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

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

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

Определение [ править ]

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

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

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

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

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

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

${\ Displaystyle (е * г) (т) = \ int _ {0} ^ {т} е (\ тау) г (т- \ тау) \, д \ тау \ квад \ {\ текст {для}} е , g: [0, \ infty) \ to \ mathbb {R}.}$

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

Обозначение [ править ]

Общепринятое соглашение о технических обозначениях: ^[2]

${\ Displaystyle е (т) * г (т) \,: = \ underbrace {\ int _ {- \ infty} ^ {\ infty} е (\ тау) г (т- \ тау) \, д \ тау} _ {(ж * ж) (т)},}$

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

Производные [ править ]

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

Визуальное объяснение [ править ]

Исторические события [ править ]

Одно из первых применений интеграла свертки появилось при выводе Даламбером теоремы Тейлора в книге «Recherches sur différents points importants 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, Paris, 1797–1800. ^[5] Вскоре после этого операции свертки появляются в работах Пьера Симона Лапласа , Жан-Батиста Жозефа Фурье , Симеона Дени Пуассона и других. Сам термин не получил широкого распространения до 1950-х или 60-х годов. До этого его иногда называли Faltung (что в переводе с немецкого означает складной ), составной продукт., Суперпозиция интеграл и интеграл Карсона . ^[6] Тем не менее, оно появилось еще в 1903 году, хотя определение довольно незнакомо для более старых применений. ^{[7] [8]}

Операция:

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

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

Круговая свертка [ править ]

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

${\displaystyle (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 , г , определенной на множестве 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].}$

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

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

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

Круговая дискретная свертка [ править ]

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

${\displaystyle (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 .

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

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

${\displaystyle {\begin{aligned}(f*g_{N})[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]\\&=\sum _{m=0}^{N-1}f[m]g[(n-m)_{\bmod {N}}]\triangleq (f*_{_{N}}g)[n]\end{aligned}}}$

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

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

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

Алгоритмы быстрой свертки [ править ]

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

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

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

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

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

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

${\displaystyle (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 1 ( R d ) , и в этом случае f ∗ g также интегрируемо ( Stein & Weiss 1971 , теорема 1.3). Это следствие теоремы Тонелли . Это также верно для функций из L ¹ при дискретной свертке или, в более общем смысле, для свертки на любой группе .

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

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

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

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

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

тогда

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

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

${\displaystyle \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 {\mathcal {L}}^{p},\ g\in {\mathcal {L}}^{q}.}$

Оптимальное значение B _{p , q} было обнаружено в 1975 году ^[16].

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

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

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

${\displaystyle \|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 - гладкая функция, определяемая формулой распределения, аналогичной

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

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

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

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

Меры [ править ]

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

${\displaystyle \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).}$

Особенно,

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

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

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

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

${\displaystyle \|\mu *\nu \|\leq \|\mu \|\|\nu \|}$

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

Свойства [ править ]

Алгебраические свойства [ править ]

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

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

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

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

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

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

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

${\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=\delta }$

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

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

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

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

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

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

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

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

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

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

Интеграция [ править ]

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

${\displaystyle \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 считаются неотрицательными измеримыми функциями по теореме Тонелли .

Дифференциация [ править ]

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

${\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_{i}}}.}$

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

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

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

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

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

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

Теорема свертки [ править ]

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

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

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

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

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

${\displaystyle {\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}$,

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

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

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

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

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

${\displaystyle (\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 = g _S ∗ f .

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

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

Свертки по группам [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Свертка мер [ править ]

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

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

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

${\displaystyle \|\mu *\nu \|\leq \|\mu \|\|\nu \|.}$

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

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

Биалгебры [ править ]

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

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

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

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

Приложения [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Сверточные нейронные сети используют несколько ядер каскадной свертки с приложениями в области машинного зрения и искусственного интеллекта . Хотя на самом деле это скорее кросс-корреляции , чем свертки. ^[27]
• В гидродинамике сглаженных частиц моделирование динамики жидкости рассчитывается с использованием частиц, каждая из которых имеет окружающие ядра. Для любой заданной частицы некоторая физическая величина вычисляется как свертка с весовой функцией, где обозначает соседей частицы : те, которые расположены внутри ее ядра. Свертка аппроксимируется как суммирование по каждому соседу. ^[28]${\displaystyle i}$${\displaystyle A_{i}}$${\displaystyle A_{j}}$${\displaystyle j}$${\displaystyle i}$

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Bracewell, R. (1986), Преобразование Фурье и его приложения (2-е изд.), McGraw – Hill, ISBN 0-07-116043-4.
• Damelin, S .; Миллер, В. (2011), Математика обработки сигналов , Cambridge University Press, ISBN 978-1107601048
• Диггл, PJ (1985), "Метод ядра для сглаживания данных процесса точки", журнал Королевского статистического общества, серия C , 34 (2): 138-147, DOI : 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, doi : 10.12989 / sem.2017.62.3.365
• Гриншпан, Аризона (2017), "Неравенство для множества сверток с относительно Дирихле вероятностной меры", Прогресс в области прикладной математики , 82 (1): 102-119, DOI : 10.1016 / j.aam.2016.08.001
• Хьюитт, Эдвин; Росс, Кеннет А. (1979), Абстрактный гармонический анализ. Vol. I , 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 , MR  0262773.
• Хёрмандер, Л. (1983), Анализ линейных дифференциальных операторов в частных производных I , Grundl. Математика. Wissenschaft., 256 , Springer, doi : 10.1007 / 978-3-642-96750-4 , ISBN 3-540-12104-8, Руководство по ремонту  0717035.
• Кассель, Кристиан (1995), Квантовые группы , Тексты для выпускников по математике, 155 , Берлин, Нью-Йорк: Springer-Verlag , DOI : 10.1007 / 978-1-4612-0783-2 , ISBN 978-0-387-94370-1, Руководство по ремонту  1321145.
• Knuth, Donald (1997), Seminumerical Algorithms (3-е изд.), Reading, Massachusetts: Addison – Wesley, 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, MR  0493420
• Рудин, Вальтер (1962), анализ Фурье по группам , Interscience Tracts in Pure and Applied Mathematics, 12 , New York – London: Interscience Publishers, ISBN 0-471-52364-X, MR  0152834.
• Шефер, Гельмут Х .; Вольф, Манфред П. (1999). Топологические векторные пространства . GTM . 8 (Второе изд.). Нью-Йорк, Нью-Йорк: Springer New York Выходные данные Springer. ISBN 978-1-4612-7155-0. OCLC  840278135 .
• Штейн, Элиас ; Вайс, Гвидо (1971), Введение в анализ Фурье на евклидовых пространствах , Princeton University Press, ISBN 0-691-08078-X.
• Соболев, В.И. (2001) [1994], "Свертка функций" , Энциклопедия математики , EMS Press.
• Стрихарц, Р. (1994), Руководство по теории распределения и преобразованиям Фурье , CRC Press, ISBN 0-8493-8273-4.
• Титчмарш, E (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. Анальный. Appl. , 227 (2): 335-358, DOI : 10,1006 / jmaa.1998.6091
• von zur Gathen, J .; Герхард, Дж. (2003), Современная компьютерная алгебра , Cambridge University Press, 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 Impulse Response Processor : процессор импульсных откликов с нулевой задержкой и открытым исходным кодом с плагинами VST
• Интерактивная Flash-демонстрация CS 178 Стэнфордского университета, демонстрирующая, как работает пространственная свертка
• Видео лекция по теме свертки дается Салман
• Пример свертки БПФ для распознавания образов (обработка изображений)