Sezione 9.5: Codifica di sorgente con perdita di informazione Su Capitolo 9: Teoria dell’informazione e codifica di sorgente Capitolo 10: Codifica di sorgente multimediale 

9.6 Appendici

9.6.1 Metodo dei moltiplicatori di Lagrange

Costituisce un modo di affrontare un problema di ottimizzazione vincolata[501]  [501] Vedi ad es. https://en.wikipedia.org/wiki/Lagrange_multiplier, ossia individuare i punti x* di massimo o minimo (detti estremali) per una funzione obiettivo f(x) definita in un aperto A ⊂ ℝn (ossia dipendente da più variabili x = (x1, x2, ⋯xn)), nel rispetto di una o più condizioni di vincolo del tipo qi(x) = bi ossia gi(x) = 0 con i = 1, 2, ⋯, m dopo aver posto gi(x) = qi(x) − bi.
Le condizioni di vincolo individuano una regione ammissibile X  per le soluzioni x* ∈ X come X = {x ∈ A: gi(x) = 0  con i = 1, 2, ⋯, m}.
Osservazione L’insieme X ha gradi di libertà ridotti rispetto all’aperto A: ad esempio se n = 2, ovvero z = f(x, y) è una superficie, allora un vincolo g(x, y) = 0 è una curva nel piano (x, y), proiezione della intersezione tra la superficie z = q(x, y) ed il piano orizzontale z = b. A sua volta la curva espressa dal vincolo g(x, y) = 0 viene proiettata in verticale sulla superficie z = f(x, y), individuando su di essa un cammino lungo il quale si trovano i punti x* di ottimo vincolato. Qualora si aggiunga un ulteriore vincolo g2(x, y) = 0 l’insieme X si riduce ulteriormente ai punti di intersezione tra i cammini disegnati sulla superficie z = f(x, y) dai due vincoli.
A patto che le funzioni siano derivabili con derivate continue e che m < n, trovare i punti x* estremali di f(x) nel rispetto dei vincoli g(x) = 0 passa per la definizione della funzione Lagrangiana come
(10.258)
L(x, λ)  = f(x) − λ, g(x) = f(x) − mi = 1 λi gi(x)
in cui g(x) è il vettore delle m funzioni gi(x), λ un vettore di m moltiplicatori scalari, e λ, g(x) esprime il prodotto scalare (§ 2.4.3) tra i due. Osserviamo che L è una funzione di n + m variabili, le dimensioni di x e λ.
Gradiente prima di poter proseguire occorre definire l’operatore gradiente di f(x) come il vettore i cui elementi ne sono le derivate parziali, ossia f(x) = fx1, f x2, ⋯, f xn. Il suo orientamento nello spazio indica la direzione verso cui f(x) cresce più velocemente, e se x = x0 è un punto stazionario (minimo, massimo o di sella) di f(x), allora f(x0) =  0, ovvero piccole variazioni dell’argomento xx0 non alterano di molto il valore di f.
Possiamo finalmente enunciare il teorema, che afferma
Qualora esista un punto x* di ottimo vincolato, e la matrice Jacobiana J{g(x*)} abbia rango m[502]  [502] La matrice Jacobiana J{g(x)} (associata ai vincoli gi(x)) è stata introdotta al 6.4.2, ed essendo la sua i − esima riga riga ottenuta come la sequenza delle derivate parziali gi xj, si ottiene impilando i vettori gradiente xgi(x) calcolati per ciascun vincolo., allora esiste un vettore λ* ∈ ℝm tale che
(10.259) L (x*, λ*) = 0
ovvero i valori (x*, λ*) individuano punti stazionari di
(10.258)
Ciò comporta che
  1. l’azzeramento di L(x, λ) per un qualche valore (x*, λ*) è condizione necessaria all’esistenza del punto x* di ottimo, ovvero i valori che verificano la (10.259) possono non essere soluzione al problema di ottimo, ma devono essere verificati singolarmente;
  2. L (10.259) è un vettore i cui elementi sono n + m funzioni di x e λ, il cui azzeramento realizza un sistema di altrettante equazioni, le cui soluzioni sono i valori (x*, λ*) desiderati;
  3. i primi n elementi di L sono le Lxj con j = 1, 2, ⋯, n, il cui azzeramento implica f xj = mi = 1 λ * i gi xj ovvero xf(x*) = mi = 1 λ * ix gi(x*) od anche xf(x*) = λ*, ∇xg(x*), e cioè quando (x, λ) = (x*, λ*) il gradiente della funzione obiettivo xf diviene eguale ad una combinazione lineare mi = 1 λ * ix gi degli m gradienti delle condizioni di vincolo, con i moltiplicatori λ * j come coefficienti. Ciò comporta che xf(x*) è ortogonale a ciascun cammino individuato dai vincoli[503]  [503] Vedi ad es. https://www.geogebra.org/m/gXyun8mD, o ovvero che la curva di livello di f(x) che passa per x = x* è tangente (in tale punto) alla curva descritta dal vincolo;
  4. gli ultimi m elementi di L corrispondono a Lλj = − gj(x) e dunque il loro annullamento comporta il rispetto dei vincoli;
  5. se i vincoli sono soddisfatti il termine mi = 1 λ * igi(x) della (10.258) è nullo, e dunque i punti estremali di L al variare di x lo sono anche per la f(x) di partenza;
  6. la condizione J{g(x*)} di rango m garantisce che i gradienti dei vincoli siano linearmente indipendenti, consentendo di trarre le conclusioni di cui al punto 3. Qualora la condizione non si verifichi la soluzione offerta dal teorema non è praticabile, dato che in tal caso L può non azzerarsi nei punti di ottimo, per qualunque λ.
Esempio Si trovino i punti di massimo e di minimo della funzione f(x, y) = x + y sottoposta al vincolo g(x, y) = x2 + y2 − 1 = 0. Con l’aiuto della figura,
figure Lagrange_very_simple.png
osserviamo che i punti devono giacere sulla intersezione tra un piano inclinato z = x + y e la proiezione su di esso di una circonferenza di raggio unitario, risultato dell’intersezione tra un paraboloide z = x2 + y2 ed il piano z = 1. Per la Lagrangiana otteniamo L(x, y, λ) = x + y − λ(x2 + y2 − 1), e l’annullamento del relativo gradiente da luogo al sistema 2λx − 1 = 0 2λy − 1 = 0 x2 + y2 − 1 = 0 , da cui si può ottenere che (x*, y*, λ*) = ±12, 12, 12. Dato che f12, 12 = 2 e che f − 12,  − 12 = − 2, il primo punto individua un massimo, ed il secondo un minimo, entrambi di tipo vincolato. Osserviamo come f sia ovunque pari a (1, 1), e nei punti di ottimo risulti ortogonale alla tangente al cammino individuato dal vincolo.

9.6.2 Massimo dell’entropia per variabile aleatoria gaussiana

Si intende ora mostrare la validità della (10.236), ovvero che l’entropia differenziale per sorgente continua gaussiana hG = 12 log2(2πeσ2) (eq. (10.235)) è il massimo che si può ottenere per qualunque scelta della d.d.p. di primo ordine p(x) della sorgente, una volta fissata la sua varianza σ2, ossia
hG = 12 log2(2πeσ2) = maxp(x){−  p(x)log2p(x)dx}    dato σ2
Per arrivare allo scopo si può adottare[504]  [504] Un metodo alternativo è mostrato in https://en.wikipedia.org/wiki/Differential_entropy, mentre https://kconrad.math.uconn.edu/blurbs/analysis/entropypost.pdf approfondisce la questione. il metodo dei moltiplicatori di Lagrange (§ 9.6.1), considerando p(x) = p come una variabile p (anziché una funzione) rispetto a cui massimizzare, nel rispetto dei vincoli g1(p) = p(x)dx − 1 = 0 e g2(p) =  x2p(x)dx − σ2 = 0, mentre il vincolo sul valor medio è ininfluente a causa dell’invarianza evidenziata a pag. 1.
Scriviamo dunque il lagrangiano come
L(p, λ1, λ2)  = − p(x)log2p(x)dx − λ1(p(x)dx − 1) − λ2(x2p(x)dx − σ2x) =   = − [p(x)log2p(x) + λ1p(x) + λ2x2p(x)]dx + λ1 + λ2σ2x =   = − 1ln 2 [p(x) ln p(x) + λ1p(x) + λ2x2p(x)]dx + λ1 + λ2σ2x
in cui si è sostituito log2p(x) = 1ln 2 ln p(x) e si adotta una eguale scalatura per i moltiplicatori λi. Il massimo di L(p, λ1, λ2) si ottiene eguagliandone a zero le derivate parziali, ed applicando la proprietà di derivata sotto il segno di integrale[505]  [505] Considerando la derivata come limite di un rapporto incrementale, si tratta di una conseguenza di https://it.wikipedia.org/wiki/Passaggio_al_limite_sotto_segno_di_integrale scriviamo
Lp = − 1ln 2 [ln p(x) − p(x)1p(x) + λ1 + λ2x2]dx = 0
in cui si è applicata la regola della derivata del prodotto p ln p. L’uguaglianza con zero si verifica se ln p(x) − 1 + λ1 + λ2x2 = 0 ovvero ln p(x) = 1 − λ1 − λ2x2, da cui
p(x) = e1 − λ1 − λ2x2 =  e1 − λ1 e− λ2x2 =  eαe− βx2
dove α = 1 − λ1 e β = λ2 deve essere positivo per poter avere p(x) dx finito.
Osserviamo ora che il vincolo p(x) dx = 1 determina che[506]  [506] Infatti sappiamo che 12πσxe− x2 2σ2xdx = 1 ovvero, ponendo 12σ2x = β e dunque σ2x = 12β otteniamo e− βx2dx = 2πσ2x = 2π2β = πβ. eα e− βx2 dx = eαπβ = 1 e dunque la condizione g1(p) = 0 è soddisfatta qualora
eα = βπ
Infine, il vincolo x2p(x) dx = σ2 impone che
x2 eαe− βx2 dx = βπ x2 e− βx2dx = σ2
che risulta soddisfatta qualora β = 12σ2, ottenendo infatti in tal modo per p(x) l’espressione di una gaussiana ovvero
p(x) = eαe− βx2 =  βπe− βx2|β = 12σ2 = 12πσ2 e− x22σ2
Notiamo esplicitamente la differenza rispetto al caso continuo, in cui la d.d.p. che rende massima l’entropia è invece quella uniforme. Presso Wikipedia è possibile trovare un elenco[507]  [507] Vedi https://en.wikipedia.org/wiki/Differential_entropy di valori di entropia differenziale calcolata per diverse scelte di d.d.p.

9.6.3 Misura di piattezza spettrale di processo gaussiano

Per dimostrare[508]  [508] La trattazione segue quella fornita in N.S. Jayant, P. Noll, Digital Coding of Waveforms, 1984 Prentice Hall. la seconda eguaglianza della (10.252) occorre prima mettere in evidenza alcune proprietà degli autovalori λi, i = 1, 2⋯, n della matrice di correlazione Rxx simmetrica, definita positiva, di dimensioni n × n, e con valori Rxx(i, j) = E{xixj} valutati per i campioni xi di un processo a media nulla, e dunque pari a σ2x sulla diagonale.
Come noto da altri corsi, ad ogni autovalore è associato il relativo autovettore vi dalla relazione Rxxvi = λivi, e l’insieme degli autovalori può essere trovato risolvendo l’equazione caratteristica det(Rxx − λI) = 0 dove I è la matrice identità, diagonale n × n. Tale equazione è un polinomio di grado n in λ e le peculiarità di Rxx assicurano di poter trovare n zeri reali, a partire dai quali possono essere trovati gli autovettori corrispondenti a meno di un fattore di scala, che conviene fissare in modo che gli autovettori siano ortonormali, ossia per essi valga la relazione vivj = δij. Sussistono ora le relazioni
  1. Rxx = ni = 1λivivi
  2. det(Rxx) = ni = 1λi
  3. tr(Rxx) = ni = 1λi ma dato che è anche vero che tr(Rxx) = nσ2x, per qualunque n il valor medio degli autovalori eguaglia la varianza, ovvero
  4. σ2x = 1n ni = 1 λi. Essendo quindi gli autovalori una misura di varianza, sono non-negativi. Inoltre, se λi è autovalore di Rxx, allora 1λi è autovalore di R− 1xx.
A questo punto il colpo di scena deriva dall’applicazione del teorema di distribuzione di Toeplitz (teorema di Szego[509]  [509] In base a quanto riportato presso https://en.wikipedia.org/wiki/Szego_limit_theorems il teorema si applica quando gli autovalori sono quelli di una matrice di Toeplitz, i cui elementi sono coefficienti di Fourier di una funzione definita sul cerchio unitario, esattamente come nel nostro caso.) che afferma che per qualunque funzione f(.)
(10.260) limn → ∞1n ni = 1f(λi) = 12π π − πf [Sxx(e jω)] dω
in cui Sxx(e jω) = k = −∞Rxx(k)e− jkω è la dtft (§ 4.4) della funzione di autocorrelazione Rxx(k) = E{xnxn + k} cui valori compaiono nella matrice Rxx,, calcolata per la sequenza {xn}, di cui Sxx(e jω) è lo spettro di densità di potenza. In base all’osservazione 4., qualora f(.) sia pari ad una identità la (10.260) diviene un aspetto del teorema di Parseval, e calcola la potenza di {xn}. Ma ora si compie una magia, poiché ponendo invece f(.) = ln (.) l’eq. (10.260) diventa
(10.261) limn → ∞ ln [ni = 1λi]1n = 12ππ − πln [Sxx(e jω)] dω
da cui in base all’osservazione 2  ne consegue[510]  [510] Infatti indicando il secondo membro di (10.261) con α otteniamo
limn → ∞ln ni = 1λi1n = limn → ∞ln ( det(Rxx)1n) = α e dunque eα = limn → ∞ det(Rxx)1n
limn → ∞(det(Rxx))1n = exp12ππ − πln [Sxx(e jω)] dω = η2x
dove η2x individua la varianza del minimo errore di predizione, ossia la varianza del processo bianco in ingresso ad un filtro autoregressivo (vedi § 10.1.2.2) alla cui uscita si ottiene un segnale con autocorrelazione Rxx(k). Dividendo η2x per σ2x = E{x2} = 1 2π   ππ Sxx(e jω) dω otteniamo la misura di piattezza spettrale
(10.262) γ2x = η2x σ2x = exp12ππ − πln [Sxx(e jω)] dω 12ππ − πSxx(e jω) dω
che compare nella (10.252).

9.6.4 Autocorrelazione di sequenza autoregressiva

Sviluppiamo qui i passaggi necessari ad ottenere le grandezze indicate nell’esempio di pag. 1, osservando innanzitutto che il processo x(n) = z(n) + αx(n − 1) viene anche detto Markoviano di primo ordine, dato che la dipendenza statistica dal passato si estende al solo campione precedente. Come osservato, x(n) è l’uscita di un filtro iir del primo ordine al cui ingresso sono posti campioni di un processo gaussiano bianco a media nulla con varianza σ2z.
Per il valore di autocorrelazione, come noto (§ 7.4) risulta
Rxx(k) = Rhh(k) * Rzz(k) = σ2z Rhh(k)
in quanto Rzz(k) = σ2zδ(k). Con riferimento alla figura che segue, per k ≥ 0 si ha
Rhh(k)  = n = 0 h(n)h(n + k) = n = 0 αnαn + k =   = αkn = 0 α2n = αk1 − α2
mentre per k < 0
Rhh(k)  = n = |k| h(n)h(n + k) = n = |k| αnαn + k =   = α − kn = |k| α2(n + k) = α − kn = 0 α2n = α − k1 − α2
figure f17.veldist3.png
ma dato che se k < 0 allora  − k = |k|, possiamo scrivere
Rhh(k) = α|k| 1 − α2
per k. Risulta quindi
Rxx(k) = σ2z Rhh(k) = σ2z α|k| 1 − α2
a cui corrisponde una varianza
σ2x = Rxx(0) = σ2z 11 − α2
ottenendo in definitiva
Rxx(k) = σ2zα|k|
Applicando poi la definizione (10.262) di piattezza spettrale otteniamo
γ2x = σ2zσ2x = σ2z 1 − α2 σ2z = 1 − α2
mentre la risposta in frequenza Hxx(e jω) è stata già ricavata a pag. 1, eq. (10.82).
 Sezione 9.5: Codifica di sorgente con perdita di informazione Su Capitolo 9: Teoria dell’informazione e codifica di sorgente Capitolo 10: Codifica di sorgente multimediale