Blahut–Arimoto algoritm

Termen Blahut–Arimoto-algoritm används ofta för att hänvisa till en klass av algoritmer för att numeriskt beräkna antingen den informationsteoretiska kapaciteten hos en kanal, hastighetsförvrängningsfunktionen hos en källa eller en källkodning (dvs. komprimering för att ta bort redundansen). De är iterativa algoritmer som så småningom konvergerar till ett av maxima för optimeringsproblemet som är förknippat med dessa informationsteoretiska koncept.

Historik och tillämpning

När det gäller kanalkapacitet uppfanns algoritmen oberoende av Suguru Arimoto och Richard Blahut . Dessutom ger Blahuts behandling algoritmer för att beräkna hastighetsförvrängning och generaliserad kapacitet med ingångskontraint (dvs. kapacitetskostnadsfunktionen, analogt med hastighetsförvrängning). Dessa algoritmer är mest tillämpliga på fallet med godtyckliga finita alfabetkällor. Mycket arbete har gjorts för att utvidga det till mer generella probleminstanser. Nyligen föreslogs en version av algoritmen som står för kontinuerliga och multivariata utgångar med tillämpningar inom cellulär signalering. Det finns också en version av Blahut-Arimoto-algoritmen för riktad information .

Algoritm för kanalkapacitet

En diskret minneslös kanal (DMC) kan specificeras med två slumpvariabler $X,Y$ med alfabetet ${\mathcal {X}},{\mathcal {Y}}$ och en kanallag som en betingad sannolikhetsfördelning $p(y|x)$ . Kanalkapaciteten , definierad som ${\displaystyle C:=\sup _{p\in X}I(X;Y)} ,$ indikerar den maximala effektiviteten som en kanal kan kommunicera, i enheten bit per användning. Om vi ​​nu betecknar kardinalitet ${\displaystyle |{\mathcal {X}}|=n,|{\mathcal {Y}}|=m} ,$ sedan $p_{Y|X}$ är en $n\times m$ matris, som vi betecknar ${\displaystyle i^{th}}-$ raden, $j^{th}$ kolumnpost av $w_{ij}$ . När det gäller kanalkapacitet uppfanns algoritmen oberoende av Suguru Arimoto och Richard Blahut . fann självständigt följande uttryck för kapaciteten hos en DMC med kanallag:

$C=\max _{\mathbf {p} }\max _{Q }\summa _{i=1}^{n}\summa _{j=1}^{m}p_{i}w_{ij}\log \left({\dfrac {Q_{ji}}{p_{ i}}}\right)$

där $\mathbf {p}$ och $Q$ är maximerade över följande krav:

• $\mathbf {p}$ är en sannolikhetsfördelning på ${\displaystyle X} ,$ det vill säga om vi skriver $\mathbf {p}$ som $(p_{1},p_{2}...,p_{n}),\summa _{i=1}^{n}p_{i }=1$
• $Q=(q_{ji})$ är en $m\times n$ matris som beter sig som en övergångsmatris från $Y$ till ${\ displaystyle X}$ med avseende på kanallagen. Det vill säga, för alla $1\leq i\leq n,1\leq j\leq m$ :
  • $q_{ji}\geq 0,q_{ji}=0\Leftrightarrow w_{ij}=0$
  • Varje rad summerar till 1, dvs $\sum _{i=1}^{n}q_{ji}=1$ .

När du sedan väljer en slumpmässig sannolikhetsfördelning $\mathbf {p} ^{0}:=(p_{1}^{0},p_{2 }^{0},...p_{n}^{0})$ på $X$ , kan vi generera en sekvens $( \mathbf {p} ^{0},Q^{0},\mathbf {p} _{1},Q^{1}...)$ iterativt enligt följande:

$(q_{ji}^{t}):={\dfrac {p_{i}^{ t}w_{ij}}{\sum _{k=1}^{n}p_{k}^{t}w_{kj}}}$

$p_{k}^{t +1}:={\dfrac {\prod _{j=1}^{m}(q_{jk}^{t})^{w_{kj}}}{\sum _{i=1}^{ n}\prod _{j=1}^{m}(q_{ji}^{t})^{w_{ij}}}}$

För $t=0,1,2...$ .

Sedan, med hjälp av teorin om optimering, specifikt koordinatnedstigning , visade Yeung att sekvensen verkligen konvergerar till det maximala som krävs. Det är,

$\lim _{t\to \infty }\sum _{ i=1}^{n}\summa _{j=1}^{m}p_{i}^{t}w_{ij}\log \left({\dfrac {Q_{ji}^{t}} {p_{i}^{t}}}\right)=C$ .

Så givet en kanallag $p(y|x)$ , kan kapaciteten uppskattas numeriskt upp till godtycklig precision.

Algoritm för Rate-Distortion

Anta att vi har en källa $X$ med sannolikheten $p(x)$ för en given symbol. Vi vill hitta en kodning $p({\hat {x}}|x)$ som genererar en komprimerad signal ${\hat {X}}$ från originalet signal samtidigt som den förväntade distorsionen minimeras ${\displaystyle \langle d(x,{\hat {x}})\rangle } ,$ där förväntan tas över den gemensamma sannolikheten för $X$ och ${\hat {X}}$ . Vi kan hitta en kodning som minimerar hastighetsförvrängningen lokalt genom att upprepa följande iteration tills konvergens:

$p_{t+1}({\hat {x}})=\summa _{x}p( x)p_{t}({\hat {x}}|x)$

$p_{t+1}({\hat {x}}|x)={\frac {p_{t}( {\hat {x}})\exp(-\beta d(x,{\hat {x}}))}{\sum _{\hat {x}}p_{t}({\hat {x} })\exp(-\beta d(x,{\hat {x}}))}}$

där $\beta$ är en parameter relaterad till lutningen i hastighetsdistorsionskurvan som vi riktar in oss på och därmed är relaterad till hur mycket vi föredrar komprimering kontra distorsion (högre $\beta$ betyder mindre komprimering) .