Konvolution (matematisk analys)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 december 2021; kontroller kräver 2 redigeringar .

Konvolution , faltning är en operation i funktionsanalys , som, när den tillämpas på två funktioner och returnerar en tredje funktion som motsvarar korskorrelationsfunktionen och . Faltningsoperationen kan tolkas som "likheten" av en funktion med en speglad och förskjuten kopia av en annan. Begreppet faltning är generaliserat för funktioner definierade på godtyckliga mätbara utrymmen , och kan betraktas som en speciell typ av integrerad transformation . I det diskreta fallet motsvarar faltningen summan av värden med koefficienter som motsvarar de förskjutna värdena , 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

Låta vara två funktioner integrerbara med avseende på Lebesgue-måttet på utrymmet . Då är deras faltning den funktion som definieras av formeln $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.

Speciellt för , har formeln 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 definieras för nästan alla och är integrerbar. $(f*g)(x)$ $x\in {\mathbb {R} ^{n))$

I fallet när , och funktioner är definierade på intervallet , kan faltningen skrivas 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.

För första gången återfinns integraler, som är en konvolution av två funktioner, i verk av Leonhard Euler (1760-talet); senare dyker faltningen upp i Laplace , Lacroix , Fourier , Cauchy , Poisson och andra matematiker. Beteckningen av faltningen av funktioner med hjälp av en asterisk föreslogs först av Vito Volterra 1912 vid hans föreläsningar vid Sorbonne (publicerad ett år senare) [1] .

Egenskaper

Kommutativitet :

f*g=g*f

Associativitet :

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

Linjäritet ( distributivitet med avseende på addition och associativitet med multiplikation med en skalär ):

(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

där anger derivatan av en funktion med avseende på vilken variabel som helst. $\mathrm{D}f$ $f$

Laplace transformation :

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

Fourier transform egenskap :

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

där betecknar Fouriertransformen av funktionen. ${\mathfrak {F}}[]$

Om är en diskret Fourier-transformmatris , då: ${\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

var är symbolen för slutprodukten av matriser [2] [3] [4] [5] [6] , betecknar Kronecker-produkten , är symbolen för Hadamard-produkten (identiteten är en konsekvens av referensens egenskaper skiss [7] ). $\bullet$ $\otimes$ $\circ$

Exempel

Låt uppgiften vara att räkna ut hur mängden snö på någon bit mark kommer att förändras beroende på tid. Lösningen på detta problem kan delas in i två steg:

bygga en snöfallsmodell och en snösmältningsmodell.
på något sätt kombinera dessa två modeller till en.

Uppgifterna i det första steget löses genom observationer och experiment, och uppgifterna i det andra steget löses genom faltning av modellerna som erhållits i det första steget.

Låt, som ett resultat av att lösa problemet i det första skedet, två beroenden (matematiska modeller) byggdes:

beroende av mängden snöfall på den aktuella tiden , ${\displaystyle {\color {Röd}g(t)))$
beroende av andelen osmält snö av den tid som förflutit sedan dess fall . ${\displaystyle {\color {Blå}f(\tau )))$

Om snön inte började smälta kunde mängden av all nederbörd beräknas genom att lägga till i det diskreta fallet: $G$

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

eller genom integration i fallet med kontinuerlig:

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

Men i det här fallet sker snösmältning och dessutom beror det inte bara på den nuvarande totala mängden snö, utan också på vid vilken tidpunkt just denna mängd snö föll. Så snön som föll för två veckor sedan kan redan ha avdunstat, medan snön som föll för en halvtimme sedan fortfarande kommer att ligga och inte ens börja tina.

Det visar sig att för snö som föll vid olika tidpunkter måste du bygga din egen smältmodell och på något sätt lägga ihop alla dessa modeller.

För dessa ändamål kan begreppet matematisk faltning användas. Låt vid tidens ögonblick den snö som föll vid tidens ögonblick anses alltså $t$ $\tau$

$\tau$ - tidpunkten för snöfall. Till exempel, 13:00;
${\displaystyle {\color {Röd}g(\tau )))$ - mängden snö som har fallit för tillfället. Till exempel, 7 kg; ${\displaystyle {\tau ))$
$t$ är den tidpunkt för vilken vi behöver veta tillståndet för snöfallet. Till exempel, 15:00; $\tau$
$t-\tau$ - hur lång tid som förflutit från nederbördsögonblicket fram till beräkningen av den återstående andelen snö. Det vill säga 15:00 − 13:00 ;
${\displaystyle {\color {Blå}f(t-\tau )))$ - andelen snö som inte har smält efter att ha legat i timmar. $t-\tau$

Det är nödvändigt för varje mängd snö som har fallit vid tidpunkten t att lägga till uppsättningen modeller till en funktion. Om vi gör detta får vi summan i det diskreta fallet: ${\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 kontinuerlig:

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

Grafiskt visas funktionen nedan, där bidragen från varje snöhög från grafen är representerade i olika färger . $w(t)$ ${\displaystyle {\color {Röd}g(x)))$

Funktionen simulerar helt beteendet hos snö som faller enligt modellen . Så i grafen ovan kan du se att den totala mängden snö ökar i tre hopp, men snön börjar smälta direkt, utan att vänta på att annan nederbörd ska falla. $w(t)$ ${\displaystyle {\color {Röd}g(x)))$

Konvolution på grupper

Låta vara en grupp utrustad med mått , och vara två funktioner definierade på . Sedan är deras faltning 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.

Sammanställda åtgärder

Låt det finnas ett Borel- utrymme och två mått . Då är deras konvolution måttet $(\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\}\ höger),\quad \forall A\in {\mathcal {B}}(\mathbb {R} ),

där betecknar produkten av åtgärder och . $\mu \ibland \nu$ $\mu$ $\nu$

Egenskaper

Låt vara absolut kontinuerlig med avseende på Lebesgue-måttet . Vi betecknar deras Radon-Nikodim-derivat : $\mu,\nu$ $m$

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

Sedan är den också absolut kontinuerlig med avseende på , och dess Radon-Nikodim-derivat har formen $\mu * \nu$ $m$ $f_{\mu * \nu} = \frac{d \mu * \nu}{dm}$

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

Om är sannolikhetsmått , då är också ett sannolikhetsmått. $\mu,\nu$ $\mu * \nu$

Konvolution av distributioner

Om är fördelningar av två oberoende slumpvariabler och , då $\mathbb{P}^X,\mathbb{P}^Y$ $X$ $Y$

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

var är fördelningen av summan . I synnerhet, om de är absolut kontinuerliga och har tätheter , är den slumpmässiga variabeln också absolut kontinuerlig och dess densitet har formen: $\mathbb{P}^{X+Y}$ $X+Y$ $X,Y$ $f_X,f_Y$ $X+Y$

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

Se även

Anteckningar

↑ Domínguez A. A History of the Convolution Operation // IEEE Pulse. - 2015. - Vol. 6, nr. 1. - S. 38-49. Arkiverad från originalet den 3 februari 2016.
↑ Slyusar, VI (27 december 1996). "Slutprodukter i matriser i radarapplikationer" (PDF) . Radioelectronics and Communications Systems.– 1998, Vol. 41; Nummer 3 : 50-53. Arkiverad (PDF) från originalet 2020-07-27 . Hämtad 2020-08-01 . Utfasad parameter används |deadlink=( hjälp )
↑ Slyusar, VI (1997-05-20). "Analytisk modell av den digitala antennuppsättningen på basis av ansiktsdelande matrisprodukter" (PDF) . Proc. ICATT-97, Kiev : 108-109. Arkiverad (PDF) från originalet 2020-01-25 . Hämtad 2020-08-01 . Utfasad parameter används |deadlink=( hjälp )
↑ Slyusar, VI (1997-09-15). "Ny drift av matrisprodukt för tillämpningar av radar" (PDF) . Proc. Direkta och omvända problem med elektromagnetisk och akustisk vågteori (DIPED-97), Lviv. 73-74. Arkiverad (PDF) från originalet 2020-01-25 . Hämtad 2020-08-01 . Utfasad parameter används |deadlink=( hjälp )
↑ Slyusar, VI (13 mars 1998). "En familj av ansiktsprodukter av matriser och dess egenskaper" (PDF) . Cybernetik och systemanalys C/C för Cybernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379-384. DOI : 10.1007/BF02733426 . Arkiverad (PDF) från originalet 2020-01-25 . Hämtad 2020-08-01 . Utfasad parameter används |deadlink=( hjälp )
↑ Slyusar, VI (2003). "Generaliserade ansiktsprodukter av matriser i modeller av digitala antennuppsättningar med icke-identiska kanaler" (PDF) . Radioelektronik och kommunikationssystem . 46 (10): 9-17. Arkiverad (PDF) från originalet 2020-09-20 . Hämtad 2020-08-01 . Utfasad parameter används |deadlink=( hjälp )
↑ Ninh, Pham; Rasmus, Pagh (2013). Snabba och skalbara polynomkärnor via explicita funktionskartor . SIGKDD internationell konferens om Knowledge Discovery and data mining. Föreningen för Datormaskiner. DOI : 10.1145/2487575.2487591 .

Litteratur

Kolmogorov A. N., Fomin S. V. Element i teorin om funktioner och funktionell analys, - M .: Nauka, 2004 (7:e upplagan).
Shiryaev A. N. Sannolikhet, - M . : Nauka. 1989.
Napalkov VV Konvolutionsekvationer i flerdimensionella rum. - M., Nauka, 1982. - Upplaga 3500 ex. — 240 s.

Länkar

Java applet
Java applet
Linjär och cyklisk faltning . Hämtad: 15 november 2010. (ryska)

Kompressionsmetoder _

Teori

Information	Egen Ömsesidig Entropi Villkorlig entropi Komplexitet Redundans
Enheter	Bit Nat Knapra Hartley Hartley formel

Förlust mindre

Entropikompression	Asymmetriska talsystem Huffman algoritm Adaptiv Huffman-algoritm Shannon-Fano algoritm Shannons algoritm Aritmetisk kodning ( intervall ) Golomb-koder Delta Universell kod Elias fibonacci
Ordboksmetoder	RLE Töm luften LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Övrig	RLE CTW BWT MTF PPM DMC

Audio

Teori	Veck PCM Aliasing Provtagning Kotelnikovs teorem
Metoder	LPC LAR LSP WLPC CELP ACELP En lag μ-lag ADPCM MDCT Fouriertransform Psykoakustisk modell
Övrig	Ljudkompressor Talkompression Bandkodning

Bilder

Villkor	färg rymd Pixel Mättnad delsampling Kompressionsartefakter
Metoder	RLE DPCM fraktal vågkomponent EZW SPIHT LP PrEP PCL
Övrig	Bithastighet Standard testbild PSNR Kvantisering

Video

Villkor	Videoegenskaper Ram Ramtyper Videokvalitét
Metoder	Rörelsekompensation PrEP Kvantisering vågkomponent
Övrig	Video codec Rate distortion theory CBR ABR VBR