Algebra z geometrią
Macierze unitarne, dekompozycja Schura, SVD, macierz pseudoodwrotna
Adam Dąbrowski
Politechnika Poznańska
Wydział Informatyki
Katedra Sterowania i Inżynierii Systemów
Pracownia Układów Elektronicznych i Przetwarzania Sygnałów
25 stycznia 2013
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
1 / 51
Zakres zagadnień
1
Iloczyn skalarny wektorów o elementach zespolonych
2
Macierze unitarne
3
Fale w obwodzie elektrycznym
4
Moc padająca, odbita i transmitowana
5
Bezstratny obwód elektryczny
6
Unitarna transformacja sygnału
7
Dyskretna transformacja Fouriera (DFT)
8
Dekompozycja Schura
9
Rozkład na wartości szczególne — SVD
10
Przeszukiwanie stron internetowych — algorytm HITS
11
Macierz pseudoodwrotna Moore-Penrose
12
SVD sygnałów akustycznych na wykładzie
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
2 / 51
Iloczyn skalarny wektorów o elementach zespolonych
Obserwacja
Definicja iloczynu skalarnego wektorów o elementach rzeczywistych
x
T
y
=
k
x
k
y
k
jest niedorzeczna w przypadku wektorów o elementach zespolonych. Na
przykład długości wektora
x
=
1
j
nie można wyliczyć ze wzoru
(niezerowy wektor miałby długość równą 0)
||x||
2
= x
T
x
= 1 · 1 + j · j = 1 − 1 = 0
a ze wzoru
x
∗T
x
= x
∗
x
= 1 · 1 + (−j) · j = 1 + 1 = 2 .
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
3 / 51
Pojęcie macierzy unitarnej
Macierz unitarna jest uogólnieniem pojęcia macierzy ortogonalnej na
przypadek zespolonych elementów macierzy.
Definicja macierzy ortogonalnej — powtórka
Nieosobliwa macierz kwadratowa A, której macierz odwrotna jest jej
macierzą transponowaną, tzn.
A
−1
= A
T
jest nazywana
macierzą ortogonalną
.
Definicja macierzy unitarnej
Nieosobliwa macierz kwadratowa A, której macierz odwrotna jest jej
macierzą transsprzężoną, tzn.
A
−1
= A
∗T
= A
∗
jest nazywana
macierzą unitarną
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
4 / 51
Macierze ortogonalne i unitarne
Przykład
Macierz S jest unitarna a macierz Q jest ortogonalna i unitarna
S
=
⎡
⎢
⎣
1
√
2
1
√
2
0
−
j
√
2
j
√
2
0
0
0
j
⎤
⎥
⎦
, Q =
⎡
⎢
⎣
1
√
2
1
√
2
0
−
1
√
2
1
√
2
0
0
0 1
⎤
⎥
⎦
.
Właściwości macierzy ortogonalnych i unitarnych
Macierz ortogonalna to rzeczywista macierz unitarna.
Kolumny (wiersze) macierzy unitarnej (ortogonalnej) są
jednostkowymi wektorami ortogonalnymi (tzw. wektorami
ortonormalnymi).
Moduł wyznacznika macierzy ortogonalnej (unitarnej) jest równy
jeden.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
5 / 51
Fale w obwodzie elektrycznym
e
e
-
?
-
I
U
A
B
R
Na rysunku przedstawiono bramę (parę zacisków) układu elektrycznego,
dla której oprócz napięcia U oraz prądu I zdefiniowano również tzw. fale
napięciowe: padającą A i odbitą B zgodnie ze wzorami
A = 0.5(U + RI )
B = 0.5(U − RI ) ,
przy czym R jest pewną stałą odniesienia tzw. „rezystancją falową”. Dla
prostoty zakładamy, że R
= 1.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
6 / 51
Fale w obwodzie elektrycznym
e
e
-
?
-
I
U
A
B
Obliczając na podstawie wzorów
A = 0.5(U + I )
B = 0.5(U − I ) ,
napięcie U oraz prąd I , otrzymuje się
U = A + B
I = A − B .
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
7 / 51
Moc transmitowana do obwodu
e
e
-
?
-
I
U
A
B
Zakładając, że rozważany obwód elektryczny jest na prawo od narysowanej
bramy, czyli, że na jego wejście pada fala A, moc średnią transmitowaną
do obwodu można wyrazić wzorem
Re
(UI
∗
) = Re
(A + B)(A
∗
− B
∗
)
=
= Re (AA
∗
+ BA
∗
− AB
∗
− BB
∗
) = Re (AA
∗
− BB
∗
) + Re (BA
∗
− AB
∗
) =
= AA
∗
− BB
∗
+ 0 = ||A||
2
− ||B||
2
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
8 / 51
Moc transmitowana do obwodu
e
e
-
?
-
I
U
A
B
Zakładając, że rozważany obwód elektryczny jest na prawo od narysowanej
bramy, czyli, że na jego wejście pada fala A, moc średnią transmitowaną
do obwodu można wyrazić wzorem
Re
(UI
∗
)
=
AA
∗
−
BB
∗
=
||A||
2
−
||B||
2
.
Wniosek
Moc transmitowana do obwodu Re
(UI
∗
)
jest różnicą dwóch mocy:
mocy
padającej
równej kwadratowi modułu
||A||
2
fali padającej A i
mocy odbitej
równej kwadratowi modułu
||B||
2
fali odbitej B.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
9 / 51
Moc transmitowana do obwodu
Zakładając, że rozważany obwód elektryczny jest na prawo od narysowanej
bramy, czyli, że na jego wejście pada fala A, moc średnią transmitowaną
do obwodu można wyrazić wzorem
Re
(UI
∗
)
=
AA
∗
−
BB
∗
=
||A||
2
−
||B||
2
.
Wniosek
Moc transmitowana do obwodu Re
(UI
∗
)
jest różnicą dwóch mocy:
mocy
padającej
równej kwadratowi modułu
||A||
2
fali padającej A i
mocy odbitej
równej kwadratowi modułu
||B||
2
fali odbitej B.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
10 / 51
Bezstratny obwód elektryczny
-
?
6
6
?
A
1
B
1
A
2
B
2
A
n
B
n
Definicja
Obwód elektryczny jest nazywany bezstratnym, jeżeli suma mocy fal
padających jest równa sumie mocy fal odbitych
a
.
a
Ściślej należy mówić o średnich mocach fal padających i odbitych.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
11 / 51
Bezstratny obwód elektryczny
-
?
6
6
?
A
1
B
1
A
2
B
2
A
n
B
n
Definiując wektor a złożony z fal padających A
1
, A
2
, . . . , A
n
i wektor b
złożony z fal odbitych B
1
, B
2
, . . . , B
n
, dla obwodu bezstratnego można
napisać, że
1
||a||
2
= a
∗
a
= b
∗
b
= ||b||
2
1
Ściślej normy euklidesowe powinny być oznaczone jako || · ||
2
zamiast || · ||.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
12 / 51
Bezstratny obwód elektryczny
-
?
6
6
?
S
A
1
B
1
A
2
B
2
A
n
B
n
Wprowadzając tzw.
macierz rozproszenia S
(ang. scattering matrix)
b
= Sa ,
warunek
||b||
2
= ||a||
2
oznacza, że prawdziwy jest następujący wniosek:
Wniosek
Macierz rozproszenia bezstratnego obwodu elektryczny jest
unitarna.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
13 / 51
Transformacja sygnału
Definicja transformacji
Rozważmy jednowymiarowy sygnał x
(n) złożony z bloku N próbek,
n = 0, 1, 2, . . . , N − 1, w dziedzinie zmiennej n.
Dyskretną transformację
o jądrze a
(k, n), k, n = 0, 1, 2, . . . , N − 1, lub alternatywnie o macierzy
transformacji A
= [a(k, n)], definiuje się wyrażeniem
X (k) =
N−1
n=0
x(n)a(k, n)
Sygnał X
(k), k = 0, 1, 2, . . . , N − 1, nazywa się
transformatą
sygnału x
(n)
lub reprezentacją sygnału x
(n) w dziedzinie przetransformowanej,
określonej za pomocą zmiennej k. Złożoność obliczeniowa O
(N
2
).
Uwaga
Dzięki dobrze dobranej transformacji możemy np. jednakowo ważne próbki
x(n) zastąpić próbkami X (k) o różnych stopniach ważności.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
14 / 51
Macierzowe równanie transformacji sygnału
Zdefiniujmy wektory
x
=
⎡
⎢
⎢
⎢
⎢
⎣
x(0)
x(1)
..
.
x(N − 1)
⎤
⎥
⎥
⎥
⎥
⎦
, X =
⎡
⎢
⎢
⎢
⎢
⎣
X (0)
X (1)
..
.
X (N − 1)
⎤
⎥
⎥
⎥
⎥
⎦
Wówczas
X
= Ax
O macierzy A zakładamy, że jest nieosobliwa, wówczas istnieje
transformacja odwrotna
x
= A
−1
X
= BX
o macierzy B
= A
−1
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
15 / 51
Transformacja odwrotna i energia sygnału
Definicja transformacji odwrotnej
Wprowadźmy oznaczenie B
= A
−1
= [b(n, k)] Transformacja odwrotna do
transformacji o jądrze a
(k, n), k, n = 0, 1, 2, . . . , N − 1, przy czym
A
= [a(k, n)], jest określona wyrażeniem
x(n) =
N−1
k=0
X (k)b(n, k) .
Twierdzenie o transformacji ortogonalnej (unitarnej)
Jeśli macierz A transformacji jest ortogonalna, tzn. A
−1
= A
T
(ogólniej –
unitarna, tzn. A
−1
= A
∗
), to transformata zachowuje energię sygnału
E =
N−1
n=0
|x(n)|
2
=
N−1
k=0
|X (k)|
2
.
Dowód dla sygnałów rzeczywistych: E
= x
T
x
= X
T
A
T
AX
= X
T
X
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
16 / 51
Transformacja odwrotna i energia sygnału
Definicja transformacji odwrotnej
Wprowadźmy oznaczenie B
= A
−1
= [b(n, k)] Transformacja odwrotna do
transformacji o jądrze a
(k, n), k, n = 0, 1, 2, . . . , N − 1, przy czym
A
= [a(k, n)], jest określona wyrażeniem
x(n) =
N−1
k=0
X (k)b(n, k) .
Twierdzenie o transformacji ortogonalnej (unitarnej)
Jeśli macierz A transformacji jest ortogonalna, tzn. A
−1
= A
T
(ogólniej –
unitarna, tzn. A
−1
= A
∗
), to transformata zachowuje energię sygnału
E =
N−1
n=0
|x(n)|
2
=
N−1
k=0
|X (k)|
2
.
Dowód dla sygnałów zespolonych: E
= x
∗
x
= X
∗
A
∗
AX
= X
∗
X
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
17 / 51
Definicja dyskretnej transformacji Fouriera
DFT — discrete Fourier transformation
DFT sygnału x
n
, n
= 0, 1, ..., N − 1, polega na obliczeniu próbek X
k
w tzw. dziedzinie częstotliwości
X
k
=
1
√
N
N−1
n
=0
x
n
W
k
N
n
k = 0, 1, ..., N − 1 oraz W
N
= e
−j
2
π
N
.
Powyższą definicję można zapisać w formie macierzowej
X
= Fx
przy czym
X
=
⎡
⎢
⎢
⎢
⎢
⎣
X
0
X
1
..
.
X
N−1
⎤
⎥
⎥
⎥
⎥
⎦
, x =
⎡
⎢
⎢
⎢
⎢
⎣
x
0
x
1
..
.
x
N−1
⎤
⎥
⎥
⎥
⎥
⎦
, F =
1
√
N
⎡
⎢
⎢
⎢
⎢
⎣
1
1
· · ·
1
1
W
N
· · ·
W
N−1
N
..
.
..
.
. ..
..
.
1 W
N−1
N
· · · W
(N−1)(N−1)
N
⎤
⎥
⎥
⎥
⎥
⎦
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
18 / 51
Definicja dyskretnej transformacji Fouriera
DFT — discrete Fourier transformation
DFT sygnału x
n
, n
= 0, 1, ..., N − 1, polega na obliczeniu próbek X
k
w tzw. dziedzinie częstotliwości
X
k
=
1
√
N
N−1
n=0
x
n
W
nk
N
k = 0, 1, ..., N − 1 oraz W
N
= e
−j
2
π
N
.
Unitarność i symetria DFT
Macierz F jest symetryczna i unitarna. Zatem odwrotne dyskretne
przekształcenie Fouriera jest zdefiniowane wzorem
x
= F
−1
X
= F
∗
X
= F
∗
X
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
19 / 51
Definicja dyskretnej transformacji Fouriera
DFT — discrete Fourier transformation
DFT sygnału x
n
, n
= 0, 1, ..., N − 1, polega na obliczeniu próbek X
k
w tzw. dziedzinie częstotliwości
X
k
=
1
√
N
N−1
n=0
x
n
W
+
nk
N
k = 0, 1, ..., N − 1 oraz
W
N
= e
−j
2
π
N
.
IDFT — inverse discrete Fourier transformation
Przekształcenie odwrotne do DFT jest określone wzorem
x
n
=
1
√
N
N−1
k=0
X
k
W
−
kn
N
przy czym n
= 0, 1, ..., N − 1.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
20 / 51
Definicja dyskretnej transformacji Fouriera
DFT — discrete Fourier transformation
DFT sygnału x
n
, n
= 0, 1, ..., N − 1, polega na obliczeniu próbek X
k
w tzw. dziedzinie częstotliwości
X
k
=
1
√
N
N−1
n
=0
x
n
W
k
N
n
k = 0, 1, ..., N − 1 oraz W
N
= e
−j
2
π
N
.
IDFT - inverse discrete Fourier transformation
Przekształcenie odwrotne do DFT jest określone wzorem
x
n
=
1
√
N
N−1
k
=0
X
k
W
−
n
N
k
przy czym n
= 0, 1, ..., N − 1.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
21 / 51
DFT — discrete Fourier transformation
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
22 / 51
IDFT - inverse discrete Fourier transformation
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
23 / 51
Odkrycie szeregu Fouriera
Jean Baptiste Joseph Fourier
Jean Baptiste Joseph Fourier urodził się w marcu 1768 r. w Auxerre
w Departamencie Yonne we Francji. Jego ojciec był krawcem. W wieku
ośmiu lat został sierotą. Wychowywany był przez Benedyktynów, u których
pobierał nauki. Jako młodzieniec wziął czynny udział w rewolucji
francuskiej. Został wojskowym wykładowcą matematyki. W uznaniu zasług
w 1795 r. otrzymał stanowisko w ´
Ecole Normale Sup´erieure a następnie
w ´
Ecole Polytechnique.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
24 / 51
Odkrycie szeregu Fouriera
Jean Baptiste Joseph Fourier
Jako wojskowy wziął udział w wyprawie Napoleona na Bliski Wschód
w 1798 r., gdzie w Kairze w Egipcie prowadził prace naukowe oraz prace
nad produkcją broni. Interesował sie odprowadzaniem ciepła przy wierceniu
luf i analizą rozkładu temperatur przy przepływie ciepła. Na granicy dwóch
ośrodków występowały nieciągłości (uskoki) w rozkładzie temperatur, co
stanowiło trudność obliczeniową. Fourier rozwiązał równania różniczkowe,
poprzez rozkład szukanych przebiegów w szeregi funkcji harmonicznych.
W 1801 r. wrócił do Francji. W 1807 r. pokazał, że dzięki rozkładowi
w szereg można za pomocą funkcji ciągłych (harmonicznych) opisywać
przebiegi nieciągłe. Matematycy tego okresu włączając Laplace’a
i Lagrange’a uważali to za absurd, co wyrażali używając nawet
niedyplomatycznych określeń.
Fourier zmarł 16. maja 1830 r.
Wagę jednego z największych odkryć ludzkości, jakim jest szereg Fouriera,
docenili dopiero Bunsen i Kirchhoff 35 lat po śmierci Fouriera.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
25 / 51
Dekompozycja Schura
Twierdzenie Schura
Każda macierz kwadratowa A
∈ C
n×n
jest unitarnie podobna do pewnej
macierzy górnotrójkątnej,
innymi słowy istnieje macierz unitarna S
∈ C
n×n
i macierz górnotrójkątna U
∈ C
n×n
takie, że
A
= SUS
−1
= SUS
∗
czyli
U
= S
−1
AS
= S
∗
AS
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
26 / 51
Issai Schur
Issai Schur to niemiecki matematyk żydowskiego pochodzenia. Urodził się
10. stycznia 1875 r. w Mogilewie na Białorusi. Studiował w Berlinie
a następnie był profesorem w Bonn. W 1939 r. wyemigrował
z hitlerowskich Niemiec do Palestyny, gdzie mieszkał w biedzie. Zmarł
w Tel Aviv w dniu 10. stycznia 1941 r., czyli w swoje 66-te urodziny.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
27 / 51
Wzmocnienie wektora x przetwarzanego przez macierz A
maxmag
(A)
= max
x
=0
||Ax||
||x||
minmag
(A)
= min
x
=0
||Ax||
||x||
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
28 / 51
Wartości szczególne
σ
1
i
σ
2
macierzy A
maxmag
(A)
= max
x
=0
||Ax||
||x||
=
σ
1
minmag
(A)
= min
x
=0
||Ax||
||x||
=
σ
2
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
29 / 51
Równość Av
k
= σ
k
u
k
czyli rozkład na wartości szczególne
maxmag
(A)
= max
x
=0
||Ax||
||x||
=
σ
1
,
Av
1
= σ
1
u
1
, v
1
=?
minmag
(A)
= min
x
=0
||Ax||
||x||
=
σ
2
,
Av
2
= σ
2
u
2
, v
2
=?
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
30 / 51
Działanie macierzy ortogonalnej U
Av
1
= σ
1
u
1
, v
1
=?
Av
2
= σ
2
u
2
, v
2
=?
U
=
u
1
u
2
Wektory u
1
, u
2
są bazą przestrzeni kolumnowej (wyjściowej) macierzy A.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
31 / 51
Działanie macierzy ortogonalnej U
Av
1
= σ
1
u
1
, v
1
=?
Av
2
= σ
2
u
2
, v
2
=?
U
=
u
1
u
2
Wektory u
1
, u
2
są bazą przestrzeni kolumnowej (wyjściowej) macierzy A.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
32 / 51
Działanie macierzy diagonalnej Σ
Av
1
= σ
1
u
1
, v
1
=?
Av
2
= σ
2
u
2
, v
2
=?
U
=
u
1
u
2
, Σ =
σ
1
0
0
σ
2
, I =
e
1
e
2
=
1 0
0 1
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
33 / 51
Działanie macierzy ortogonalnej V
Av
1
= σ
1
u
1
Av
2
= σ
2
u
2
V
=
v
1
v
2
Wektory v
1
, v
2
są bazą przestrzeni wierszowej (wejściowej) macierzy A.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
34 / 51
SVD — singular value decomposition AV
= UΣ
Ve
k
= v
k
→ Av
k
= σ
k
u
k
, k = 1, 2
Σe
k
= σ
k
e
k
→ Uσ
k
e
k
= σ
k
u
k
, k = 1, 2
AVI
= UΣI czyli
AV
= UΣ
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
35 / 51
Koncepcja rozkładu na wartości szczególne AV
= UΣ
Rozważamy dowolną rzeczywistą prostokątną macierz A o wymiarze m
× n
i rzędzie r . Zawsze można dobrać dwie bazy ortonormalne wektorów
v
1
, v
2
, . . . , v
r
i u
1
, u
2
, . . . , u
r
takie, że
Av
k
= σ
k
u
k
, k = 1, 2, . . . , r .
Wektory v
k
należą do przestrzeni wejściowej (czyli wierszowej) macierzy A
a wektory u
k
należą do przestrzeni wyjściowej (kolumnowej) macierzy A.
Stąd wynika następująca
zredukowana postać rozkładu macierzy A na
wartości szczególne (zredukowana postać SVD):
A
m×n
v
1
v
2
· · · v
r
n×r
=
u
1
u
2
· · · u
r
m×r
⎡
⎢
⎢
⎢
⎢
⎣
σ
1
σ
2
. ..
σ
r
⎤
⎥
⎥
⎥
⎥
⎦
r×r
A
m×n
V
n×r
= U
m×r
Σ
r×r
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
36 / 51
Ogólna postać rozkładu na wartości szczególne — SVD
Twierdzenie SVD (singular value decomposition)
Niech macierz A
∈ R
m×n
(jest rzeczywista o wymiarze m
× n) i ma rząd r.
Wówczas istnieją macierze U
∈ R
m×m
, Σ
∈ R
m×n
i V
∈ R
n×n
, takie, że
macierze U i V są ortogonalne, macierz Σ ma postać
Σ
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
σ
1
σ
2
0
0
. ..
0
σ
r
0
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
r
n − r
⎫
⎪
⎪
⎪
⎬
⎪
⎪
⎪
⎭
r
} m − r
σ
1
σ
2
· · · σ
r
> 0 to nieujemne liczby rzeczywiste nazywane
wartościami szczególnymi
(ang. singular values) macierzy A, ponadto
A
= UΣV
T
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
37 / 51
Obliczanie wartości szczególnych za pomocą macierzy A
T
A
Rozważmy zredukowaną postać SVD, w której macierz A ma wymiar
m × n a macierz Σ jest diagonalna i ma wymiar r × r. Ze wzoru
A
= UΣV
T
wynika, że
A
T
A
=
UΣV
T
T
UΣV
T
= VΣU
T
UΣV
T
= VΣΣV
T
=
= V
⎡
⎢
⎢
⎢
⎢
⎣
σ
2
1
σ
2
2
. ..
σ
2
r
⎤
⎥
⎥
⎥
⎥
⎦
V
T
.
Wniosek
Kolumny macierzy V zawierają wektory własne symetrycznej macierzy
A
T
A a jej wartości własne to kwadraty wartości szczególnych macierzy A,
czyli
σ
2
1
, σ
2
2
, . . . , σ
2
r
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
38 / 51
Obliczanie wartości szczególnych za pomocą macierzy AA
T
Rozważmy zredukowaną postać SVD, w której macierz A ma wymiar
m × n a macierz Σ jest diagonalna i ma wymiar r × r. Ze wzoru
A
= UΣV
T
wynika, że
AA
T
= UΣV
T
UΣV
T
T
= UΣV
T
VΣU
T
= UΣΣU
T
=
= U
⎡
⎢
⎢
⎢
⎢
⎣
σ
2
1
σ
2
2
. ..
σ
2
r
⎤
⎥
⎥
⎥
⎥
⎦
U
T
.
Wniosek
Kolumny macierzy U zawierają wektory własne symetrycznej macierzy
AA
T
a jej wartości własne to kwadraty wartości szczególnych macierzy A,
czyli
σ
2
1
, σ
2
2
, . . . , σ
2
r
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
39 / 51
Algorytm obliczania
σ
k
, v
k
, u
k
,
k = 1, 2, . . . , r
1
Najpierw należy obliczyć iloczyn A
T
A lub AA
T
, można kierować się
wymiarem otrzymanej macierzy. W pierwszym przypadku jest nim
n × n a w drugim — jest nim m × m. Iloczyn A
T
A jest więc bardziej
dogodny w przypadku n
< m.
2
Następnie wyznaczamy wartości własne
λ
1
, λ
2
, . . . , λ
r
, porządkując je
od największej do najmniejszej (obie macierze, zredukowane do
wymiaru r
× r, są dodatnio określone i mają te same wartości własne).
3
Teraz oblicza się wartości szczególne
σ
k
=
λ
k
, k = 1, 2, . . . , r .
4
Przypuśćmy, że obliczono iloczyn A
T
A. Na tej podstawie wyznacza
się prawe wektory szczególne v
k
, k
= 1, 2, . . . , r.
5
Lewe wektory szczególne u
k
, k
= 1, 2, . . . , r, można by wyliczyć
z macierzy AA
T
, ale prościej jest wykorzystać wzór
u
k
= Av
k
/σ
k
, k = 1, 2, . . . , r .
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
40 / 51
Wyprowadzenie wzoru u
k
= Av
k
/σ
k
,
k = 1, 2, . . . , r
Najpierw zauważmy, że
A
T
Av
k
= σ
2
k
v
k
, k = 1, 2, . . . , r .
Stąd
v
T
k
A
T
Av
k
= σ
2
k
v
T
k
v
k
,
czyli
||Av
k
||
2
= σ
2
k
a więc
||Av
k
|| = σ
k
.
Z pierwszej zależności wnioskujemy także, że
AA
T
Av
k
= σ
2
k
Av
k
.
Zatem
u
k
= Av
k
/||Av
k
|| = Av
k
/σ
k
, k = 1, 2, . . . , r .
W ten sam sposób można udowodnić, że
v
k
= A
T
u
k
/σ
k
, k = 1, 2, . . . , r .
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
41 / 51
Obliczanie
σ
k
, v
k
, u
k
,
k = 1, 2, . . . , r
Przykład obliczania wartości szczególnych
σ
k
,
k = 1, 2
Obliczyć
σ
k
, v
k
, u
k
, k
= 1, 2 macierzy
A
=
1 2 0
2 0 2
Macierz A
T
A ma wymiar 3
× 3 a macierz AA
T
ma wymiar 2
× 2, więc
obliczamy
AA
T
=
5 2
2 8
.
Z równania charakterystycznego
(λ − 5)(λ − 8) − 4 = λ
2
− 13λ + 36 = (λ − 9)(λ − 4) = 0
wynika, że
λ
1
= 9, λ
2
= 4 oraz σ
1
= 3, σ
2
= 2 .
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
42 / 51
Obliczanie
σ
k
, v
k
, u
k
,
k = 1, 2, . . . , r
Przykład obliczania wektorów szczególnych u
k
i v
k
,
k = 1, 2
Rozwiązując równanie
(9I − AA
T
)u
1
wyznaczamy
wektor własny
1
2
i stąd u
1
=
1
√
5
1
2
.
Rozwiązując z kolei równanie
(4I − AA
T
)u
2
wyznaczamy
wektor własny
2
−1
i stąd u
2
=
1
√
5
2
−1
.
Konsekwentnie
v
1
= A
T
u
1
/σ
1
=
1
3
√
5
⎡
⎢
⎣
5
2
4
⎤
⎥
⎦
oraz v
2
= A
T
u
2
/σ
2
=
1
√
5
⎡
⎢
⎣
0
2
−1
⎤
⎥
⎦
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
43 / 51
Wyznaczanie macierzy U, Σ i V
Określenie zredukowanej postacji SVD
Na podstawie otrzymanych wyników wyznaczamy
U
=
u
1
u
2
=
1
√
5
1
2
2
−1
≈
0
.4472
0
.8944
0
.8944 −0.4472
,
Σ
=
σ
1
0
0
σ
2
=
3 0
0 2
,
V
=
v
1
v
2
=
1
3
√
5
⎡
⎢
⎣
5
0
2
6
4
−3
⎤
⎥
⎦
≈
⎡
⎢
⎣
0
.7454
0
0
.2981
0
.8944
0
.5963 −0.4472
⎤
⎥
⎦
,
Zredukowana postać SVD macierzy A, czyli A
= UΣV
T
to
1 2 0
2 0 2
≈
0
.4472
0
.8944
0
.8944 −0.4472
3 0
0 2
0
.7454 0.2981
0
.5963
0
0
.8944 −0.4472
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
44 / 51
Wyznaczanie macierzy U, Σ i V
Określenie pełnej postacji SVD
Rozwiązując równanie
Av
3
= 0
po normalizacji wyniku otrzymujemy
v
3
=
1
3
⎡
⎢
⎣
−2
1
2
⎤
⎥
⎦
≈
⎡
⎢
⎣
−0.6667
0
.3333
0
.6667
⎤
⎥
⎦
.
Pełna postać SVD macierzy A, czyli A
= UΣV
T
to
1 2 0
2 0 2
≈
0
.4472
0
.8944
0
.8944 −0.4472
3 0 0
0 2 0
⎡
⎢
⎣
0
.7454
0
.2981 0.5963
0
0
.8944 −0.4472
−0.6667 0.3333 0.6667
⎤
⎥
⎦
.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
45 / 51
Algorytm HITS przeszukiwania stron internetowych
Firma Google stosuje algorytm HITS (hyperlink-induced topic search)
opracowany przez Jona Michaela Kleinberga do przeszukiwania stron
internetowych, oparty na procedurze SVD macierzy sąsiedztwa A
zawierającej elementy równe 1 lub 0. Element a
kl
macierzy A jest równy 1,
jeśli istnieje link ze strony k do strony l. Algorytm działa następująco:
około 200 stron internetowych ustala się na podstawie wypisanych
słów kluczowych i korzysta się z nich oraz ze wszystkich stron,
z których dochodzą do nich linki i do których wychodzą z nich linki
strony dzielimy na:
strony eksperckie
(ang. authorities) — do nich dochodzą linki z wielu
stron, szczególnie ze stron centralnych
strony centralne
(ang. hubs) — z nich wychodzą linki do wielu stron,
szczególnie do stron eksperckich
poszukujemy rankingu stron eksperckich w postaci wektora x i stron
centralnych w postaci wektora y
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
46 / 51
Algorytm HITS przeszukiwania stron internetowych, cd.
jako początkowe wartości elementów x
0
k
i y
0
k
obu wektorów przyjmuje
się odpowiednio liczby linków dochodzących do i wychodzących
z k-tej strony.
nowe listy rankingowe oblicza się ze wzorów
ranking stron eksperckich
x
1
k
=
l
linkuje do
k
y
0
l
czyli
x
1
= A
T
y
0
ranking stron centralnych
y
1
k
=
k
linkuje do
l
x
0
l
czyli
y
1
= Ax
0
w następnym kroku oblicza się
x
2
= A
T
y
1
=
A
T
A
x
0
oraz
y
2
= Ax
1
=
AA
T
y
0
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
47 / 51
Algorytm HITS przeszukiwania stron internetowych, cd.
macierze
A
T
A
,
AA
T
sa znormalizowane tak, aby były macierzami
Markowa, czyli aby ich dominująca wartość własna była równa 1
po n
= 2k krokach korzystamy z macierzy
(A
T
A
)
k
i
(AA
T
)
k
,
a system dynamiczny realizujący algorytm HITS zbliża się do stanu
ustalonego, który tworzą pierwsze wektory szczególne macierzy A:
dla stron eksperckich
jest to pierwszy prawy wektor szczególny v
1
, czyli
x
n
≈ v
1
dla stron eksperckich
jest to pierwszy lewy wektor szczególny u
1
, czyli
y
n
≈ u
1
.
Uwaga
Algorytm HITS realizuje rozkład SVD macierzy o kilku miliardach wierszy
i kolumn (bo w Świecie jest tyle stron internetowych).
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
48 / 51
Jon Michael Kleinberg
Jon Michael Kleinberg jest profesorem informatyki w Cornell University
w mieście Ithaca w stanie Nowy Jork w USA. Urodził się w październiku
1971 r. w Bostonie (Massachusetts). Studiował w Cornell University
i w Massachusetts Institute of Technology.
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
49 / 51
Macierz pseudoodwrotna Moore-Penrose
Twierdzenie o macierzy pseudoodwrotnej
Niech macierz A
∈ R
m×n
rzędu r ma rozkład SVD na macierze
U
∈ R
m×m
, Σ
∈ R
m×n
i V
∈ R
n×n
. Macierzą pseudoodwrotną
Moore-Penrose macierzy A nazywa się macierz A
†
∈ R
n×m
równą
A
†
= VΣ
†
U
t
przy czym macierz Σ
†
∈ R
n×m
jest określona wzorem
Σ
†
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
σ
−1
1
σ
−1
2
0
0
. ..
0
σ
−1
r
0
0
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
r
m − r
⎫
⎪
⎪
⎪
⎬
⎪
⎪
⎪
⎭
r
} n − r
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
50 / 51
SVD sygnałów akustycznych na wykładzie
Adam Dąbrowski (Politechnika Poznańska)
Algebra z geometrią
25 stycznia 2013
51 / 51
Wyszukiwarka
Podobne podstrony:
14 przejscia fazoweid 15265 Nieznany (2)
piel 38 1 14 79 id 356923 Nieznany
14 Zmaganie sie z choroba1id 1 Nieznany (2)
Przeksztalcenia macierzowe id 4 Nieznany
14 Prowadzenie roznych kierunko Nieznany (4)
14 Poslugiwanie sie dokumentacj Nieznany
Demineralizowana macierz kostna Nieznany
1 Macierzeid 8571 Nieznany (2)
2009 05 30 14;58;17id 26810 Nieznany (2)
2009 05 30 14;58;14id 26809 Nieznany
14 spiaczki cukrzycoweid 15553 Nieznany (2)
14 rozdzial 13 w2pa42u4da5r3dcm Nieznany (2)
AAS piatek 14 30 id 50013 Nieznany
14 elementy i uklady elektronic Nieznany
2009 05 30 14;57;36id 26802 Nieznany
14 Zastosowanie przepisow prawa Nieznany (2)
14 Stosowanie technik laczenia Nieznany (2)
więcej podobnych podstron