Algebra linearebernardi/Didattica/Analisi/Lucidi/lin-slides_1.pdfRichiami di algebra lineare...

Algebra lineare

Richiami di algebra lineareMotivazioni

• L’esempio piu comune di spazio vettoriale e RN, ma non e l’unico

• Esistono molti altri esempi di spazi vettoriali importanti per le applicazioni

• Questo ci permette di utilizzare in altri contesti gli strumenti dell’algebralineare

1

DIEGM UNIVERSITA DI UDINE

Richiami di algebra lineareUtilita per banchi di filtri

• L’uscita di un generico ramo di un banco di analisi

x?hk(Nn) = ∑m∈Z

x(m)hk(Nn−m) = 〈x,hk(Nn−·)〉

puo essere interpretata come un prodotto scalare tra il segnale di ingressoe la versione traslata e rovesciata del filtro

• Questo suggerisce di utilizzare gli strumenti dell’algebra lineare nell’analisidei banchi di filtri

2


Algebra lineareSpazi di Hilbert

Spazi lineari di segnaliDefinizioni: Spazi di Hilbert

Spazio di Hilbert

• Spazio vettoriale

• Dotato di prodotto scalare 〈·, ·〉

• Completo (ogni sequenza di Cauchy xn, ‖xn− xm‖ → 0, converge)

3


Spazi di HilbertDefinizione: sottospazio

• Sottospazio

– Chiuso rispetto a combinazioni lineari

– Completo

• Attenzione:

– La completezza di solito non e un problema, ma trascurarla puo esserecausa di errori “sottili”

4


Spazi lineari di segnaliCos’e un prodotto scalare?

• Prodotto scalare

〈αx+ y,z〉= α〈x,z〉+ 〈y,z〉, α ∈C (1)

〈x,y〉= 〈y,x〉∗ (2)

〈x,x〉 ≥ 0, 〈x,x〉= 0⇔ x = 0 (3)

• Esempio: prodotto scalare tra vettori di CN

〈y,x〉= xty =N

∑n=1

x∗nyn

5


Spazi lineari di segnaliDefinizioni: norma

• Norma e distanza indotte dal prodotto scalare

‖x‖2 = 〈x,x〉 d(x,y) = ‖x− y‖

• Norma ≈ idea di lunghezza

• Ritorno alle origini: dalla norma al prodotto scalare

Re〈x,y〉= ‖x+ y‖2−‖x− y‖24

Im〈x,y〉= ‖x+ jy‖2−‖x− jy‖24 j

6


Prodotto scalare e normaProprieta

• x e y si dicono ortogonali se 〈x,y〉= 0

• Teorema di Pitagora

〈x,y〉= 0⇒‖x+ y‖2 = ‖x‖2 +‖y‖2

• Disuguaglianza triangolare

‖x+ y‖ ≤ ‖x‖+‖y‖

7


Angolo tra vettori

• Disuguaglianza di Cauchy-Schwarz

|〈x,y〉| ≤ ‖x‖‖y‖

→ uguaglianza se e solo se x = αy ←

• Possiamo scrivere

cosθ =|〈x,y〉|‖x‖‖y‖

dove θ ∈ [0,π/2] e, per definizione, l’angolo tra x e y

• Nota: θ = 0⇔ paralleli, θ = π/2⇔ ortogonali.

8


Esempi di spazi di HilbertSpazi a dimensione finita RN, CN

• Prodotto scalare

〈y,x〉= xty =N

∑n=1

x∗nyn

• Norma

‖x‖2 = 〈y,x〉=N

∑n=1|xn|2

9


Spazi di HilbertSpazio di segnali ad energia finita L2(R)

• Prodotto scalare usato

〈 f ,g〉=∫

R

f (x)g∗(x)dx

• Norma associata

‖ f‖2 =∫

R

| f (x)|2dx

10


Spazi di HilbertSpazio delle sequenze ad energia finita `2(Z)


〈 f ,g〉=+∞∑

n=−∞f (n)g∗(n)

• Norma associata

‖ f‖2 =+∞∑

n=−∞| f (n)|2

11


Spazi di HilbertSegnali periodici ad energia finita L2((0,P])


〈 f ,g〉=∫ P

0f (x)g∗(x)dx

• Norma associata

‖ f‖2 =∫ P

0| f (x)|2dx < ∞

12


Spazi di Hilbertsegnali a potenza finita


〈 f ,g〉= limT→∞

1T

∫ T/2

−T/2f (x)g∗(x)dx

• Norma associata

‖ f‖2 = limT→∞

1T

∫ T/2

−T/2| f (x)|2dx < ∞

13


Spazi di HilbertVariabili aleatorie a media nulla e varianza finita

• Prodotto scalare usato: correlazione

〈x,y〉= E[xy∗]

• Norma associata: varianza

‖x‖2 = σ2x = E[x2]

14


Spazi di HilbertVariabili aleatorie a media nulla e varianza finita (2)

• Nota:

– due variabili incorrelate si dicono anche. . . ortogonali

– la diseguaglianza di Cauchy-Schwarz porge

|〈x,y〉|‖x‖‖y‖ =

|E[xy∗]|σxσy

= |ρxy| ≤ 1

ossia, la covarianza normalizzata e compresa tra −1 e 1

– ρxy puo essere interpretata come coseno dell’“angolo” tra x e y

15


Algebra lineareBasi

Basi

• Un insieme di vettori B ={

b1,b2, . . .}

e una base di V se

1. I vettori bi sono linearmente indipendenti (non ridondante)

2. Ogni vettore di V si scrive come combinazione lineare dei bi (completa)

16


Basi: attenzione!

• Sia V uno spazio di dimensione d

• Se d < ∞, d vettori linearmente indipendenti sono una base

• Se d = ∞, d vettori linearmente indipendenti possono non essere una base

• Esempio:

1√P

exp( j2π(n/P)t), n = . . . ,−2,0,2,4, . . .

non sono una base per L2((0,P])

17


Basi di RieszMotivazione

• Una base di uno spazio vettoriale V e solitamente definita come un insiemedi vettori φi di V ale che

1. Genera V

2. E linearmente indipendente

• Quando lavoriamo con spazi a dimensione infinita e utile usare un concettopiu “forte” di base. . .

18


Basi di Riesz: perche?

• Consideriamo lo spazio `2(Z) e la sua base

φi =1

1+ |i|δ (·− i), i ∈ Z

b0 b1 b2 b3

19


Basi di Riesz: perche?(2)

• E ovvio che possiamo ricostruire ogni x ∈ `2(Z) a partire dai prodotti scalari

〈x,φi〉=x(i)

1+ |i|tramite la

x = ∑i∈Z

(1+ |i|)〈x,φi〉δ (·− i) = ∑i∈Z

x(i)δ (·− i)

ma. . .

20


Basi di Riesz: perche? (3)

• Se commettiamo un piccolo errore εN sull’N-simo coefficiente 〈x,φN〉 Il se-gnale ricostruito e

x = ∑i∈Z,i6=N

(1+ |i|)〈x,φi〉δ (·− i) coeff. buoni

+ (1+ |N|)(〈x,φi〉+ εN)δ (·−N) coeff. errato

• La norma dell’errore di ricostruzione e quindi

‖x− x‖ = (1+ |N|)‖εN‖

21


Cosa abbiamo scoperto?

• L’insieme di funzioni φi e sı una base di `2(Z), ma. . .

• . . . non e una buona base poiche un piccolo errore puo venire amplificatoin maniera arbitrariamente elevata

• Se usiamo φi in un contesto di codifica (in cui i prodotti scalari 〈x,φi〉 vengonoquantizzati) questo e un comportamento che non vogliamo.

22


Perche?

Q: Da dove deriva questo comportamento?

A: Dal fatto che i vettori φi hanno norma sempre piu piccola al crescere di i

• Onde “compensare” l’attenuazione introdotta dalla norma decrescente sia-mo costretti ad amplificare i coefficienti, amplificando cosı anche il rumore

Scegliamo una base che non abbia questo problema. . .

23


Basi di Riesz: definizione

Definition 1. Un insieme di vettori φi e detto una base di Riesz di V se

1. E linearmente indipendente

2. Esistono A > 0 e B < ∞ tali che per ogni x ∈V

A‖x‖2 ≤ ∑i∈Z

|〈x,φi〉|2 ≤ B‖x‖2

24


Base di Riesz: significato della condizione

• Perche ∑i∈Z|〈x,φi〉|2 ≤ B‖x‖2?

– Piccole variazioni di x non danno luogo a variazioni arbitrariamente gran-di dei coefficienti

– La mappa x→ 〈x,φi〉 e continua

25


Base di Riesz: significato della condizione

• Perche A‖x‖2 ≤ ∑i∈Z|〈x,φi〉|2?

– Se x 6= 0, allora esiste almeno un prodotto scalare non nullo

– La sequenza dei prodotti scalari descrive completamente x ⇒ possoriottenere x da 〈x,φi〉, ma inoltre. . .

– . . . impedisce alla base di introdurre attenuazioni arbitrariamente grandi,risolvendo il problema visto prima

26


Robustezza delle basi di Riesz

• Supponiamo che x corrisponda ai prodotti scalari 〈x,φi〉 e che x corrispondaai prodotti scalari 〈x,φi〉+ εi

• Ne segue che

εi = 〈x,φi〉−〈x,φi〉= 〈x− x,φi〉

da cui

‖x− x‖2 ≤ 1A ∑

i∈Z

|εi|2

⇒ L’errore di ricostruzione e amplificato al piu di 1/A ⇐

27


Commento: basi di Riesz a dimensione finita

• Per uno spazio a dimensione finita

1. La diseguaglianza ∑i∈Z|〈x,φi〉|2 ≤ B‖x‖2 e automaticamente verificata

2. La diseguaglianza A‖x‖2 ≤ ∑i∈Z|〈x,φi〉|2 equivale a richiedere che sia

∑i∈Z

|〈x,φi〉|2 6= 0

per ogni x 6= 0, ossia che φi sia una base

• Se la dimensione di V e infinita sono possibili i “giochetti” visti prima

28


Basi biortogonali

• Se φi e una base di Riesz e possibile dimostrare che esiste (ed e unico)l’insieme {bi}i∈Z

tale che

〈φi, b j〉= δi, j

• L’insieme dei vettori bi e una base di Riesz a sua volta

• Le basi φi e bi si dicono biortogonali e sono l’una l’“inversa” dell’altra

• Grazie a bi posso ricostruire x

x = ∑i∈Z

bi〈x,φi〉

29


Biortogonalita ed inversa

• Consideriamo il sistema Bx = y

• Come ben noto, la sua soluzione puo essere ottenuta come x = B−1y

• Cerchiamo un legame con le relazioni di biortogonalita. . .

30


Biortogonalita ed inversa (2)

• Se chiamo φ ti la i-sima riga di B, il sistema puo essere scritto

y1y2...yN

=

φ t1

φ t2...

φ tN

x

da cui

yi = φ ti x = 〈x,φi〉

31


Biortogonalita ed inversa (3)

• Se chiamo bi la i-sima colonna di B−1 posso scrivere la soluzione come

x

=[

b1 b2 · · · bN

]

y1y2...yN

da cui

x =N

∑i=1

biyi =N

∑i=1

bi〈x,φi〉

• Quindi le colonne di B−1 sono biortogonali alle righe di B

32


Basi ortonormali

• Se la base φi e tale che

〈φi,φ j〉= δi, j

la base si dice ortonormale

• E chiaro che una base ortonormale e l’inversa di se stessa

33


Basi ortonormali: proprieta

• Espansione di x

x =∞∑

n=0〈x,bi〉bi

• Uguaglianza di Parseval e corollario (≈ teorema di Pitagora esteso)

〈x,y〉=∞∑

n=0〈x,bi〉〈y,bi〉

∗, ‖x‖2 =∞∑

n=0|〈x,bi〉|

2

34


Parseval per d = 2

b1

b2

<x, b >1

<x,

b > 2

1

x

35


Basi ortonormaliEsempio

• Una base ortonormale per L2((0,P]) e data da

Wn(t)4=

1√P

exp( j2π(n/P)t), n ∈ Z

• Ortogonalita degli esponenziali

〈Wn,Wm〉=∫ P

0exp( j2π(n/P)t)exp(− j2π(m/P)t)dt = δ (n−m)

36


Basi ortonormaliEsempio

• Espansione di x ∈ L2((0,P])

Xn4= 〈x,Wn〉

=1√P

∫ P

0x(t)exp(− j2π(n/P)t)dt

x(t) =+∞∑

n=−∞〈x,Wn〉Wn(t)

=+∞∑

n=−∞Xn exp( j2π(n/P)t)

• Abbiamo ritrovato la trasformata di Fourier!

37


Basi ortonormaliEsempio: segnali a banda limitata

• Sia V lo spazio dei segnali a banda limitata in [−π,π].

• Vogliamo dimostrare che le fuunzioni

τn sinc(t) = sinc(t−n), n ∈ Z

formano una base ortonormale di V .

38


Basi ortonormaliEsempio: segnali a banda limitata (2)

• Ovviamente ogni combinazione lineare di τn sinc e a banda limitata

• Dobbiamo verificare che le funzioni τn sinc generino V

– Se x ∈V il teorema del campionamento dice che

x(t) = ∑n∈Z

x(n)sinc(t−n) = ∑n∈Z

x(n)τn sinc(t)

– Quindi x e combinazione lineare di τn sinc

39


Basi ortonormaliEsempio: segnali a banda limitata (3)

• Verificheremo che

〈sinc,τn sinc〉= δ (n)

dimostrando la seguente proprieta generale (e molto utile)

Property 1. Il segnale f ∈ L2(R) e ortogonale rispetto alle proprie traslazioni inZ (ossia, 〈 f ,τn f 〉= δ (n)) se e solo se

∑k∈Z

|F(ω +2kπ)|2 = 1

dove F(ω) e la trasformata di Fourier di f .

40


Condizioni di ortogonalitaProva

1. Sia r : Z→C definita come r(n) = 〈 f ,τn f 〉

2. r(n) e la versione campionata della correlazione di f . r = δ se e solo seR(ω) = 1

3. R(ω) e la ripetizione periodica della trasformata di Fourier della correlazionedi f

4. Ricordando che la trasformata di Fourier della correlazione di f e |F(ω)|2 siottiene la tesi

41


Condizioni di ortogonalitaConseguenze

• Sia f ∈ L2(R) e sia

V = span{τn f , n ∈ Z}

Q: Se f non e ortogonale alle sue traslazioni, come trovo una base ortonormaledi V?

A: “Ortonormalizzo” f calcolando

G(ω) =F(ω)

√

∑k|F(ω +2kπ)|2= F(ω)H(ω)

42


Ortonormalizzazione di fProva

• g(t) e chiaramente ortogonale alle sue traslazioni

• Rimane da verificare che le traslazioni di g generano V

– H(ω) e periodica di periodo 2π ⇒ posso scrivere g = h? f dove

h(t) = ∑n∈Z

anδR(t−n)

da cui

g(t) = ∑n∈Z

an f (t−n) ∈V

– Con ragionamento analogo f ∈ span{τng}n∈Z

43


Algebra lineareOperatori

Operatore aggiuntoIntroduzione

• La trasposta di una matrice (mappa lineare a dimensione finita) e definita inmaniera “fisica” (scambio righe con colonne)

• Come definiamo la trasposta quando lavoriamo a dimensione infinita?

• Per esempio, se V e lo spazio dei segnali a banda limitata, qual’e la traspo-sta dell’operatore Ch definito da

Chx4= h? x

con h ∈V?

44


Operatore aggiunto• Si osservi che a dimensione finita

ytAx = 〈Ax,y〉||

(Aty)x = 〈x,Aty〉

• Questo suggerisce di definire l’operatore trasposto di A come l’operatore At

tale che, per ogni x,y,

〈Ax,y〉= 〈x,Aty〉 (*)

• Tale definizione e ben posta poiche c’e un solo At che soddisfa (*).

• Spesso At viene anche detto operatore aggiunto ed indicato con A∗

45


Operatore aggiunto: esempio

• Proviamo a calcolare l’aggiunto di Ch

• Da Parseval

〈h? x,y〉= 〈HX ,Y 〉=

∫

R

H( f )X( f )Y ∗( f )d f

=∫

R

X( f )(H∗( f )Y ( f ))∗d f

= 〈X ,H∗Y 〉= 〈x,h− ? y〉

• Quindi C ∗h = Ch−

46


Norma di un operatore• Un concetto spesso utile e quello di norma |||A|||2 di un operatore A

|||A|||24= sup‖x‖≤1

‖Ax‖ = sup‖x‖6=0

‖Ax‖‖x‖

• Se lavoriamo a dimensione finita, la sfera ‖x‖ = 1viene mappata da A in un ellissoide

• |||A|||2 = asse maggiore dell’ellissoide

||| A |||

47


Algebra lineareProiezioni

Proiezione ortogonale

Ci servira il seguente risultato (che non dimostriamo)Property 2. Un operatore P e una proiezione ortogonale se e solo se

P2 = P e idempotente (a)

P∗ = P e autoaggiunto (simmetrico) (b)

48


Proiezione ortogonale: esempio (banale)

•In R3 la proiezione ortogonale sul piano x,y lascia in-variate le prime due componenti e pone la terza azero x

y

z

A

P(A)

• La matrice che rappresenta la proiezione

1 0 00 1 00 0 0

e idempotente e simmetrica

49


Proiezione ortogonale: esempio (filtro passa basso)

• Filtrare con un passa-basso ideale e una proiezione ortogonale; infatti

– E idempotente

L’uscita del primo passa basso e gia a banda limitata e quindi ilsecondo non fa nulla

– E autoaggiunto

Segue dal risultato su C ∗h e dalla parita del sinc

• Gli unici filtri che corrispondono a proiezioni sono “passa-qualcosa” ideali

50


Proiezione ortogonale: utilita del prefiltraggio

• E noto che se si deve campionare un segnale la cui banda non e limitata econveniente eseguire un filtraggio passa basso prima del campionatore

Tale accorgimento minimizza l’errore di ricostruzione

• Possiamo anche dire che il filtro passa basso proietta il segnale a bandanon limitata sullo spazio dei segnali perfettamente ricostruibili

• In questo modo campioniamo il segnale “ricostruibile dopo campionamento”piu vicino al segnale di partenza

51


Proiezione ortogonale: esempio (progetto di filtri)

• Progetto di filtri tramite finestre

– Voglio un filtro Hd( f ), ma la sua risposta impulsiva hd(n) ha durata infinita

– Problema: trovare il filtro h con supporto tra −N e N la cui risposta infrequenza H( f ) sia a minima distanza quadratica da Hd( f )

52


Proiezione ortogonale: esempio (progetto di filtri 2)

• Soluzione

La H( f ) desiderata e la proiezione di Hd( f ) sullo spazio delle trasfor-mate di Fourier dei segnali con supporto tra −N e N

ma grazie a Parseval

La h(n) desiderata e la proiezione di hd(n) sullo spazio dei segnalicon supporto tra −N e N

53



Q: Qual’e la proiezione sullo spazio dei segnali con supporto tra −N e N?

A: Il troncamento: e idempotente e autoaggiunto

• Ne segue che

h(n) =

{

hd(n) se |n| ≤ N

0 altrimenti

54



Q: . . . e se volessi il filtro pari a supporto tra −N e N a minima distanza quadra-tica da hd(n)?

A: Facile:

h(n) =

{

hd(n)+hd(−n)2 se |n| ≤ N

0 altrimenti

• Tale operatore e idempotente ed autoaggiunto: e una proiezione (verificarlo)

55


Basi ortonormali e proiezioni

• Se φn e una base ortonormale di V e noto che possiamo scrivere la proie-zione di x su V come

PV x = ∑n∈Z

φn〈x,φn〉

• Verifichiamo che PV sia idempotente ed autoaggiunto. . .

56


Basi ortonormali e proiezioniIdempotenza

PV PV x = ∑n∈Z

φn〈PV x,φn〉 definizione di PV

= ∑n∈Z

φn〈∑k∈Z

φk〈x,φk〉,φn〉 definizione di PV

= ∑n∈Z

φn ∑k∈Z

〈x,φk〉〈φk,φn〉 linearita

= ∑n∈Z

φn ∑k∈Z

〈x,φk〉δ (k−n) ortogonalita

= ∑n∈Z

φn〈x,φn〉= PV x

57


Basi ortonormali e proiezioniSimmetria

〈PV x,y〉= 〈∑n∈Z

φn〈x,φn〉,y〉 definizione di PV

= ∑n∈Z

〈x,φn〉〈φn,y〉 linearita

= 〈x,φn ∑n∈Z

〈φn,y〉∗〉 linearita

= 〈x,φn ∑n∈Z

〈y,φn〉〉= 〈x,PV y〉

58


Esempio semi-applicativo

• Problema: vogliamo trasmettere una 3 valori a0, a1, a2 lungo un filo.

• Soluzione: scegliamo 3 segnali g0(t), g1(t) e g2(t), li combiniamo secondola

x(t) =2

∑n=0

angn(t)

e mandiamo il risultato lungo il filo.

59


Esempio (2)

• Schema a blocchi del “trasmettitore”a 0

a 1

a 2

g 2g 1g 0

x(t) y(t)

(t)η

• Nota: x(t) non e qualunque, ma appartiene allo spazio G generato dai gn.

60


Esempio (2)• Problema: Come possiamo riottenere i valori an?

• Caso piu semplice:

1. Assenza di rumore (riceviamo esattamente x(t))

2. gn(t) ortonormali, 〈gi,g j〉= δ (i− j).

• Soluzione: calcoliamo i prodotti scalari tra x(t) ed i segnali gn

〈x,gk〉= 〈2

∑n=0

angn,gk〉

=2

∑n=0

an〈gn,gk〉= ak

61


Esempio (3)

• Domanda: cosa accade se c’e rumore?

• Risposta: il segnale ricevuto y(t) non appartiene a G

• Se il rumore non e “troppo forte,” possiamo supporre che x(t) sia abbastanzavicino a G

• Scegliamo come stima x(t) del segnale trasmesso il segnale appartenentea G piu vicino a y(t)

62


Esempio (4)

• Domanda: Come calcolo x(t)?

• Risposta: Calcolo la proiezione ortogonale di y(t) su G

• Domanda: come?

• Risposta: sfruttando il fatto che i gn sono una base ortonormale di G.

x(t) =2

∑n=0

gn(t)〈y,gn〉

• I valori an corrispondenti ad x sono an = 〈y,gn〉

63


Algebra linearebernardi/Didattica/Analisi/Lucidi/lin-slides_1.pdfRichiami di algebra lineare...

Documents

Transcript of Algebra linearebernardi/Didattica/Analisi/Lucidi/lin-slides_1.pdfRichiami di algebra lineare...