\documentclass[twoside,12pt]{article} \usepackage{graphics,latexsym,a4wide} \usepackage[latin2]{inputenc} \usepackage{t1enc} \usepackage[magyar]{babel} \usepackage{hyperref} \newenvironment{proof}{\noindent{\bf Bizonyítás:}}{\qed\bigskip} \newenvironment{proof_sketch}{\noindent{\bf Sketch of Proof}\hspace*{1em}}{\qed\bigskip} \newtheorem{thm}{Tétel} \newtheorem{corollary}{Következmény} \newtheorem{lemma}{Lemma} \newtheorem{claim}{Állítás} \newtheorem{definition}{Definíció} \newtheorem{example}{Példa} \newtheorem{algorithm}{Algoritmus} \newtheorem{note}{Megjegyzés} \newcommand{\qed}{$\Box$} \newcommand{\eloadas}[2]{ %\pagestyle{myheadings}[Hálózatok és a World Wide Web matematikája][#1 \hfill #2] \thispagestyle{empty} \noindent \begin{center}\framebox{ \vbox{ \hbox to 5.875in { {Hálózatok és a World Wide Web matematikája \hfill 2003/2004 I. félév} } \vspace{4mm} \hbox to 5.875in {\hfill {\Large #1} \hfill #2} \vspace{2mm} \hbox to 5.875in { {\it Előadó: Benczúr András\quad \texttt{benczur@sztaki.hu} \hfill } } \hbox to 5.875in { {\it Jegyzetíró: Jankó Zsolt\quad \texttt{janko@sztaki.hu}} \hfill } }}\end{center} \vspace*{4mm} } \begin{document} \eloadas{Ötödik előadás}{2003. november 13.} \section{Mátrixok szinguláris (és spektrál-) felbontása} \begin{note}~ \begin{itemize} \item szinguláris felbontás: minden mátrixra, de mi csak a négyzetes mátrixokra nézzük \item spektrálfelbontás: csak szimmetrikus mátrixokra, speciálisan $AA^{T}$ \end{itemize} \end{note} \paragraph*{Alkalmazások, motiváció} \begin{itemize} \item Kleinberg algoritmus \item klaszterezés \end{itemize} \begin{thm} Minden $A$ mátrix felírható $A=U\Lambda V^{T}$alakban, ahol \begin{itemize} \item $U$, $V$: unitér (más néven ortogonális, ortonormált), azaz $UU^{T}=U^{T}U=I$, vagyis $u_{i.}^{T}u_{.j}=\left\{ \begin{array}{cc} 1 & i=j\\ 0 & \mbox{különben}\end{array} \right.$, ahol $u_{i.}$ az $U$ mátrix $i$-edik sorvektorát, $u_{.j}$ pedig a $j$-edik oszlopvektorát jelöli. $V$-re hasonlóan. \item $\Lambda =\left(\begin{array}{cccc} \sigma _{1} & & & \\ & \sigma _{2} & & \\ & & \ddots & \\ & & & \sigma _{n}\end{array} \right)$, ahol $\sigma _{i}\geq 0$ a szinguláris értékek. \end{itemize} \end{thm} \paragraph*{Motiváció} Kleinberg algoritmusnál \begin{eqnarray*} AA^{T} & = & U\Lambda V^{T}V\Lambda U^{T}=U\Lambda ^{2}U^{T}\\ AA^{T} & = & V\Lambda ^{2}V^{T} \end{eqnarray*} Ezt hívjuk spektrálfelbontásnak. Az oszlopok sajátvektorok, pl. $u_{.j}$ az $AA^{T}$mátrix sajátvektora $\sigma _{j}^{2}$ sajátértékkel. Ugyanis $AA^{T}U=U\Lambda ^{2}U^{T}U=U\Lambda ^{2}=\Lambda ^{2}U$, azaz $AA^{T}u_{.j}=\sigma _{j}^{2}u_{.j}$. A spektrálfelbontás tehát a szinguláris felbontás speciális esete. (Kellene: $\forall B$ szemidefinit szimmetrikus mátrixhoz $\exists A$, $B=AA^{T}$.) \subsection{Kleinberg algoritmus} \begin{tabular}{cclcl} weboldalak& $\longrightarrow $& tekintély (\emph{authority})& $\longrightarrow $& $a=(a_{1},\ldots ,a_{n})$\\ & $\longrightarrow $& hub (\emph{gyűjtőoldal})& $\longrightarrow $& $h=(h_{1},\ldots ,h_{n})$\\ \end{tabular} \medskip{} \noindent \begin{tabular}{ll} $a=hA$& $a=aA^{T}A$\\ $h=aA^{T}$& $h=hAA^{T}$\\ \end{tabular} \medskip{} \noindent Ha az induló vektor nem merőleges az első sajátvektorra, akkor $a=v_{1}$ és $h=u_{1}$ (a $\sigma _{1}^{2}$ sajátértékhez tartozó első oszlopvektorok). Megjegyzés: $AA^{T}$és $A^{T}A$ sajátértékei azonosak. \noindent A Kleinberg algoritmus tehát az első szinguláris vektorokat adja. \begin{claim} $v_{1}$ maximalizálja az $\left\{ \left\Vert Av\right\Vert :\left\Vert v\right\Vert =1\right\} $ halmazt (a normalizálást az $a$, $h$ számításakor fel kell tenni), hasonlóan $u_{1}$ maximalizálja az $\left\{ \left\Vert A^{T}u\right\Vert :\left\Vert u\right\Vert =1\right\} $ halmazt. \end{claim} \paragraph*{Jelentés 1} $\left\Vert A^{T}u\right\Vert =\left\Vert u^{T}A\right\Vert $ A gyűjtőoldal pontokat az élek mentén kiküldöm. A gyűjtőoldal vektor a lehető legtöbb pontot küldi, a lehető legtöbb tekintélyt éri el. \paragraph*{Jelentés 2} $\left\Vert Av\right\Vert =\left\Vert v^{T}A^{T}\right\Vert $ A tekintélyoldal pontszám a legjobb kiosztás, ha a lehető legtöbb helyre akarom a pontszámot fordított éleken visszavinni. \paragraph*{További motiváció az $u_{1}$, $v_{1}$ jelentésére} $\left\{ x^{T}A:\left\Vert x\right\Vert =1\right\} $ azaz az egységgömbön végrehajtjuk az $A$ mátrix szerinti lineáris transzformációt. A kapott halmaz egy ellipszis. Más értelemben: a gráf élein az $x$ szerinti értékeket továbbviszem. $y^{T}=x^{T}A$ $y=A^{T}x$ $A^{T}=V\Lambda U^{T}=V\left(\begin{array}{ccc} \sigma _{1} & & \\ & \ddots & \\ & & \sigma _{n}\end{array} \right)U^{T}$ \begin{claim} $\left\{ y=A^{T}x:\left\Vert x\right\Vert =1\right\} $ ellipszoid, főtengelyei a $v_{i}$-k, hosszuk $\sigma _{i}$. \end{claim} \paragraph*{\emph{Ábra}} $\left\{ y=A^{T}x:x=(0,\ldots ,0,1,0,\ldots ,0)^{T},\textrm{ azaz a csúcsok}\right\} $ mindig félellipszoidot ad, mert az első $h,a$ vektorban nincsenek negatív értékek \emph{első 3 tekintély és gyűjtőoldal pontszáma a gráf csúcsainak} \subsection{Bizonyítások} A bizonyításokhoz: \begin{claim} $UU^{T}=I\Longrightarrow \forall x:\left\Vert Ux\right\Vert =\left\Vert x\right\Vert $ (ezért ,,unitér'' a neve), azaz nem változtatja a hosszat, forgatás. \end{claim} \begin{proof} $\left\Vert Ux\right\Vert ^{2}=(Ux)^{T}(Ux)=x^{T}U^{T}Ux=x^{T}x=\left\Vert x\right\Vert ^{2}$ \end{proof} \begin{proof} \emph{Az ellipszoidos állítás bizonyítása} $y=A^{T}x\textrm{, tehát }x=(A^{T})^{-1}y\textrm{, így }1=\left\Vert x\right\Vert =\left\Vert (A^{T})^{-1}y\right\Vert $ Mivel $A^{T}=V\Lambda U^{T}$, ezért $(A^{T})^{-1}=U\Lambda ^{-1}V^{T}$, ugyanis $A^{T}(A^{T})^{-1}=U\Lambda ^{-1}V^{T}V\Lambda U^{T}=I$, ahol $\Lambda ^{-1}=\left(\begin{array}{ccc} 1/\sigma _{1} & & \\ & \ddots & \\ & & 1/\sigma _{n}\end{array} \right)$. $1=\left\Vert x\right\Vert =\left\Vert A^{-T}y\right\Vert =\left\Vert U\Lambda ^{-1}V^{T}y\right\Vert =\left\Vert \Lambda ^{-1}y\right\Vert =\sqrt{\sum (y_{i}/\sigma _{i})^{2}}$ A főtengelyek hossza valóban $\sigma _{i}$ irányuk: $A^{T}x=V\Lambda U^{T}x$, azaz $V$ szerint elforgatjuk a $\Lambda U^{T}x$ ellipszoidot $\Longrightarrow$ a $\sigma _{i}$ hosszú tengely $v_{i}$-be fordul. \end{proof} \begin{lemma} $\max \left\{ \left\Vert Ax\right\Vert :\left\Vert x\right\Vert =1\right\} =\max \left\{ \left\Vert A^{T}y\right\Vert :\left\Vert y\right\Vert =1\right\} $ (a jelentése pont az, hogy az $AA^{T}$és az $A^{T}A$ mátrixok legnagyobb sajátértéke ugyanaz). \end{lemma} \begin{proof} $\sigma _{1}=\max \left\{ \left\Vert Ax\right\Vert :\left\Vert x\right\Vert =1\right\} =\max _{\left\Vert x\right\Vert =\left\Vert y\right\Vert =1}\left\{ \left\Vert y^{T}Ax\right\Vert \right\} $ a Cauchy-egyenlőtlenség miatt, ami kimondja, hogy $(y^{T}Ax)^{2}\leq \left\Vert y\right\Vert \left\Vert Ax\right\Vert $, és $=$, ha $y$-t $Ax$ irányába választjuk. Mivel $y^{T}Ax$ skalár, azaz $y^{T}Ax=x^{T}A^{T}y$, továbbá $\max \left\{ \left\Vert A^{T}y\right\Vert :\left\Vert y\right\Vert =1\right\} =\max _{\left\Vert x\right\Vert =\left\Vert y\right\Vert =1}\left\{ \left\Vert x^{T}A^{T}y\right\Vert \right\} $, így pont a lemma állítását kapjuk. \end{proof} \begin{proof} \emph{Tétel bizonyítása} Keressük $\sigma _{1}$-et úgy, hogy $\sigma _{1}=\max _{\left\Vert v\right\Vert =1}\left\Vert Av\right\Vert $ és $v_{1}$ maximalizáljon. Legyen $u_{1}=\frac{1}{\sigma _{1}}Av_{1}$ és megmutatjuk, hogy ez jó első szinguláris vektorpár ill. érték választás. Tovább indukcóval egy kisebb mátrixon. Kell: $\Lambda =U^{T}(U\Lambda V^{T})V=U^{T}AV$ Állítás: $\left(\frac{u_{1}^{T}}{U^{\star }}\right)A(\left.v_{1}\right|V^{\star })=\left(\begin{array}{cccc} \sigma _{1} & 0 & \ldots & 0\\ 0 & & & \\ \vdots & & A^{\star } & \\ 0 & & & \end{array} \right)=x$ (ha ezt beláttuk, akkor $A^{\star }$-ra indukcióval, és kész). Bizonyítjuk az állítást: $U^{\star }$ és $V^{\star }$ tetszőleges úgy, hogy $\left(\frac{u_{1}^{T}}{U^{\star }}\right)$ és $(\left.v_{1}\right|V^{\star })$ unitér. $x_{ij}=u_{i}^{T}Av_{j}$, azaz $x_{11}=u_{1}^{T}Av_{1}=\left(\frac{1}{\sigma _{1}}Av_{1}\right)^{T}Av_{1}=\frac{1}{\sigma _{1}}\left\Vert Av_{1}\right\Vert ^{2}=\sigma _{1}$ (az $u_{1}$-et úgy választottuk, hogy $\sigma _{1}$ kijöjjön). Most használni kell, hogy $v_{1}$ maximalizál: első oszlop: $x_{.1}=UAv_{1}$ csak úgy lehet $\sigma _{1}$ hosszú, ha $x_{12}=\ldots =x_{1n}=0$ első sor: $x_{1.}=u_{1}^{T}AV$ $\left\Vert x_{1.}\right\Vert =\left\Vert u_{1}^{T}AV\right\Vert =\left\Vert u_{1}^{T}A\right\Vert =\left\Vert A^{T}u_{1}\right\Vert $ $\left\Vert u_{1}\right\Vert =\left\Vert \frac{1}{\sigma _{1}}Av_{1}\right\Vert =\frac{1}{\sigma _{1}}\left\Vert Av_{1}\right\Vert =1$ Mivel $\max \left\{ \left\Vert Av\right\Vert :\left\Vert v\right\Vert =1\right\} =\sigma _{1}$, ezért $\max \left\{ \left\Vert A^{T}u_{1}\right\Vert :\left\Vert u_{1}\right\Vert =1\right\} =\sigma _{1}$ az állítás szerint $\Longrightarrow $ $\left\Vert x_{1.}\right\Vert =\left\Vert A^{T}u_{1}\right\Vert \leq \sigma _{1}$, tehát $x_{11}=\sigma _{1}$ miatt $x_{12}=\ldots =x_{1n}=0$. \end{proof} \subsection{Rövid összefoglalás} $v_{1}$-et úgy választottuk, hogy az ellipszoid leghosszabb tengelye legyen.\\ $u_{1}=\frac{1}{\sigma _{1}}Av_{1}$\\ $u_{1}^{T}=\frac{1}{\sigma _{1}}v_{1}^{T}A^{T}\Longrightarrow $ pont az egy Kleinberg-iteráció lépéssel kapott vektor lesz az $u_{1}$.\\ Azt bizonyítottuk, hogy ez a transzponált transzformáció ellipszoid főtengelye. \begin{note} Algoritmusunk is lett szinguláris felbontásra. \end{note} \begin{algorithm}~ \begin{enumerate} \item $h_{1}$ és $a_{1}$ vektorokat számolni néhány iterációban. \item $h_{2}$ és $a_{2}$ számolása úgy, hogy minden lépésben $h_{1}$-re ill. $a_{1}$-re merőlegesen vetítünk. \item \emph{i-edik lépés:} $h_{i}$ és $a_{i}$, vetítsük a $h_{1},\ldots ,h_{i-1}$ ill. $a_{1},\ldots ,a_{i-1}$ altérre \end{enumerate} \end{algorithm} \end{document}