Convoluția (analiza matematică)

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 28 decembrie 2021; verificările necesită 2 modificări .

Convoluția , convoluția este o operație în analiza funcțională , care, atunci când este aplicată la două funcții și returnează o a treia funcție corespunzătoare funcției de corelație încrucișată și . Operația de convoluție poate fi interpretată ca „asemănarea” unei funcții cu o copie în oglindă și deplasată a alteia. Conceptul de convoluție este generalizat pentru funcții definite pe spații măsurabile arbitrare și poate fi considerat ca un tip special de transformare integrală . În cazul discret , convoluția corespunde sumei valorilor cu coeficienți corespunzători valorilor deplasate , i.e. $f$ $g$ $f(x)$ $g(-x)$ $f$ $g$ $(f*g)(x)=f(1)g(x-1)+f(2)g(x-2)+f(3)g(x-3)+\dots$

Definiție

Fie două funcții integrabile în raport cu măsura Lebesgue pe spațiu . Atunci convoluția lor este funcția definită de formulă $f,g:\mathbb {R} ^{n}\la \mathbb {R}$ $\mathbb {R} ^{n}$ $f*g:\mathbb {R} ^{n}\la \mathbb {R}$

(f*g)(x)\

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

În special, pentru , formula ia forma $n=1$

(f*g)(x)\

\stackrel{\mathrm{def}}{=}\ \int \limits_{-\infty}^{\infty} f(y)\, g(xy)\, dy = \int \limits_{-\infty} ^{\infty} f(xy)\, g(y)\, dy.

Convoluția este definită pentru aproape toți și este integrabilă. $(f*g)(x)$ $x\in {\mathbb {R} ^{n)}$

În cazul în care , și funcțiile sunt definite pe intervalul , convoluția poate fi scrisă ca $x\in \mathbb {R}$ $f(x),~g(x)$ $[0,+\infty )$

(f*g)(x)\

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

Pentru prima dată, integralele, care sunt o convoluție a două funcții, se găsesc în lucrările lui Leonhard Euler (1760); mai târziu, convoluția apare la Laplace , Lacroix , Fourier , Cauchy , Poisson și alți matematicieni. Desemnarea circumvoluției de funcții folosind un asterisc a fost propusă pentru prima dată de Vito Volterra în 1912, la prelegerile sale de la Sorbona (publicate un an mai târziu) [1] .

Proprietăți

Comutativitate :

f*g=g*f

Asociativitate :

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

Linearitate ( distributivitatea în raport cu adunarea și asociativitatea cu înmulțirea cu un scalar ):

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

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

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

Regula de diferențiere:

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

unde denota derivata unei functii fata de orice variabila. $\mathrm{D}f$ $f$

Transformarea Laplace :

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

Proprietatea transformării Fourier :

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

unde denotă transformata Fourier a funcției. ${\mathfrak {F}}[]$

Dacă este o matrice discretă a transformării Fourier , atunci: ${\mathcal {W}}$

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

unde este simbolul produsului final al matricelor [2] [3] [4] [5] [6] , denotă produsul Kronecker , este simbolul produsului Hadamard (identitatea este o consecință a proprietăților referinței schiță [7] ). $\bullet$ $\otimes$ $\circ$

Exemplu

Sarcina să fie de a calcula modul în care cantitatea de zăpadă de pe orice bucată de pământ se va schimba în funcție de timp. Soluția la această problemă poate fi împărțită în două etape:

construiți un model de zăpadă și un model de topire a zăpezii.
combină cumva aceste două modele într-unul singur.

Sarcinile din prima etapă sunt rezolvate prin observații și experimente, iar sarcinile din a doua etapă sunt rezolvate prin convoluția modelelor obținute în prima etapă.

Să fie, ca urmare a rezolvării problemei din prima etapă, s-au construit două dependențe (modele matematice):

dependența cantității de zăpadă de ora curentă , ${\color {Roșu}g(t))$
dependenţa ponderii zăpezii netopite de timpul scurs de la căderea acesteia . ${\color {Albastru} f(\tau ))$

Dacă zăpada nu a început să se topească, cantitatea tuturor precipitațiilor ar putea fi calculată adăugând în cazul discret: $G$

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

sau prin integrare în cazul continuului:

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

Dar, în acest caz, are loc topirea zăpezii și, în plus, depinde nu numai de cantitatea totală actuală de zăpadă, ci și de momentul în care a căzut această cantitate specială de zăpadă. Așa că zăpada căzută acum două săptămâni s-ar putea să se fi evaporat deja, în timp ce zăpada căzută acum o jumătate de oră va zăcea în continuare și nici nu va începe să se dezghețe.

Se pare că pentru zăpada care a căzut în momente diferite, trebuie să vă construiți propriul model de topire și să adăugați cumva toate aceste modele împreună.

În aceste scopuri, poate fi folosit conceptul de convoluție matematică. Fie ca în momentul de timp zăpada care a căzut în momentul de timp este considerată , atunci $t$ $\tau$

$\tau$ - timpul ninsorii. De exemplu, 13:00;
${\color {Roșu}g(\tau ))$ - cantitatea de zăpadă căzută în acest moment. De exemplu, 7 kg; ${\tau )$
$t$ este momentul în care trebuie să cunoaștem starea zăpezii. De exemplu, 15:00; $\tau$
$t-\tau$ - timpul scurs din momentul precipitațiilor până la calculul proporției rămase de zăpadă. Adică 15:00 − 13:00 ;
${\color {Albastru} f(t-\tau ))$ - proporția de zăpadă care nu s-a topit după ce a stat ore în șir. $t-\tau$

Este necesar pentru fiecare cantitate de zăpadă care a căzut în momentul t să adăugați setul de modele într-o singură funcție. Dacă facem acest lucru, obținem suma în cazul discret: ${\color {Roșu}g(\tau ))$ $\tau$ $f(t-\tau )$

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

sau integrală în continuu:

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

Grafic, funcția este prezentată mai jos, unde contribuțiile fiecărui morman de zăpadă din grafic sunt reprezentate în culori diferite . $w(t)$ ${\color {Roșu}g(x))$

Funcția simulează pe deplin comportamentul căderii zăpezii conform modelului . Deci, în graficul de mai sus, puteți observa că cantitatea totală de zăpadă crește în trei sărituri, dar zăpada începe să se topească imediat, fără să așteptați să cadă alte precipitații. $w(t)$ ${\color {Roșu}g(x))$

Convoluție pe grupuri

Fie un grup dotat cu măsură și două funcții definite pe . Atunci convoluția lor este funcția $G$ $m$ $f,g:G \to \mathbb{R}$ $G$

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

Măsuri cumulate

Să fie un spațiu Borel și două măsuri . Atunci convoluția lor este măsura $(\mathbb {R} ,{\mathcal {B}}(\mathbb {R} ))$ $\mu,\nu: \mathcal{B}(\mathbb{R}) \to \mathbb{R}$

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

unde denotă produsul măsurilor și . $\mu \otimes \nu$ $\mu$ $\nu$

Proprietăți

Să fie absolut continuu cu privire la măsura Lebesgue . Notăm derivații lor Radon-Nikodim : $\mu,\nu$ $m$

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

Apoi este, de asemenea, absolut continuu în ceea ce privește , iar derivatul său Radon-Nikodim are forma $\mu * \nu$ $m$ $f_{\mu * \nu} = \frac{d \mu * \nu}{dm}$

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

Dacă sunt măsuri de probabilitate , atunci este și o măsură de probabilitate. $\mu,\nu$ $\mu * \nu$

Convoluția distribuțiilor

Dacă sunt distribuții a două variabile aleatoare independente și , atunci $\mathbb{P}^X,\mathbb{P}^Y$ $X$ $Y$

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

unde este distribuția sumei . În special, dacă sunt absolut continue și au densități , atunci variabila aleatoare este , de asemenea, absolut continuă, iar densitatea sa are forma: $\mathbb{P}^{X+Y}$ $X+Y$ $X Y$ $f_X,f_Y$ $X+Y$

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

Vezi și

Note

↑ Domínguez A. A History of the Convolution Operation // IEEE Pulse. - 2015. - Vol. 6, nr. 1. - P. 38-49. Arhivat din original pe 3 februarie 2016.
↑ Slyusar, VI (27 decembrie 1996). „Produse finale în matrice în aplicații radar” (PDF) . Radioelectronică și sisteme de comunicații.– 1998, voi. 41; Numărul 3 : 50-53. Arhivat (PDF) din original pe 27.07.2020 . Extras 2020-08-01 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Slyusar, VI (20.05.1997). „Model analitic al rețelei de antene digitale pe baza produselor matricei de divizare a feței” (PDF) . Proc. ICATT-97, Kiev : 108-109. Arhivat (PDF) din original pe 25.01.2020 . Extras 2020-08-01 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Slyusar, VI (15.09.1997). „Noi operațiuni de produs matrice pentru aplicații de radare” (PDF) . Proc. Probleme directe și inverse ale teoriei undelor electromagnetice și acustice (DIPED-97), Lviv. : 73-74. Arhivat (PDF) din original pe 25.01.2020 . Extras 2020-08-01 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Slyusar, VI (13 martie 1998). „O familie de produse faciale ale matricelor și proprietățile sale” (PDF) . Cybernetics and Systems Analysis C/C of Cybernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379-384. DOI : 10.1007/BF02733426 . Arhivat (PDF) din original pe 25.01.2020 . Extras 2020-08-01 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Slyusar, VI (2003). „Produse faciale generalizate ale matricelor în modele de rețele de antene digitale cu canale neidentice” (PDF) . Sisteme de radioelectronică și comunicații . 46 (10): 9-17. Arhivat (PDF) din original pe 20.09.2020 . Extras 2020-08-01 . Parametrul depreciat folosit |deadlink=( ajutor )
↑ Ninh, Pham; Rasmus, Pagh (2013). Nuclee polinomiale rapide și scalabile prin hărți de caracteristici explicite . Conferința internațională SIGKDD privind descoperirea cunoștințelor și extragerea datelor. Asociația pentru Mașini de Calcul. DOI : 10.1145/2487575.2487591 .

Literatură

Kolmogorov A. N., Fomin S. V. Elemente de teoria funcțiilor și analiză funcțională, - M .: Nauka, 2004 (ed. a VII-a).
Shiryaev A. N. Probabilitate, - M .: Nauka. 1989.
Napalkov VV Ecuații de convoluție în spații multidimensionale. - M., Nauka, 1982. - Tiraj 3500 exemplare. — 240 s.

Link -uri

Applet Java
Applet Java
Convoluția liniară și ciclică . Preluat: 15 noiembrie 2010. (Rusă)

Metode de compresie

Teorie

informație	propriu Reciproc Entropie Entropia condiționată Complexitate Redundanţă
Unități	Pic Nat Ciuguli Hartley Formula Hartley

Fara pierderi

Compresie entropică	Sisteme numerice asimetrice Algoritmul Huffman Algoritmul adaptiv Huffman Algoritmul Shannon-Fano algoritmul lui Shannon Codare aritmetică ( Interval ) Codurile Golomb Delta Cod universal Elias Fibonacci
Dicţionar Methods	RLE Dezumfla LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Alte	RLE CTW BWT MTF PPM DMC

Audio

Teorie	Convoluţie PCM Alianta Prelevarea de probe teorema lui Kotelnikov
Metode	LPC LAR LSP WLPC CELP ACELP O lege μ-legea ADPCM MDCT transformata Fourier Model psihoacustic
Alte	Compresor audio Compresia vorbirii Codarea benzii

Imagini

Termeni	spațiu de culoare Pixel Subeșantionarea de saturație Artefacte de compresie
Metode	RLE DPCM fractal wavelet EZW SPIHT LP PrEP PCL
Alte	Rata de biți Imagine de testare standard PSNR Cuantizarea

Video

Termeni	Caracteristicile video Cadru Tipuri de cadre Calitate video
Metode	Compensarea mișcării PrEP Cuantizarea wavelet
Alte	Codec video Teoria distorsiunii ratei CBR ABR VBR