Dyskretny uniwersalny denoiser

W teorii informacji i przetwarzaniu sygnałów Discrete Universal Denoiser ( DUDE ) jest schematem odszumiania służącym do odzyskiwania sekwencji w skończonym alfabecie, które zostały uszkodzone przez dyskretny kanał bez pamięci . DUDE został zaproponowany w 2005 roku przez Tsachy'ego Weissmana, Erika Ordentlicha, Gadiela Seroussiego, Sergio Verdú i Marcelo J. Weinbergera.

Przegląd

Discrete Universal Denoiser (DUDE) to schemat odszumiania , który szacuje nieznany sygnał ${\ Displaystyle x ^ {n} = \ lewo (x_ {1} \ ldots x_ {n} \ right )}$ nad skończonym alfabetem z hałaśliwej wersji ${\ Displaystyle z ^ {n} = \ lewo (z_ {1} \ ldots z_ {n} \ prawej)}$ . Podczas gdy większość odszumiania w literaturze dotyczącej przetwarzania sygnałów i statystyki dotyczy sygnałów w nieskończonym alfabecie (zwłaszcza sygnałów o wartościach rzeczywistych), DUDE odnosi się do skończonego przypadku alfabetu. Zakłada $, że$$hałaśliwa$ wersja jest generowana przez transmisję znany kanał bez .

Dla ustalonego parametru długości kontekstu , DUDE $n$ wystąpienia wszystkich ciągów o długości się w . $}}$${$ . Szacunkowa wartość jest określana na podstawie dwustronnego kontekstu $displaystyle {\ hat {x}} _ {$$ja$$i$${\ Displaystyle \ lewo (z_ {ik}, \ ldots, z_ {i-1}, z_ {i + 1}, \ ldots, z_ {i + k} \$ z ${\ displaystyle z_ {i}}$ , biorąc pod uwagę wszystkie inne tokeny w tym samym kontekście, a także znaną macierz kanałów i funkcję utraty z ja {\ $i}$ używany.

Pomysł leżący u podstaw KOLESA najlepiej ilustruje sytuacja, gdy ${n}}$ losowego wektora $^$ . Jeśli rozkład warunkowy $} \ ldots , Z_ {i + k}}$${\ Displaystyle X_ {i} | Z_ {ik}, \ ldots, Z_ {i-1}, Z_ {i +$$-$ , a mianowicie dystrybucja bezgłośnego symbolu ${\ Displaystyle \ lewo (Z_ {ik}, \ ldots, Z_ {i-1}, Z_ {i + 1}, \ ldots, Z_ {i + k} \ prawo )} był$ hałaśliwym kontekstem $dostępny$ , estymator byłby odpowiedzią ${\ Displaystyle X_ {i} | Z_ {ik}, \ ldots, Z_ {i-1}, Z_ {i + 1},\ldots ,Z_{i+k}}$ . Na szczęście, gdy macierz kanałów jest znana i niezdegenerowana, ten rozkład warunkowy można wyrazić za pomocą rozkładu warunkowego ${i + k}}$${\ Displaystyle Z_ {i} | Z_ {ik}, \ ldots, Z_ {i-1}, Z_ {i + 1},$$\ ldots,$ , a mianowicie rozkład hałaśliwego symbolu zależny od jego hałaśliwego kontekstu $rozkład z$ można oszacować na podstawie prawa wielkich liczb , pod warunkiem, że $„$ duży”.

Zastosowanie schematu DUDE z długością kontekstu $O$ sekwencji długości $Displaystyle$${\ Displaystyle O (n)}$ alfabetem wymaga ${\ mathcal {Z}}}$ operacje i przestrzeń ${\ Displaystyle O \ lewo (\ min (n, | {\ mathcal {Z}} | ^ {2k}) \ prawej)}$ .

Przy pewnych założeniach DUDE jest schematem uniwersalnym w sensie działania asymptotycznego, a także optymalnym denoiserem, który ma wyrocznię dostęp do nieznanej sekwencji. Dokładniej, załóżmy, że wydajność odszumiania jest mierzona przy użyciu danego kryterium wierności pojedynczego znaku i rozważmy reżim, w którym długość sekwencji $displaystyle$ do nieskończoności, a długość kontekstu $k = k_ {n}}$ dąży do nieskończoności „niezbyt szybko”. W ustawieniu stochastycznym, gdzie podwójnie nieskończona sekwencja bezgłośna sekwencja $\ mathbf {X}}$ realizacją procesu stacjonarnego , KOLEŚ wykonuje również asymptotycznie w oczekiwaniu $displaystyle$ jako najlepszy denoiser, który ma dostęp wyroczni do dystrybucji źródłowej ${\ displaystyle \ mathbf {X}}$ . W ustawieniu jednosekwencyjnym lub „półstochastycznym” ze stałą podwójnie nieskończoną sekwencją , DUDE asymptotycznie działa równie dobrze jak najlepszy denoiser „przesuwnego okna”, a mianowicie dowolny denoiser, $określa$${\ Displaystyle {\ kapelusz {x}} _ {i}}$ z okna ${\ Displaystyle \ lewo (z_ {ik}, \ ldots, z_ { i + k} \ right)}$ , który ma dostęp Oracle do ${\ displaystyle \ mathbf {x}}$ .

Dyskretny problem odszumiania

Schemat blokowy opis problemu odszumiania dyskretnego

Niech $będzie$ skończonym alfabetem ustalonej, ale nieznanej oryginalnej „bezszelestnej” sekwencji $\ Displaystyle x ^ {n} =\left(x_{1},\ldots,x_{n}\right)\in {\mathcal {X}}^{n}}$ . Sekwencja jest wprowadzana do dyskretnego kanału bez pamięci (DMC). DMC działa niezależnie na $,$$odpowiedni$$skończonym$ losowy symbol w DMC jest znany $podany$ jako ${\ Displaystyle \ pi (x, z) = \ mathbb {P} \ lewo (Z = z \, | \, X = x \ prawej)}$ Markowa , $π$$wpisy$ . Wygodnie jest napisać dla $\$ - $}}$$displaystyle \ pi _ {$ . DMC tworzy losową sekwencję szumów ${\ Displaystyle Z ^ {n} = \ lewo (z_ {1}, \ ldots, z_ {n} \ prawej) \ w {\mathcal {Z}}^{n}}$ . Konkretna realizacja tego losowego wektora będzie oznaczona przez ${\ displaystyle z ^ {n}}$ . Denoiser jest funkcją $}$${\ Displaystyle {\ kapelusz {X}} ^ {n}: {\ mathcal {Z}} ^ {n} \ do {\ mathcal {X}} ^ {n$$}}$ , który próbuje odzyskać bezszumową sekwencję $n$ zniekształconej wersji . Określona odszumiona sekwencja jest oznaczona przez ${\ Displaystyle {\ hat {x}} ^ { n}={\kapelusz {X}}^{n}\left(z^{n}\right)=\left({\kapelusz {X}}_{1}(z^{n}),\ldots ,{\kapelusz {X}}_{n}(z^{n})\right)}$ . Problem wyboru denoisera $jest$ znany jako szacowanie lub wygładzanie . Aby porównać kandydujących denoiserów, wybieramy kryterium wierności pojedynczego symbolu ${\ Displaystyle \ Lambda: {\ mathcal {X}} \ razy {\ mathcal {X}} \ do [0, \ infty )}$ (na przykład strata Hamminga) i zdefiniuj utratę denoisera na symbol ${\ Displaystyle {\ kapelusz {X}} ^ {n}}$ w ${\ styl wyświetlania (x^{n},z^{n})}$ wg

${\ Displaystyle {\ rozpocząć {wyrównane} L_ {{\ kapelusz {X}} ^ {n}} \ lewo (x ^ {n}, z ^ {n} \ prawej) = {\ Frac {1} {n} }\sum _{i=1}^{n}\Lambda \left(x_{i}\,,\,{\kapelusz {X}}_{i}(z^{n})\right)\, .\end{wyrównane}}}$

$\ Displaystyle {\ mathcal {X}} = \ lewo (a_ {1} ,\ldots ,a_{|{\mathcal {X}}|}\right)}$ alfabetu według $|$ , kryterium wierności może być określone jako ${\ Displaystyle | {\ mathcal {X}} |}$ -by- ${\ displaystyle | {\ mathcal {X}}|}$ macierz z kolumnami formularza

${\ Displaystyle {\ rozpocząć {wyrównane} \ lambda _ {\ kapelusz {x}} = \ lewo ({\ rozpocząć {tablica} {c} \ Lambda (a_ {1}, {\ kapelusz {x}}) \\ \vdots \\\Lambda (a_{|{\mathcal {X}}|},{\hat {x}})\end{array}}\right)\,.\end{aligned}}}$

Schemat DUDE

Krok 1: Obliczenie rozkładu empirycznego w każdym kontekście

DUDE koryguje symbole zgodnie z ich kontekstem. $Zastosowana$ długość kontekstu parametrem dostrajania schematu. k ${\ Displaystyle k + 1 \ równoważnik i \ równoważnik nk} zdefiniuj$ kontekst -tego symbolu w ${\ displaystyle i}$${\ displaystyle z ^ {n} }$ przez ${\ Displaystyle l ^ {k} (z ^ {n}, i) = \ lewo (z_ {ik}, \ldots, z_ {i-1} \ prawej)}$ i odpowiedni prawy kontekst jako ${\ Displaystyle r ^ {k} ( z^{n},i)=\left(z_{i+1},\ldots,z_{i+k}\right)}$ . $_$ dwustronny prawego

$w$ każdym możliwym dwustronnym kontekście wzdłuż hałaśliwej sekwencji . Formalnie dany kontekst dwustronny ${\ Displaystyle (l ^ {k}, r ^ {k}) \ in {\ mathcal {Z}} ^ {k} \times {\ mathcal {Z}} ^ {k}}$$,$ który pojawia się raz lub więcej wzdłuż, empiryczny rozkład prawdopodobieństwa na ${\ displaystyle {\ mathcal {Z}}$ } którego wartość przy symbolu wynosi ${\ displaystyle z}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ mu \ lewo (z ^ {n}, l ^ {k}, r ^ {k} \ prawej) [z] = {\ Frac {{\ duży |} \ lewo \ {k+1\leq i\leq nk\,\,|\,\,(z_{ik},\ldots,z_{i+k})=l^{k}zr^{k}\right\} {\Duży |}}{{\Duży |}\left\{k+1\równik i\równik nk\,\,|\,\,l^{k}(z^{n},i)=l ^{k}{\text{i }}r^{k}(z^{n},i)=r^{k}\right\}{\Duży |}}}\,.\end{wyrównane} }}$

$przeskanowanie$ schematu DUDE z długością kontekstu $zapisanie$ hałaśliwej sekwencji wejściowej i długości- ${\ Displaystyle | {\ mathcal {Z}}|}$ empiryczny wektor dystrybucji ${\ Displaystyle \ mu \ lewo (z ^ {n}, l ^ {k}, r ^ { k} \ right)}$ (lub jego nieznormalizowana wersja, wektor zliczania) dla każdego dwustronnego kontekstu znalezionego wzdłuż ${\ displaystyle z ^ {n}}$ . Ponieważ istnieje co najwyżej ${\ Displaystyle N_ {n, k} = \ min \ lewo (n, | {\ mathcal {Z}} | ^ {2k} \ prawej)}$ możliwe dwustronne konteksty wzdłuż $n$ ten krok wymaga operacji i przechowywania ${\ Displaystyle O (n)}$$Displaystyle O(N_{n,k})}$ .

Krok 2: Obliczanie odpowiedzi Bayesa dla każdego kontekstu

$,$ kolumnę $symbolu$ symbolowi przez ${\ Displaystyle \ lambda _ {\ kapelusz {x}}}$ . Definiujemy odpowiedź Bayesa na $dowolny$ długości ${\ Displaystyle | {\ mathcal {X}} |}$ z nieujemnymi wpisami jako

${\ Displaystyle {\ rozpocząć {wyrównane}} {\ kapelusz {X}} _ {Bayes} (\ mathbf {v}) = {\ tekst {argmin}} _ {{\ kapelusz {x}} \ w {\ mathcal { X}}}\lambda _{\hat {x}}^{\góra}\mathbf {v} \,.\end{wyrównane}}}$

Ta definicja jest uzasadniona w tle poniżej.

$każdego$ dwustronnego kontekstu zaobserwowanego w poprzednim kroku wzdłuż $\displaystyle z^{n}}$$)}$$obserwowanego$${\ Displaystyle l ^ {r} zr ^ {k}}$ każdego symbolu $w$ każdym kontekście (mianowicie każdy że jest podłańcuchem odpowiedzi Bayesa na wektor ${\ displaystyle z ^ {n}}$${\ Displaystyle \ Pi ^ {- \ top} \ mu \ lewo (z ^ {n} \ , \, l ^ {k} \ , \, r ^ {k} \ prawej) \ odot \pi _{z}}$ , a mianowicie

${\ Displaystyle {\ rozpocząć {wyrównane} g (l ^ {k}, z, r ^ {k}): = {\ kapelusz {X}} _ {Bayes} \ lewo (\ Pi ^ {- \ top} \ mu \left(z^{n}\,,\,l^{k}\,,\,r^{k}\right)\odot \pi _{z}\right)\,.\end{wyrównane }}}$

$,$ że sekwencja i $niejawne$ kontekstu . Tutaj ${\ Displaystyle \ pi _ {z}}$ jest $\$ -kolumny z ${\ Displaystyle \ Pi}$ i dla wektorów i za $Displaystyle \ mathbf {a}}$ i ${\ Displaystyle \ mathbf {b}}$ , ${\ Displaystyle \ mathbf {a} \ odot \ mathbf {b}}$ oznacza ich iloczyn Schur (wejściowy), zdefiniowany przez ${\ Displaystyle \left(\mathbf {a} \odot \mathbf {b} \right)_{i}=a_{i}b_{i}}$ . ${\ Displaystyle (\ Pi ^ {- \ wierzchołek} \ mu) \ dot \ pi _ {z}}$$.$ iloczynem Schura oznacza .

$}$ że macierz kanałów kwadratowa ( i odwracalna) $Pi$ . kiedy $mathcal {Z}} |} i$$\$ nie jest odwracalny, przy rozsądnym założeniu, że ma pełny rząd wierszy, zastępujemy ${\ Displaystyle (\ Pi ^ {\ top}) ^ {- 1}}$ powyżej z pseudoodwrotnością Moore'a-Penrose'a ${\ Displaystyle \ lewo (\ Pi \ Pi ^{\top }\right)^{-1}\Pi }$ i oblicz zamiast tego

${\ Displaystyle {\ rozpocząć {wyrównane} g (l ^ {k}, z, r ^ {k}): = {\ kapelusz {X}} _ {Bayes} \ lewo ((\ Pi \ Pi ^ {\ top })^{-1}\Pi \mu \left(z^{n},l^{k},r^{k}\right)\odot \pi _{z}\right)\,.\end {wyrównany}}}$

Przez buforowanie odwrotności lub pseudo-odwrotności $⊙$ λ $\ Displaystyle \ lambda _ {\ kapelusz {x}} \ odot$ dla odpowiednich par ${\ Displaystyle ({\ kapelusz {x}}, z) \ in {\ mathcal {X}} \ razy {\ mathcal {Z} }}$$}$ , ) $k$ }

Krok 3: Szacowanie każdego symbolu na podstawie odpowiedzi Bayesa na jego kontekst

Trzecim i ostatnim krokiem schematu DUDE jest ponowne zeskanowanie $^$${\ Displaystyle {\ kapelusz {X}} ^ {n} (z ^ {n}) = \ lewo ({\ kapelusz {X}} _ {1} (z ^ {n}) ,\ldots ,{\kapelusz {X}}_{n}(z^{n})\right)}$ odszumionej sekwencji . Odszumiony symbol wybrany do zastąpienia jest odpowiedzią Bayesa na dwustronny kontekst symbolu, a mianowicie z ja {\ displaystyle $i}}$

${\ Displaystyle {\ rozpocząć {wyrównane} {\ kapelusz {X}} _ {i} (z ^ {n}): = g \ lewo (l ^ {k} (z ^ {n}, i) \ ,, \,z_{i}\,,\,r^{k}(z^{n},i)\right)\,.\end{wyrównane}}}$

Ten krok wymaga $operacji$ strukturę danych skonstruowaną w poprzednim

$_$ cały $wymaga$ _ _

Asymptotyczne własności optymalności

DUDE jest zaprojektowany tak, aby był uniwersalnie optymalny, a mianowicie optymalny (przy pewnych założeniach ma to sens), niezależnie od oryginalnej sekwencji ${\ displaystyle x ^ {n}}$ .

Niech ${\ Displaystyle {\ kapelusz {X}} _ {KOLEŚ} ^ {n}: {\ mathcal {Z}} ^ {n} \ do {\ mathcal { X}} ^ {n}}$ oznaczają sekwencję schematów DUDE, jak opisano powyżej, gdzie ${\ displaystyle {\ kapelusz {X}} _ {DUDE} ^ {n}}$ używa długości kontekstu ${\ displaystyle k_ {n}},$ co jest ukryte w notacji. Wymagamy tylko, aby ${\ Displaystyle \ lim _ {n \ do \ infty} k_ {n} = \ infty}$ i że ${\ Displaystyle k_ {n} | {\ mathcal {Z}} | ^ {2K_ {n}} = o \ lewo ({\ Frac {n} {\ log n} }\prawo)}$ .

Dla źródła stacjonarnego

Oznacz przez $\$ wszystkich denoiserów $bloków$ , a mianowicie wszystkie mapy $\ kapelusz {X}}^{n}:{\mathcal {Z}}^{n}\do {\mathcal {X}}^{n}}$ .

Niech $będzie$ nieznanym źródłem stacjonarnym i $rozkładem$ odpowiedniej hałaśliwej sekwencji Następnie

${ \ Displaystyle {\ rozpocząć {wyrównane} \ lim _ {n \ do \ infty} \ mathbf {E} \ lewo [L _ {{\ kapelusz {X}} _ {KOLEŚ} ^ {n}} \ lewo (X ^ { n},Z^{n}\right)\right]=\lim _{n\to \infty}\min _{{\hat {X}}^{n}\in {\mathcal {D}}_ {n}}\mathbf {E} \left[L_{{\kapelusz {X}}^{n}}\left(X^{n},Z^{n}\right)\right]\,,\ koniec {wyrównany}}}$

i istnieją obie granice. Jeśli dodatkowo źródło jest ergodyczne, to ${\ displaystyle \ mathbf {X}}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ limsup _ {n \ do \ infty} L _ {{\ kapelusz {X}} _ {KOLEŚ} ^ {n}} \ lewo (X ^ {n}, Z ^ {n }\right)=\lim _{n\to \infty }\min _{{\hat {X}}^{n}\in {\mathcal {D}}_{n}}\mathbf {E} \ left[L_{{\kapelusz {X}}^{n}}\left(X^{n},Z^{n}\right)\right]\,,\,{\text{prawie na pewno}}\ ,.\end{wyrównane}}}$

Dla indywidualnej sekwencji

Oznacz przez ${\ Displaystyle {\ mathcal {D}} _ {n, k}}$ zestaw wszystkich denoiserów przesuwnych okien ${\ displaystyle n}$ -block ${\ displaystyle k} -tego rzędu, a mianowicie wszystkie$ mapy ${\ Displaystyle {\ kapelusz {X}} ^ {n}: {\ mathcal {Z}} \ do {\ mathcal {X}}}$ postaci ${\ Displaystyle {\ kapelusz {X}} _ {i} (z ^ {n}) = f \ lewo (z_ {ik}, \ ldots, z_ {i + k} \ prawej)}$ z dowolnie ${\ Displaystyle F: {\ mathcal {Z}} ^ {2k + 1} \ do {\ mathcal {X}}}$ .

Niech ${\ Displaystyle \ mathbf {x} \ in {\ mathcal {X}} ^ {\ infty}}$ będzie nieznanym, cichym sekwencyjnym źródłem stacjonarnym i będzie rozkładem ${\ Displaystyle \ mathbf {Z}}$ odpowiednią hałaśliwą sekwencję. Następnie

${\ Displaystyle {\ rozpocząć {wyrównane} \ lim _ {n \ do \ infty} \ lewo [L_ {{\ kapelusz {X}} _ {KOLEŚ} ^ {n}} \ lewo (x ^ {n}, Z ^{n}\right)-\min _{{\kapelusz {X}}^{n}\in {\mathcal {D}}_{n,k}}L_{{\kapelusz {X}}^{ n}}\left(x^{n},Z^{n}\right)\right]=0\,,\,{\text{prawie na pewno}}\,.\end{wyrównane}}}$

Wydajność nieasymptotyczna

Niech ${X}} _ {k} ^ {n}}$$na$$KOLEGO$ na z długością kontekstu zdefiniowaną -blokach. Wtedy istnieją jawne stałe, $)}$ zależą od ${\ Displaystyle A, C> 0}$$>$$\ Displaystyle B$ 1 samodzielnie, tak że dla dowolnego $∈$ dowolnego mamy x $Displaystyle x ^ {n} \ in {\ mathcal {X}} ^ {n$

${\ Displaystyle {\ rozpocząć {wyrównane} {\ Frac {A} {\ sqrt {n}}} B ^ {k} \, \ równoważnik \ mathbf {E} \ lewo [L_ {{\ kapelusz {X} }_{k}^{n}}\left(x^{n},Z^{n}\right)-\min _{{\kapelusz {X}}^{n}\in {\mathcal {D }}_{n,k}}L_{{\kapelusz {X}}^{n}}\left(x^{n},Z^{n}\right)\right]\leq {\sqrt {k }}{\frac {C}{\sqrt {n}}}|{\mathcal {Z}}|^{k}\,,\end{wyrównane}}}$

gdzie $jest$$.$ sekwencją odpowiadającą (której losowość wynika wyłącznie

$co$ samymi stałymi, powyżej dla każdego -block denoiser $n} \in {\mathcal {D}}^{n}}$$n$ . $była$ dolnej granicy wymaga, aby macierz kanału $kwadratowa$ para spełniała pewien

Tło

Aby uzasadnić konkretną definicję KOLEGO przy użyciu odpowiedzi Bayesa na określony wektor, znajdujemy teraz optymalny denoiser w przypadku nieuniwersalnym, w którym nieznana sekwencja jest realizacją a x $\ displaystyle x ^ {n}}$$,$ wektor którego rozkład jest znany

Rozważmy najpierw przypadek ${\ displaystyle n = 1}$ . Ponieważ wspólny rozkład $jest$ znany, biorąc pod uwagę obserwowany hałaśliwy symbol nieznany symbol $X}}}$$Displaystyle$$X \ w {$ jest dystrybuowane zgodnie ze znanym rozkładem ${\ Displaystyle \ mathbb {P} (X = x | Z = z)}$ . Zamawiając elementy , możemy opisać ten rozkład warunkowy na $\$${\ Displaystyle \ mathbf {P} _ {X| z}}$$displaystyle {\ mathcal {X}}}$ za pomocą wektora prawdopodobieństwa , indeksowane przez ${\ Displaystyle {\ mathcal {X}}}$ , którego wpisem jest ${\ Displaystyle x}$${\ Displaystyle \ mathbb {P} \ lewo (X = x | Z = z \ prawej)}$ . Oczywiście oczekiwana ${\ Displaystyle \ lambda _ {\ kapelusz {x}} ^ {\ top} \ mathbf {P} _ {X | z}}$ wyborze szacowanego $|$ wynosi .

Zdefiniuj $}}}$ Bayesa wektora prawdopodobieństwa $,$ opisując rozkład prawdopodobieństwa na $v$ minimalną oczekiwaną stratę ${\ Displaystyle U (\ mathbf {v}) = \ min _ {{\ kapelusz {x}} \ w {\ mathcal {X}}} \ mathbf {v} ^ {\ top}$${\ Displaystyle {\ kapelusz {X}} _ {Bayes} (\ mathbf {v}) = {\ tekst {argmin}} _ {{\ kapelusz {x}} \ w {\ mathcal { X}}}\mathbf {v} ^{\top }\lambda _{\hat {x}}}$$x$ i odpowiedź Bayesa na jako przewidywanie, które osiąga to minimum, . Zauważ, że odpowiedź Bayesa jest niezmienna w skali w tym sensie, że ${\ Displaystyle {\ hat {X}} _ {Bayes} (\ mathbf {v}) = {\ hat {X}} _ {Bayes} (\ alfa \ mathbf {v})}$ dla ${\ Displaystyle \ alpha> 0}$ .

W przypadku ${\ Displaystyle n = 1}$ optymalnym denoiserem jest ${\ Displaystyle {\ hat {X}} ( z)={\kapelusz {X}}_{Bayes}\left(\mathbf {P} _{X|z}\right)}$ . Ten optymalny denoiser można wyrazić za pomocą samego rozkładu krańcowego $w$ sposób. Kiedy macierz kanałów $_$$odwracalna$ , mamy _ $Displaystyle \ pi _ {z}}$${\ displaystyle \ Pi}$ to $kolumna$ Π . Oznacza to, że optymalny denoiser jest podany równoważnie przez ${\ Displaystyle {\ kapelusz {X}} (z) = {\ kapelusz {X}}_{Bayes}\left(\Pi ^{-\top }\mathbf {P} _{Z}\odot \pi _{z}\right)}$ . kiedy $mathcal {Z}} |} i$$\$ nie jest odwracalny, przy rozsądnym założeniu, że ma pełny rząd wierszy, możemy zastąpić ${\ Displaystyle \ Pi ^ {- 1}}$ z pseudoodwrotnością Moore'a-Penrose'a i otrzymać

${\ Displaystyle {\ kapelusz {X}} (z) = {\ kapelusz {X}} _ {Bayes} \ lewo ((\ Pi \ Pi ^ {\ wierzchołek}) ^ {- 1} \ Pi \ mathbf {P } _{Z}\odot \pi _{z}\right)\,.}$

Przechodząc teraz do arbitralnego $n$${$ z oczekiwaną stratą ) jest zatem dana przez odpowiedź Bayesa na ${\ Displaystyle \ mathbf {P} _ {X_ {i} | z ^ {n}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} {\ kapelusz {X}} _ {i} ^ {opt} (z ^ {n}) = {\ kapelusz {X}} _ {Bayes} \ mathbf {P } _{X_{i}|z^{n}}={\text{argmin}}_{{\kapelusz {x}}\in {\mathcal {X}}}\lambda _{\kapelusz {x} }^{\top }\mathbf {P} _{X_{i}|z^{n}}\,,\end{wyrównane}}}$

gdzie ${\ Displaystyle \ mathbf {P} _ {X_ {i} | z ^ {n}}}$ jest wektorem indeksowanym przez ${\ Displaystyle {\ mathcal {X}}}$ , którego ${\ Displaystyle x}$ - wpis jest ${\ Displaystyle \ mathbb {P} \ lewo (X_ {i} = x | Z ^ {n} = z ^ {n} \ prawej)}$ . Warunkowy wektor prawdopodobieństwa ${\ Displaystyle \ mathbf {P} _ {X_ {i}| z ^ {n}}}$ jest trudne do obliczenia. Wyprowadzenie analogiczne do powyższego przypadku $, że$${\ Displaystyle {\ kapelusz {X}} _ {i} ^ {opt} (z ^ {n}) = {\ kapelusz {X}} _ {Bayes} \left(\Pi ^{-\top }\mathbf {P} _{Z_{i},z^{n\backslash i}}\odot \pi _{z_{i}}\right)} ,$ denoiser dopuszcza alternatywną reprezentację, a gdzie ${\ Displaystyle z ^ {n \ backslash i} = \ lewo (z_ {1}, \ldots ,z_{i-1},z_{i+1},\ldots ,z_{n}\right)\in {\mathcal {Z}}^{n-1}} to dany wektor$ i ${\ Displaystyle \ mathbf {P} _ {Z_ {i}, z ^ {n \ ukośnik odwrotny i}}}$ jest wektorem prawdopodobieństwa indeksowanym przez ${\ Displaystyle {\ mathcal {Z}}},$ którego ${\ Displaystyle z}$ -wpis jest $⊤ {$${\ Displaystyle \ mathbb {P} \ lewo ((Z_ {1}, \ ldots, Z_ {n}) = (z_ {1}, \ ldots, z_ {i-1}, z, z_ {i + 1}$${\ Displaystyle \ Pi ^ {- \ top}}$ jest zastępowane przez pseudo-odwrotność, jeśli nie jest $\ Displaystyle \ Pi ^ {- \ top}$ } kwadratowy lub nieodwracalny.

Gdy dystrybucja (a zatem $)$ nie jest dostępna, KOLEJ zastępuje nieznany wektor $\ backslash i}}}$$ja$${ Z_ {i}, z ^ {$${\ Displaystyle \ mu \ lewo (Z_ {i}, l ^ {k} (Z ^ {n}, ja), r ^ {k} (Z ^ {n },i)\prawo)}$ z empirycznym oszacowaniem uzyskanym wzdłuż samej hałaśliwej sekwencji $Z$ mianowicie z . Prowadzi to do powyższej definicji KOLEGO.

Chociaż argumenty zbieżności stojące za powyższymi właściwościami optymalności są bardziej subtelne, zauważamy, że powyższe, w połączeniu z twierdzeniem ergodycznym Birkhoffa , wystarczy, aby udowodnić, że dla stacjonarnego źródła ergodycznego KSIĄŻKA o długości kontekstu jest ${\ displaystyle k}$ asymptotycznie optymalne wszystkie $.$ przesuwanego okna -tego rzędu

Rozszerzenia

Podstawowy DUDE, jak opisano tutaj, zakłada sygnał z jednowymiarowym indeksem ustawionym na skończonym alfabecie, znanym kanale bez pamięci i długości kontekstu, która jest z góry ustalona. Rozważono kolejno złagodzenia każdego z tych założeń. Konkretnie:

• Nieskończone alfabety
• Kanały z pamięcią
• Nieznana macierz kanałów
• Zmienny kontekst i adaptacyjny wybór długości kontekstu
• Sygnały dwuwymiarowe

Aplikacje

Zastosowanie do odszumiania obrazu

Oparta na DUDE struktura do odszumiania obrazów w skali szarości zapewnia najnowocześniejsze usuwanie szumów dla impulsowych kanałów szumów (np. porównywalny ze schematem odszumiania obrazu środków nielokalnych na tym kanale). Inny wariant DUDE mający zastosowanie do obrazów w skali szarości jest przedstawiony w.

Aplikacja do dekodowania kanałów nieskompresowanych źródeł

DUDE doprowadził do powstania uniwersalnych algorytmów dekodowania kanałów nieskompresowanych źródeł.