Konvoluce (matematická analýza)

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 28. prosince 2021; kontroly vyžadují 2 úpravy .

Konvoluce , konvoluce je operace ve funkcionální analýze , která při aplikaci na dvě funkce vrací třetí funkci odpovídající funkci vzájemné korelace a . Operaci konvoluce lze interpretovat jako „podobnost“ jedné funkce se zrcadlenou a posunutou kopií jiné. Pojem konvoluce je zobecněn pro funkce definované na libovolných měřitelných prostorech a lze jej považovat za zvláštní druh integrální transformace . V diskrétním případě konvoluce odpovídá součtu hodnot s koeficienty odpovídajícími posunutým hodnotám , tj. $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)+\tečky$

Definice

Dovolit být dvě funkce integrovatelné s ohledem na Lebesgue opatření na prostoru . Pak je jejich konvoluce funkcí definovanou vzorcem $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.

Konkrétně pro , vzorec má tvar $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.

Konvoluce je definována téměř pro všechny a je integrovatelná. $(f*g)(x)$ $x\in {\mathbb {R} ^{n))$

V případě, kdy jsou funkce a funkce definovány na intervalu , lze konvoluci zapsat jako $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.

Poprvé se integrály, které jsou konvolucí dvou funkcí, nacházejí v dílech Leonharda Eulera (60. léta 18. století); později se konvoluce objevuje u Laplacea , Lacroixe , Fouriera , Cauchyho , Poissona a dalších matematiků. Označení konvoluce funkcí pomocí hvězdičky poprvé navrhl Vito Volterra v roce 1912 na svých přednáškách na Sorbonně (vyšlo o rok později) [1] .

Vlastnosti

komutativnost :

f*g=g*f

Asociativita :

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

Linearita ( distributivita s ohledem na sčítání a asociativita s násobením skalárem ):

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

Pravidlo diferenciace:

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

kde označuje derivaci funkce vzhledem k jakékoli proměnné. $\mathrm{D}f$ $F$

Laplaceova transformace :

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

Vlastnost Fourierovy transformace :

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

kde označuje Fourierovu transformaci funkce. ${\mathfrak {F}}[]$

Pokud je matice diskrétní Fourierovy transformace , pak: ${\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

kde je symbol konečného produktu matric [2] [3] [4] [5] [6] , označuje produkt Kronecker , je symbol produktu Hadamard (identita je důsledkem vlastností reference skica [7] ). $\bullet$ $\otimes$ $\circ$

Příklad

Úkolem nechť je vypočítat, jak se bude množství sněhu na kterémkoli pozemku měnit v závislosti na čase. Řešení tohoto problému lze rozdělit do dvou fází:

postavit model sněžení a model tání sněhu.
nějak spojit tyto dva modely do jednoho.

Úlohy prvního stupně se řeší pozorováním a experimenty a úkoly druhého stupně se řeší konvolucí modelů získaných na prvním stupni.

Nechť, jako výsledek řešení problému v první fázi, byly vytvořeny dvě závislosti (matematické modely):

závislost množství sněhu na aktuálním čase , ${\displaystyle {\color {Červená}g(t)))$
závislost podílu neroztátého sněhu na době uplynulé od jeho pádu . ${\displaystyle {\color {Blue}f(\tau )))$

Pokud sníh nezačal tát, množství všech srážek by se dalo vypočítat přidáním v diskrétním případě: $G$

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

nebo integrací v případě nepřetržitého:

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

Ale v tomto případě k tání sněhu dochází a navíc záleží nejen na aktuálním celkovém množství sněhu, ale také na tom, v jakém časovém okamžiku toto konkrétní množství sněhu napadlo. Takže sníh, který napadl před dvěma týdny, se už možná vypařil, zatímco sníh, který napadl před půl hodinou, bude stále ležet a ani nezačne tát.

Ukazuje se, že pro sníh, který napadl v různých časech, si musíte sestavit svůj vlastní model tání a všechny tyto modely nějak sečíst.

Pro tyto účely lze použít koncept matematické konvoluce. Nechť je v daném okamžiku uvažován sníh, který v daném okamžiku napadl $t$ $\tau$

$\tau$ - čas sněžení. Například 13:00;
${\displaystyle {\color {Červená}g(\tau )))$ - množství sněhu, které v tuto chvíli napadlo. Například 7 kg; ${\displaystyle {\tau ))$
$t$ je časový okamžik, kdy potřebujeme znát stav sněžení. Například 15:00; $\tau$
$t-\tau$ - množství času, které uplynulo od okamžiku srážek do výpočtu zbývajícího podílu sněhu. Tedy 15:00 − 13:00 ;
${\displaystyle {\color {Blue}f(t-\tau )))$ - podíl sněhu, který neroztál po hodinách ležení. $t-\tau$

Za každé množství sněhu, které napadlo v čase t , je nutné přidat sadu modelů do jedné funkce. Pokud to uděláme, dostaneme součet v diskrétním případě: ${\displaystyle {\color {Červená}g(\tau )))$ $\tau$ $f(t-\tau )$

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

nebo integrál v spojitém:

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

Graficky je funkce znázorněna níže, kde jsou příspěvky každé hromady sněhu z grafu znázorněny různými barvami . $w(t)$ ${\displaystyle {\color {Červená}g(x)))$

Funkce plně simuluje chování padajícího sněhu podle modelu . Na výše uvedeném grafu tedy můžete vidět, že celkové množství sněhu naroste ve třech skocích, ale sníh začne okamžitě tát, aniž by čekal na padnutí dalších srážek. $w(t)$ ${\displaystyle {\color {Červená}g(x)))$

Konvoluce na skupinách

Dovolit být skupina obdařená opatřením a být dvě funkce definované na . Pak je funkcí jejich konvoluce $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.

Souhrnná opatření

Nechť existuje prostor Borel a dvě míry . Pak je měřítkem jejich konvoluce $(\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\}\ vpravo),\quad \forall A\in {\mathcal {B}} (\mathbb {R} ),

kde označuje součin měr a . $\mu \otimes \nu$ $\mu$ $\nu$

Vlastnosti

Dovolit být absolutně spojité s ohledem na Lebesgueovu míru . Označujeme jejich deriváty Radon-Nikodim : $\mu,\nu$ $m$

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

Pak je také absolutně spojitý vzhledem k , a jeho Radon-Nikodimský derivát má tvar $\mu * \nu$ $m$ $f_{\mu * \nu} = \frac{d \mu * \nu}{dm}$

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

Jestliže jsou míry pravděpodobnosti , pak je také míra pravděpodobnosti. $\mu,\nu$ $\mu * \nu$

Konvoluce distribucí

Jestliže jsou rozdělení dvou nezávislých náhodných veličin a , pak $\mathbb{P}^X,\mathbb{P}^Y$ $X$ $Y$

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

kde je rozdělení součtu . Konkrétně, pokud jsou absolutně spojité a mají hustoty , pak je náhodná veličina také absolutně spojitá a její hustota má tvar: $\mathbb{P}^{X+Y}$ $X+Y$ $X,Y$ $f_X, f_Y$ $X+Y$

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

Viz také

Poznámky

↑ Domínguez A. Historie operace konvoluce // Puls IEEE. - 2015. - Sv. 6, č. 1. - S. 38-49. Archivováno z originálu 3. února 2016.
↑ Slyusar, VI (27. prosince 1996). “Koncové produkty v matricích v radarových aplikacích” (PDF) . Radioelektronika a komunikační systémy. – 1998, sv. 41; Číslo 3 : 50-53. Archivováno (PDF) z originálu dne 27.07.2020 . Staženo 2020-08-01 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Slyusar, VI (1997-05-20). „Analytický model digitálního anténního pole na bázi produktů face-splitting matrix“ (PDF) . Proč. ICATT-97, Kyjev : 108-109. Archivováno (PDF) z originálu dne 25.01.2020 . Staženo 2020-08-01 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Slyusar, VI (1997-09-15). „Nové operace maticového produktu pro aplikace radarů“ (PDF) . Proč. Přímé a inverzní problémy teorie elektromagnetických a akustických vln (DIPED-97), Lvov. : 73-74. Archivováno (PDF) z originálu dne 25.01.2020 . Staženo 2020-08-01 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Slyusar, VI (13. března 1998). „Rodina maticových produktů pro tváře a její vlastnosti“ (PDF) . Kybernetika a systémová analýza C/C of Cybernetika I Sistemnyi Analiz.- 1999 . 35 (3): 379-384. DOI : 10.1007/BF02733426 . Archivováno (PDF) z originálu dne 25.01.2020 . Staženo 2020-08-01 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Slyusar, VI (2003). „Zobecněné obličejové produkty matic v modelech digitálních anténních polí s neidentickými kanály“ (PDF) . Radioelektronika a komunikační systémy . 46 (10): 9-17. Archivováno (PDF) z originálu dne 20.09.2020 . Staženo 2020-08-01 . Použitý zastaralý parametr |deadlink=( nápověda )
↑ Ninh, Pham; Rasmus, Pagh (2013). Rychlá a škálovatelná polynomiální jádra prostřednictvím explicitních map funkcí . Mezinárodní konference SIGKDD o objevování znalostí a dolování dat. Asociace pro výpočetní techniku. DOI : 10.1145/2487575.2487591 .

Literatura

Kolmogorov A. N., Fomin S. V. Základy teorie funkcí a funkcionální analýza, - M.: Nauka, 2004 (7. vyd.).
Shiryaev A. N. Pravděpodobnost, - M . : Nauka. 1989.
Napalkov VV Konvoluční rovnice ve vícerozměrných prostorech. - M., Nauka, 1982. - Náklad 3500 výtisků. — 240 s.

Odkazy

Java applet
Java applet
Lineární a cyklická konvoluce . Staženo: 15. listopadu 2010. (Ruština)

Kompresní metody

Teorie

Informace	Vlastní Vzájemné Entropie Podmíněná entropie Složitost Nadbytek
Jednotky	Bit Nat Okusovat Hartley Hartleyho vzorec

Bezztrátový

Entropická komprese	Asymetrické číselné soustavy Huffmanův algoritmus Adaptivní Huffmanův algoritmus Shannon-Fano algoritmus Shannonův algoritmus Aritmetické kódování ( interval ) Golombovy kódy Delta Univerzální kód Eliáš fibonacci
Slovníkové metody	RLE Vyfouknout LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
jiný	RLE CTW BWT MTF PPM DMC

Zvuk

Teorie	Konvoluce PCM Aliasing Vzorkování Kotelnikovova věta
Metody	LPC LAR LSP WLPC CELP ACELP Zákon μ-zákon ADPCM MDCT Fourierova transformace Psychoakustický model
jiný	Audio kompresor Komprese řeči Pásmové kódování

snímky

Podmínky	barevný prostor Pixel Saturační podvzorkování Kompresní artefakty
Metody	RLE DPCM fraktál vlnka EZW SPIHT LP Přípravka PCL
jiný	Bitová rychlost Standardní testovací obrázek PSNR Kvantování

Video

Podmínky	Vlastnosti videa Rám Typy rámů Kvalita videa
Metody	Kompenzace pohybu Přípravka Kvantování vlnka
jiný	Video kodek Teorie zkreslení sazby CBR ABR VBR