Convolución

Comparación visual de convolución, correlación cruzada e autocorrelación. Para as operacións que implican a función $f$, e asumindo que a altura de $f$ é 1.0, o valor do resultado en 5 puntos diferentes está indicado pola área sombreada debaixo de cada punto. A simetría de $f$ é a razón pola que $f\star g$ e $g*f$ son idénticos neste exemplo.

En matemáticas (en particular, na análise funcional), a convolución é unha operación matemática sobre dúas funcións ($f$ e $g$) que produce unha terceira función ($f*g$). O termo convolución refírese tanto á función resultante como ao proceso de calculala.

A convolución defínese como a integral do produto das dúas funcións despois de que unha delas se reflicte sobre o eixo $y$ e se despraza. A integral evalúase para todos os valores de desprazamento, producindo a función de convolución. Gráficamente, exprésase como a 'forma' dunha función é modificada pola outra.

A convolución discreta de dúas funcións para un índice n enteiro defínese como os produtos das valores das funcións nos índices que suman n (ver abaixo explicación detallada).

Algúns aspectos da convolución son similares á correlación cruzada: para funcións de valor real, dunha variábel continua ou discreta, a convolución ($f*g$) difire da correlación cruzada ($f\star g$) só en que $f(x)$ ou $g(x)$ se reflicte sobre o eixp $y$ na convolución; así, é unha correlación cruzada de $g(-x)$ e $f(x)$, ou de $f(-x)$ e $g(x)$. Para funcións de valor complexo, o operador de correlación cruzada é o adxunto do operador de convolución.

A convolución ten aplicacións que inclúen a probabilidade, estatística, acústica, espectroscopia, procesamento de sinais e procesamento de imaxes, xeofísica, enxeñaría, física e ecuacións diferenciais.

O cálculo da inversa da operación de convolución coñécese como deconvolución.

Definición

A convolución de $f$ e $g$ escríbese $f*g$, denotando o operador co símbolo $*$. Defínese como a integral do produto das dúas funcións despois de que unha delas se reflicte sobre o eixo $y$ e se despraza. Como tal, é un tipo particular de transformada integral:

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

Aínda que se usa o símbolo $t$ anteriormente, non ten que representar o dominio do tempo. En cada $t$, a fórmula de convolución pode describirse como a área baixo a función $f(\tau )$ ponderada pola función $g(-\tau )$ desprazada pola cantidade $t$. A medida que $t$ muda, a función de ponderación $g(t-\tau )$ destaca diferentes partes da función de entrada $f(\tau )$.

Se $t$ é un valor positivo, entón $g(t-\tau )$ é igual a $g(-\tau )$ que se desliza ou se despraza ao longo do eixo $\tau$ cara á dereita (cara a $+\infty$) pola cantidade de $t$, mentres que se $t$ é un valor negativo, entón $g(t-\tau )$ é igual a $g(-\tau )$ que se desliza ou se despraza cara á esquerda (cara a $-\infty$) pola cantidade de $|t|$.

Para funcións $f$, $g$ soportadas só en $[0,\infty )$ (é dicir, cero para argumentos negativos), os límites de integración poden truncarse, resultando en:

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

Para a formulación multidimensional da convolución, véxase dominio de definición (a continuación).

Notación

Unha convención notacional común en enxeñaría é:

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

que debe interpretarse con coidado para evitar confusións. Por exemplo, $f(t)*g(t-t_{0})$ é equivalente a $(f*g)(t-t_{0})$, mais $f(t-t_{0})*g(t-t_{0})$ é de feito equivalente a $(f*g)(t-2t_{0})$.

Convolución circular

Artigo principal: Convolución circular.

Cando unha función $g_{T}$ é periódica, con período $T$, entón para funcións, $f$, tal que $f*g_{T}$ existe, a convolución é tamén periódica e idéntica a:

$(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 ,$

onde $t_{0}$ é unha escolla arbitraria. A suma chámase suma periódica da función $f$.

Cando $g_{T}$ é unha suma periódica doutra función, $g$, entón $f*g_{T}$ coñécese como unha convolución circular ou cíclica de $f$ e $g$.

E se a suma periódica anterior se substitúe por $f_{T}$, a operación chámase unha convolución periódica de $f_{T}$ e $g_{T}$.

Convolución discreta

Animación de convolución discreta 2D

Para funcións de valor complexo $f$ e $g$ definidas no conxunto $\mathbb {Z}$ dos enteiros, a convolución discreta de $f$ e $g$ vén dada por:

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

A convolución de dúas secuencias finitas defínese estendendo as secuencias a funcións de soporte finito no conxunto dos enteiros. Cando as secuencias son os coeficientes de dous polinomios, entón os coeficientes do produto ordinario dos dous polinomios son a convolución das dúas secuencias orixinais. Isto coñécese como o produto de Cauchy dos coeficientes das secuencias.

Así, cando g ten soporte finito no conxunto $\{-M,-M+1,\dots ,M-1,M\}$ (representando, por exemplo, unha resposta finita ao impulso), pode usarse unha suma finita:

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

Como exemplo de convolución discreta para o caso dun produto de Cauchy de dúas series infinitas podemos organizar cada sumando do produto en forma de matriz cos coeficientes da combinación de elementos todos por todos:

$A={\begin{pmatrix}a_{0}b_{0}&a_{0}b_{1}&a_{0}b_{2}&a_{0}b_{3}&\cdots \\a_{1}b_{0}&a_{1}b_{1}&a_{1}b_{2}&a_{1}b_{3}&\cdots \\a_{2}b_{0}&a_{2}b_{1}&a_{2}b_{2}&a_{2}b_{3}&\cdots \\a_{3}b_{0}&a_{3}b_{1}&\cdots &\cdots &\cdots \\a_{4}b_{0}&\cdots &\cdots &\cdots &\cdots \\\vdots &\cdots &\cdots &\cdots &\cdots \\\end{pmatrix}}$,

desde o punto de vista desta matriz o produto de Cauchy é unha convolución discreta formada pola suma das antidiagonais:

$\left(\sum _{n=0}^{\infty }a_{n}\right)\cdot \left(\sum _{n=0}^{\infty }b_{n}\right)=\sum _{n=0}^{\infty }{\text{antidiagonais}}=\sum _{n=0}^{\infty }\sum _{k=0}^{n}a_{k}b_{n-k}.$

$\left(\sum _{n=0}^{\infty }a_{n}\right)\cdot \left(\sum _{n=0}^{\infty }b_{n}\right)=(a_{0}b_{0})+(a_{0}b_{1}+a_{1}b_{0})+(a_{0}b_{2}+a_{1}b_{1}+a_{2}b_{0})+\cdots$

Convolución circular discreta

Cando unha función $g_{_{N}}$ é periódica, con período $N,$ entón para funcións, $f,$ tales que $f*g_{_{N}}$ existe, a convolución é tamén periódica e idéntica a:

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

A suma sobre $k$ chámase suma periódica da función $f.$

Se $g_{_{N}}$ é unha suma periódica doutra función, $g,$ entón $f*g_{_{N}}$ coñécese como unha convolución circular de $f$ e $g.$

Cando as duracións non nulas de ambas as dúas $f$ e $g$ están limitadas ao intervalo $[0,N-1],$  $f*g_{_{N}}$ redúcese a estas formas comúns:

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

A notación $f*_{N}g$ para a convolución cíclica denota convolución sobre o grupo cíclico de enteiros módulo N.

A convolución circular xorde a miúdo no contexto da convolución rápida cun algoritmo de transformada rápida de Fourier (FFT).

Algoritmos rápidos de convolución

En moitas situacións, as convolucións discretas poden converterse en convolucións circulares para que as transformadas rápidas cunha propiedade de convolución poidan usarse para implementar o cálculo. Por exemplo, a convolución de secuencias de díxitos é a operación central na multiplicación de números de varios díxitos, que pode implementarse eficientemente con técnicas de transformación (Knuth 1997, §4.3.3.C; von zur Gathen & Gerhard 2003, §8.2).

A convolución circular de dúas secuencias de lonxitude finita obtense ao calcular unha FFT de cada secuencia, multiplicar punto a punto e logo realizar unha FFT inversa. As convolucións do tipo definido anteriormente impleméntanse eficientemente empregando esa técnica en conxunto coa extensión por ceros e/ou descartando partes da saída.

Outros algoritmos rápidos de convolución, como o algoritmo de Schönhage-Strassen ou a transformación de Mersenne, empregan transformacións rápidas de Fourier noutros anéis. O método de Winograd emprégase como alternativa á FFT. Acelera significativamente as convolucións en 1D, 2D, e 3D.

Se unha secuencia é moito máis longa que a outra, a extensión por ceros da secuencia máis curta e a convolución circular rápida non é o método computacionalmente máis eficiente dispoñíbel. En vez diso, descompoñer a secuencia máis longa en bloques e convolver cada bloque permite empregar algoritmos máis rápidos como o método superposición-salvar e o método superposición-sumar. Un método híbrido de convolución que combina algoritmos por bloques e FIR permite unha latencia de entrada-saída nula, útil para computacións de convolución en tempo real.

Dominio de definición

A convolución de dúas funcións de valor complexo en R^d é unha función de valor complexo en R^d, definida por:

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

e está ben definida só se f e g decaen suficientemente rápido no infinito para que a integral exista. As condicións para a existencia da convolución poden ser complicadas, xa que un aumento en g no infinito pode ser facilmente compensado por un decaemento suficientemente rápido en f. Así, a cuestión da existencia pode implicar diferentes condicións sobre f e g:

Funcións de soporte compacto

Se f e g son funcións continuas de soporte compacto, entón a súa convolución existe e tamén é de soporte compacto e continua (Hörmander 1983, Capítulo 1). Máis xeralmente, se unha das funcións (por exemplo, f) é de soporte compacto e a outra é localmente integrábel, entón a convolución f∗g está ben definida e é continua.

A convolución de f e g tamén está ben definida cando ambas as funcións son localmente cadrado integrábeis en R e están soportadas nun intervalo da forma [a, +∞) (ou en [−∞, a]).

Funcións integrábeis

A convolución de f e g existe se f e g son ambas as dúas funcións integrábeis de Lebesgue en L¹(R^d), e neste caso f∗g tamén é integrábel (Stein & Weiss 1971, Teorema 1.3). Isto é unha consecuencia do teorema de Tonelli. Isto tamén é certo para funcións en L¹, baixo a convolución discreta, ou máis xeralmente para a convolución en calquera grupo.

Do mesmo xeito, se f ∈ L¹(R^d)  e  g ∈ L^p(R^d)  onde 1 ≤ p ≤ ∞,  entón  f*g ∈ L^p(R^d),  e

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

No caso particular p = 1, isto mostra que L¹ é unha álxebra de Banach baixo a convolución (e a igualdade dos dous lados cúmprese se f e g son non negativas case en tódalas partes).

Máis xeralmente, a desigualdade de Young implica que a convolución é unha aplicación bilinear continua entre os espazos L^p adecuados. Especificamente, se 1 ≤ p, q, r ≤ ∞ cumpren:

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

entón

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

de xeito que a convolución é unha aplicación bilinear continua de L^p×L^q a L^r. A desigualdade de Young para a convolución tamén é certa noutros contextos (grupo circular, convolución en Z). A desigualdade anterior non é estrita na recta real: cando 1 < p, q, r < ∞, existe unha constante B_p,q < 1 tal que:

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

O valor óptimo de B_p,q descubriuse en 1975 e independentemente en 1976, véxase desigualdade de Brascamp-Lieb.

Unha estimación máis forte é certa sempre que 1 < p, q, r < ∞:

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

onde $\|g\|_{q,w}$ é a norma débil L^q. A convolución tamén define unha aplicación bilinear continua $L^{p,w}\times L^{q,w}\to L^{r,w}$ para $1<p,q,r<\infty$, debido á desigualdade de Young débil:

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

Funcións de decaemento rápido

Alén das funcións de soporte compacto e das funcións integrábeis, as funcións que teñen un decaemento suficientemente rápido no infinito tamén poden ser convolucionadas. Unha característica importante da convolución é que se f e g decaen rapidamente, entón f∗g tamén decae rapidamente. En particular, se f e g son funcións de decaemento rápido, entón a convolución f∗g tamén o é. Combinado co feito de que a convolución conmuta coa diferenciación (véxase #Propiedades), dedúcese que a clase de funcións de Schwartz é pechada baixo a convolución (Stein & Weiss 1971, Teorema 3.3).

Distribucións

Artigo principal: Distribución (matemáticas).

Se f é unha función suave de soporte compacto e g é unha distribución, entón f∗g é unha función suave definida por

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

Máis xeralmente, é posible estender a definición da convolución dun xeito único con $\varphi$ igual que coa f anteriormente, de xeito que a lei asociativa

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

siga a ser válida no caso en que f sexa unha distribución e g unha distribución de soporte compacto (Hörmander 1983, §4.2).

Medidas

A convolución de dúas medidas de Borel μ e ν de variación limitada é a medida $\mu *\nu$ definida por (Rudin 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).$

En particular,

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

onde $A\subset \mathbf {R} ^{d}$ é un conxunto medíbel e $1_{A}$ é a función indicadora de $A$.

Isto coincide coa convolución definida anteriormente cando μ e ν se consideran distribucións, así como coa convolución de funcións L¹ cando μ e ν son absolutamente continuas en relación á medida de Lebesgue.

A convolución de medidas tamén cumpre a seguinte versión da desigualdade de Young:

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

onde a norma é a variación total dunha medida. Como o espazo das medidas de variación limitada é un espazo de Banach, a convolución de medidas pode tratarse con métodos estándar da análise funcional que poden non aplicarse á convolución de distribucións.

Propiedades

Propiedades alxébricas

A convolución define un produto no espazo linear das funcións integrábeis. Este produto satisfai as seguintes propiedades alxébricas, que formalmente significan que o espazo das funcións integrábeis co produto dado pola convolución é unha álxebra asociativa conmutativa sen identidade (Strichartz 1994, §3.3). Outros espazos lineares de funcións, como o espazo das funcións continuas de soporte compacto, son pechados baixo a convolución, e tamén forman álxebras asociativas conmutativas.

Conmutatividade

$f*g=g*f$

Demostración: Por definición:

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

Mudando a variábel de integración a $u=t-\tau$ dedúcese o resultado.

Asociatividade

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

Demostración: Isto dedúcese de usar o teorema de Fubini (é dicir, as integrais dobres poden ser avaliadas como integrais iteradas en calquera orde).

Distributividade

$f*(g+h)=(f*g)+(f*h)$

Demostración: Isto dedúcese da linearidade da integral.

Asociatividade coa multiplicación escalar

$a(f*g)=(af)*g$

para calquera número real (ou complexo) $a$.

Identidade multiplicativa

Ningunha álxebra de funcións posúe unha identidade para a convolución. A falta de identidade normalmente non é un gran inconveniente, xa que a maioría das coleccións de funcións nas que se realiza a convolución poden ser convolucionadas cunha distribución delta (un impulso unitario, centrado en cero) ou, polo menos (como é o caso de L¹), admiten aproximacións á identidade. No entanto, o espazo linear das distribucións de soporte compacto admite unha identidade baixo a convolución. Especificamente,

$f*\delta =f$

onde δ é a distribución delta.

Elemento inverso

Algunhas distribucións S teñen un elemento inverso S⁻¹ para a convolución que entón debe satisfacer

$S^{-1}*S=\delta$

a partir do cal se pode obter unha fórmula explícita para S⁻¹. O conxunto das distribucións invertíbeis forma un grupo abeliano baixo a convolución.

Conxugación complexa

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

Inversión temporal

Se  $q(t)=r(t)*s(t),$  entón  $q(-t)=r(-t)*s(-t).$

Demostración (usando o teorema da convolución):

$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}}$

Relación coa diferenciación

$(f*g)'=f'*g=f*g'$

Demostración:

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

Relación coa integración

Se ${\textstyle F(t)=\int _{-\infty }^{t}f(\tau )d\tau ,}$ e ${\textstyle G(t)=\int _{-\infty }^{t}g(\tau )\,d\tau ,}$ entón

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

Véxase tamén

Bibliografía

• Titchmarsh, E (1948). Introduction to the theory of Fourier integrals (2nd ed.). New York, N.Y.: Chelsea Pub. Co. (publicado o 1986). ISBN 978-0-8284-0324-5. .

Outros artigos

• Procesamento anlóxico de sinal
• Matriz circulante
• Potencia dunha convolución
• Cociente de convolución
• Convolución de Dirichlet
• Lista de convolucións de distribucións de probabilidade
• Convolución discreta multidimensional
• Teorema de convolución de Titchmarsh
• Matriz de Toeplitz (as convolucións pódense considerar unha operación da matriz de Toeplitz onde cada fila é unha copia desprazada do núcleo de convolución)
• Transformación de onda

Ligazóns externas

• Usos máis antigos: a entrada sobre Convolution ten algunha información histórica.
• Convolution, on The Data Analysis BriefBook
• https://jhu.edu/~signals/convolve/index.html Visual convolution Java Applet
• https://jhu.edu/~signals/discreteconv2/index.html convolución visual Java Applet for discrete-time functions
• https://get-the-solution.net/projects/discret-convolution convolución discreta calculadora online
• Lectures on Image Processing: Unha colección de 18 conferencias en formato pdf da Universidade de Vanderbilt. A clase 7 trata sobre a convolución 2D, por Alan Peters

• Tutorial interactivo de operación de máscara de núcleo de convolución
• Convolution en MathWorld
• Freeverb3 Impulse Response Processor: Procesador de resposta de impulso de latencia cero de código aberto con complementos VST
• Stanford University CS 178 interactive Flash demo mostrando como funciona a convolución espacial.

• Exemplo de convolución FFT para o recoñecemento de padróns (procesamento de imaxes)
• Intuitive Guide to Convolution Unha publicación de blog sobre unha interpretación intuitiva da convolución.