Konvolution (matematisk analyse)

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 28. december 2021; checks kræver 2 redigeringer .

Konvolution , foldning er en operation i funktionel analyse , som, når den anvendes på to funktioner og returnerer en tredje funktion svarende til krydskorrelationsfunktionen og . Konvolutionsoperationen kan fortolkes som "ligheden" af en funktion med en spejlet og forskudt kopi af en anden. Konvolutionsbegrebet er generaliseret for funktioner defineret på vilkårlige målbare rum og kan betragtes som en speciel form for integral transformation . I det diskrete tilfælde svarer foldningen til summen af værdier med koefficienter svarende til de forskudte værdier , dvs. $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$

Definition

Lad være to funktioner, der kan integreres med hensyn til Lebesgue-målet på rummet . Så er deres foldning den funktion, der er defineret af formlen $f,g:\mathbb {R} ^{n}\to \mathbb {R}$ $\mathbb {R} ^{n}$ $f*g:\mathbb {R} ^{n}\to \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.

Især for , formlen har formen $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.

Konvolutionen er defineret for næsten alle og kan integreres. $(f*g)(x)$ $x\in {\mathbb {R} ^{n))$

I det tilfælde, hvor , og funktioner er defineret på intervallet , kan foldningen skrives som $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.

For første gang findes integraler, som er en foldning af to funktioner, i Leonhard Eulers værker (1760'erne); senere optræder foldningen hos Laplace , Lacroix , Fourier , Cauchy , Poisson og andre matematikere. Udpegningen af foldningen af funktioner ved hjælp af en stjerne blev først foreslået af Vito Volterra i 1912 ved hans forelæsninger på Sorbonne (udgivet et år senere) [1] .

Egenskaber

Kommutativitet :

f*g=g*f

Associativitet :

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

Linearitet ( distributivitet med hensyn til addition og associativitet med multiplikation med en skalar ):

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

Differentieringsregel:

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

hvor angiver den afledede af en funktion i forhold til enhver variabel. $\mathrm{D}f$ $f$

Laplace transformation :

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

Fourier transform egenskab :

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

hvor betegner Fourier-transformationen af funktionen. ${\mathfrak {F}}[]$

Hvis er en diskret Fourier-transformationsmatrix , så: ${\mathcal {W}}$

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

hvor er symbolet for slutproduktet af matricer [2] [3] [4] [5] [6] , betegner Kronecker-produktet , er symbolet på Hadamard-produktet (identiteten er en konsekvens af referencens egenskaber skitse [7] ). $\bullet$ $\otimes$ $\circ$

Eksempel

Lad opgaven være at beregne, hvordan mængden af sne på ethvert stykke jord vil ændre sig afhængigt af tid. Løsningen på dette problem kan opdeles i to faser:

bygge en snefaldsmodel og en snesmeltningsmodel.
kombinere disse to modeller til én.

Opgaverne i det første trin løses ved observationer og eksperimenter, og opgaverne i det andet trin løses ved foldning af modellerne opnået på det første trin.

Lad, som et resultat af at løse problemet i den første fase, bygges to afhængigheder (matematiske modeller):

afhængighed af mængden af snefald på det aktuelle tidspunkt , ${\displaystyle {\color {Rød}g(t)))$
afhængighed af andelen af usmeltet sne af den tid, der er gået siden dens fald . ${\displaystyle {\color {Blå}f(\tau )))$

Hvis sneen ikke begyndte at smelte, kunne mængden af al nedbør beregnes ved at tilføje i det diskrete tilfælde: $G$

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

eller ved integration i tilfælde af kontinuerlig:

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

Men i dette tilfælde finder snesmeltning sted, og det afhænger desuden ikke kun af den aktuelle samlede snemængde, men også af på hvilket tidspunkt netop denne mængde sne faldt. Så sneen, der faldt for to uger siden, er måske allerede fordampet, mens sneen, der faldt for en halv time siden, stadig vil ligge og ikke engang begynder at tø op.

Det viser sig, at for sne, der faldt på forskellige tidspunkter, skal du bygge din egen smeltemodel og på en eller anden måde tilføje alle disse modeller sammen.

Til disse formål kan begrebet matematisk foldning bruges. Lad på tidspunktet for tiden betragtes sneen, der faldt på tidspunktet , da $t$ $\tau$

$\tau$ - tidspunktet for snefald. For eksempel 13:00;
${\displaystyle {\color {Rød}g(\tau )))$ - mængden af sne, der er faldet i øjeblikket. For eksempel 7 kg; ${\displaystyle {\tau ))$
$t$ er det tidspunkt, hvor vi skal kende snefaldets tilstand . For eksempel 15:00; $\tau$
$t-\tau$ - mængden af tid, der er gået fra nedbørsøjeblikket til beregningen af den resterende andel af sne. Det vil sige 15:00 − 13:00 ;
${\displaystyle {\color {Blå}f(t-\tau )))$ - andelen af sne, der ikke er smeltet efter at have ligget i timevis. $t-\tau$

Det er nødvendigt for hver mængde sne, der er faldet på tidspunktet t , at tilføje sættet af modeller til én funktion. Hvis vi gør dette, får vi summen i det diskrete tilfælde: ${\displaystyle {\color {Rød}g(\tau )))$ $\tau$ $f(t-\tau )$

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

eller integral i kontinuert:

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

Grafisk er funktionen vist nedenfor, hvor bidragene fra hver snebunke fra grafen er repræsenteret i forskellige farver . $w(t)$ ${\displaystyle {\color {Rød}g(x)))$

Funktionen simulerer fuldt ud opførselen af snefald i henhold til modellen . Så i grafen ovenfor kan du se, at den samlede mængde sne stiger i tre hop, men sneen begynder at smelte med det samme, uden at vente på, at anden nedbør falder. $w(t)$ ${\displaystyle {\color {Rød}g(x)))$

Konvolution på grupper

Lade være en gruppe udstyret med måle , og være to funktioner defineret på . Så er deres foldning funktionen $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\in G.

Oprulningsforanstaltninger

Lad der være et Borel -rum og to mål . Så er deres foldning målet $(\mathbb {R} ,{\mathcal {B}}(\mathbb {R} ))$ $\mu,\nu: \mathcal{B}(\mathbb{R}) \to \mathbb{R}$

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

hvor angiver produktet af foranstaltninger og . $\mu \nogle gange \nu$ $\mu$ $\nu$

Egenskaber

Lad være absolut kontinuerlig med hensyn til Lebesgue-målet . Vi betegner deres Radon-Nikodim-derivater : $\mu,\nu$ $m$

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

Så er den også absolut kontinuerlig med hensyn til , og dens Radon-Nikodim-afledte har formen $\mu * \nu$ $m$ $f_{\mu * \nu} = \frac{d \mu * \nu}{dm}$

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

Hvis er sandsynlighedsmål , så er det også et sandsynlighedsmål. $\mu,\nu$ $\mu * \nu$

Konvolution af distributioner

Hvis er fordelinger af to uafhængige stokastiske variable og , så $\mathbb{P}^X,\mathbb{P}^Y$ $x$ $Y$

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

hvor er fordelingen af summen . Især, hvis de er absolut kontinuerte og har tætheder , så er den tilfældige variabel også absolut kontinuert, og dens tæthed har formen: $\mathbb{P}^{X+Y}$ $X+Y$ $X,Y$ $f_X,f_Y$ $X+Y$

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

Se også

Noter

↑ Domínguez A. A History of the Convolution Operation // IEEE Pulse. - 2015. - Bd. 6, nr. 1. - S. 38-49. Arkiveret fra originalen den 3. februar 2016.
↑ Slyusar, VI (27. december 1996). "Slutprodukter i matricer i radarapplikationer" (PDF) . Radioelectronics and Communications Systems.– 1998, Vol. 41; Nummer 3 : 50-53. Arkiveret (PDF) fra originalen 2020-07-27 . Hentet 2020-08-01 . Forældet parameter brugt |deadlink=( hjælp )
↑ Slyusar, VI (1997-05-20). "Analytisk model af det digitale antennearray på basis af facesplittende matrixprodukter" (PDF) . Proc. ICATT-97, Kiev : 108-109. Arkiveret (PDF) fra originalen 2020-01-25 . Hentet 2020-08-01 . Forældet parameter brugt |deadlink=( hjælp )
↑ Slyusar, VI (1997-09-15). "Nye operationer af matricer produkt til applikationer af radarer" (PDF) . Proc. Direkte og omvendte problemer med elektromagnetisk og akustisk bølgeteori (DIPED-97), Lviv. : 73-74. Arkiveret (PDF) fra originalen 2020-01-25 . Hentet 2020-08-01 . Forældet parameter brugt |deadlink=( hjælp )
↑ Slyusar, VI (13. marts 1998). "En familie af ansigtsprodukter af matricer og dens egenskaber" (PDF) . Cybernetik og systemanalyse C/C af Cybernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379-384. DOI : 10.1007/BF02733426 . Arkiveret (PDF) fra originalen 2020-01-25 . Hentet 2020-08-01 . Forældet parameter brugt |deadlink=( hjælp )
↑ Slyusar, VI (2003). "Generaliserede ansigtsprodukter af matricer i modeller af digitale antennesystemer med ikke-identiske kanaler" (PDF) . Radioelektronik og kommunikationssystemer . 46 (10): 9-17. Arkiveret (PDF) fra originalen 2020-09-20 . Hentet 2020-08-01 . Forældet parameter brugt |deadlink=( hjælp )
↑ Ninh, Pham; Rasmus, Pagh (2013). Hurtige og skalerbare polynomielle kerner via eksplicitte feature maps . SIGKDD international konference om videnopdagelse og datamining. Foreningen for Datamaskiner. DOI : 10.1145/2487575.2487591 .

Litteratur

Kolmogorov A. N., Fomin S. V. Elementer i teorien om funktioner og funktionel analyse, - M .: Nauka, 2004 (7. udgave).
Shiryaev A. N. Sandsynlighed, - M . : Nauka. 1989.
Napalkov VV Konvolutionsligninger i flerdimensionelle rum. - M., Nauka, 1982. - Oplag 3500 eksemplarer. - 240 sek.

Links

Java Applet
Java Applet
Lineær og cyklisk foldning . Hentet: 15. november 2010. (Russisk)

Kompressionsmetoder _

Teori

Information	Egen Gensidig Entropi Betinget entropi Kompleksitet Redundans
Enheder	Bit Nat Nappe Hartley Hartley formel

Tabsfri

Entropi kompression	Asymmetriske talsystemer Huffman algoritme Adaptiv Huffman-algoritme Shannon-Fano algoritme Shannons algoritme Aritmetisk kodning ( interval ) Golomb koder Delta Universel kode Elias fibonacci
Ordbogsmetoder	RLE Tøm luften ud LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Andet	RLE CTW BWT MTF PPM DMC

Lyd

Teori	Konvolution PCM Aliasing Prøveudtagning Kotelnikovs teorem
Metoder	LPC LAR LSP WLPC CELP ACELP En lov μ-lov ADPCM MDCT Fourier transformation Psykoakustisk model
Andet	Audio kompressor Talekompression Båndkodning

Billeder

Vilkår	farverum Pixel Mætningsundersampling Kompressionsartefakter
Metoder	RLE DPCM fraktal wavelet EZW SPIHT LP Forbered PCL
Andet	Bitrate Standard testbillede PSNR Kvantisering

Video

Vilkår	Video egenskaber Ramme Rammetyper Videokvalitet
Metoder	Bevægelseskompensation Forbered Kvantisering wavelet
Andet	Video codec Teori om prisforvrængning CBR ABR VBR