5.5. 5.5. Iterációs módszer a relatív kapacitás meghatározására (kiegészítő tananyag)

A szakasz kitekintést ad arra, hogyan lehetne az Arimoto-Blahut algoritmust általánosítani, ha zajos csatorna esetén a jelek különböző idő alatt mennek át, azaz additív költség esetén [ 14 ].

5.13. Definíció. Relatív kapacitásnak nevezzük a csatornán ténylegesen átvitt információ és a forrásentrópia hányadosát:

Legyen a és bemeneti eloszlásvektorok halmaza a következőképpen definiálva:

és

valamint legyen

az adókarakterisztika mátrix.

Ekkor a csatornán átvitt információmennyiséget a következőképpen számolhatjuk ki:

Az egyszerűség kedvéért legyen

ahol kimeneti eloszlás, mely mátrix-vektor szorzással meghatározható.

Az jelölésbeni egyszerűsítés után az átvitt információmennyiség:

Ezek után vezessünk be egy költségváltozót minden -dik bemeneti szimbólumhoz, valamint legyen költségfüggvény

A relatív kapacitást a következőképpen definiálta Reza(1961):

Az iterációs algoritmus a következő:

  1. Legyen

  2. Legyen tetszőleges bemeneti eloszlás.

  3. A valószínűségi vektor után határozzuk meg a vektort a következőképpen

5.14. Tétel. Az

sorozat monoton növekvő és konvergál a relatív kapacitáshoz.

Bizonyítás. Először is azt mutatjuk meg, hogy az eljárás által kapott

sorozat monoton növekvő. Jelöljük -vel és -rel a -adik és a -edik valószínűségi vektorokat, melyeket az előbbi iterációs formulával kapunk. Legyen

Ekkor nyilvánvalóan

Legyen , ahol:

A következő lemma garantálja, hogy az eljárás fenti sorozata monoton növekvő lesz.

5.15. Lemma.

ahol

Egyenlőség akkor és csak akkor áll fenn mindkét oldalon, ha konstans bármely -ra.

Bizonyítás. A Jensen-egyenlőtlenséget alkalmazva kapjuk, hogy

A második egyenlőtlenséghez elegendő belátni a következőt:

Legyen kimeneti valószínűségi vektor úgy, hogy

Az I-divergencia tulajdonságából könnyen beláthatjuk a következő egyenlőtlenséget:

Figyelembe véve ezt az egyenlőtlenséget kapjuk a következőt:

Másfelől

Ennélfogva

A lemmából azonnal következik, hogy ha és akkor az

függvény a esetben veszi fel a értéket, és pozitív ha . Könnyű belátni, hogy az egyenlőség feltétele, hogy konstans legyen bármely -ra.

Most már készen vagyunk, hogy bebizonyítsuk, az iterációs eljárás által létrehozott

sorozat a relatív kapacitáshoz tart.

Legyen

Mivel

kapjuk, hogy

Ennélfogva a

és a

sorozatok monoton növekvőek és ugyanahhoz az értékhez tartanak. Vezessünk be egy valószínűségi vektort mely elérte a relatív kapacitást és legyen

Ezenfelül vezessünk be egy

és kimeneti valószinűségi vektorokat. Ha figyelembe vesszük, hogy

akkor a következőhöz jutunk

Az egyenlőség jobboldalán lévő kifejezés nemnegatív, ezért

Összeadva ezeket az egyenlőtlenségeket -tól -ig, kapjuk, hogy

Az egyenlőtlenség jobb oldalán lévő kifejezés független -től, és véges, a

sorozat tart a relatív kapacitáshoz. Ezzel bizonyítottuk az iterációs eljárás konvergenciáját.

5.16. Következmény. A

kimeneti eloszlások sorozata, hasonlóan az

bemeneti eloszlások sorozatához, konvergens.

Bizonyítás. Az tételből kapjuk a

egyenlőtlenséget. Összeadva ezeket az egyenlőtlenségeket -tól -ig, úgy, mint a korábbi egyenlőtlenség levezetésében, könnyen beláthatjuk a következmény helyességét.

A következő lemma a kovergencia sebességének kimondásához szükséges.

5.17. Lemma. A közelítés

hibája egy

kifejezéssel határolható.

Bizonyítás. Az előzőek felhasználásával jutunk el a következő kifejezésig

A konvergencia sebessége:

Abban az esetben ha a bemeneti eloszlás eléri a relatív kapacitást, akkor ez egyedi és Ekkor a konvergencia sebessége meglehetősen javul.

A következőkben szükségünk lesz az alábbi lemmára, mely könnyen levezethető a Kuhn-Tucker tételből.

5.18. Lemma. Ha a valószínűségi vektor eléri a relatív kapacitást, akkor

5.19. Tétel. Ha a bemeneti valószínűségi vektor eléri a relatív kapacitást, akkor az egyedi és . Ekkor létezik olyan pozitív egész és egy konstans , amik kielégitik a következő egyenlőtlenséget

és független -tól.

Bizonyítás. Legyen ekkor tart a -hoz, ha .

Továbbá legyen

Ekkor a következőkhöz jutunk:

ahol egy méretű szimmetrikus mátrix, úgy, hogy

Eléggé nagy esetén

Az Arimoto-Blahut algoritmus bizonyításához hasonló érveléssel, kombinálva az egyenlőtlenségeket, bizonyítani tudjuk a tételt.