Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Statystyka II – 3. Analiza Składowych Głównych – MIM UW

Zagadnienia

3. Analiza Składowych Głównych

3.1. Analiza danych wielowymiarowych

Oznaczenia:

  • X będzie oznaczał wektor losowy w przestrzeni \mathbb{R}^{p}: X=\left(\begin{array}[]{c}X_{1}\\
\ldots\\
X_{p}\\
\end{array}\right).

  • Przez t oznaczymy wektor liczb, t\in\mathbb{R}^{p}.

  • C to macierz liczb: C\in\mathbb{R}^{{r\times p}}.

  • \Sigma będzie oznaczać macierz kowariancji wektora losowego X, czyli:

    \Sigma=\left(\mathbb{E}(X_{i}-\mathbb{E}X_{i})(X_{j}-\mathbb{E}X_{j})\right)^{p}_{{i,j=1}}.

    Oznaczeń \Sigma=\text{Var}(X)=\text{Cov}(X) będziemy używać zamiennie.

Stwierdzenie 3.1

Proste własności wprowadzonych pojęć:

  1. \mathbb{E}(t^{T}X)=t^{T}\mathbb{E}X, \mathbb{E}(X^{T}t)=(\mathbb{E}X)^{T}t.

  2. \mathbb{E}(CX)=C\text{ }\mathbb{E}X, gdzie:

    C=\left(\begin{array}[]{c}C_{1}^{T}\\
\ldots\\
C_{r}^{T}\\
\end{array}\right),\quad\mathbb{E}(CX)\stackrel{(1)}{=}\left(\begin{array}[]{c}C_{1}^{T}\\
\ldots\\
C_{r}^{T}\\
\end{array}\right)\mathbb{E}X

    .

  3. Macierz kowariancji jest równa:

    \Sigma=\mathbb{E}\left[(X-\mathbb{E}X)(X-\mathbb{E}X)^{T}\right].
  4. Macierz kowariancji ma następującą własność:

    \displaystyle\text{Var}(CX)= \displaystyle\mathbb{E}\left[(CX-\mathbb{E}CX)(CX-\mathbb{E}CX)^{T}\right]=
    \displaystyle= \displaystyle\mathbb{E}\left[C(X-\mathbb{E}X)(X-\mathbb{E}X)^{T}C^{T}\right]=
    \displaystyle= \displaystyle C\text{ }\mathbb{E}\left[(X-\mathbb{E}X)(X-\mathbb{E}X)^{T}\right]C^{T}=
    \displaystyle= \displaystyle C(\text{Var}X)C^{T}.
  5. Ponadto, macierz \text{Var}(X) jest symetryczna i nieujemnie określona:

    symetryczność wynika z symetryczności kowariancji dwóch zmiennych losowych;

    nieujemna określoność wynika z nieujemności wariancji dla zmiennej losowej. Dla C^{T} o wymiarach 1\times p:

    0\leq\text{Var}(\underbrace{C^{T}X}_{{\text{zm losowa}}})\stackrel{(4)}{=}C^{T}\text{Var}(X)C=C^{T}\Sigma C.
  6. Jeżeli \text{Var}(X)=\sigma^{2}I_{p}, a macierz C jest ortonormlna o wymiarach p\times p (C^{T}C=CC^{T}=I_{p}), to:

    \text{Var}(CX)=C\text{Var}(X)C^{T}=\sigma^{2}CC^{T}=\sigma^{2}I_{p}\text{ , czyli się nie zmienia.}

3.2. Redukcja Wymiaru danych

Wygodną postacią macierzy wariancji \Sigma=\text{Var}(X) jest postać diagonalna. Wtedy korelacje pomiędzy różnymi elementami wektora losowego są zerowe.

Problem 3.1

Jak przekształcić wektor losowy X żeby zdiagonalizować \Sigma?

Twierdzenie 3.1

Rozkład spektralny macierzy symetrycznej A. Dla symetrycznej macierzy A o wymiarze p\times p istnieją:

  • ortonormalna (czyli VV^{T}=I_{p}) macierz kwadratowa V o wymiarze p\times p, oznaczmy V=[v_{1},\ldots,v_{p}];

  • diagonalna macierz \Lambda o wyrazach na przekątnych (\lambda _{1},\ldots,\lambda _{p}), że

Av_{i}=\lambda _{i}v_{i}\text{ , czyli }

v_{i} to wektory własne macierzy A, a \lambda _{i} to wartości własne, które dla macierzy symetrycznej są rzeczywiste. Wtedy:

\displaystyle A[v_{1},\ldots,v_{p}] \displaystyle=[\lambda _{1}v_{1},\ldots,\lambda _{p}v_{p}];
\displaystyle AV \displaystyle=V\Lambda;
\displaystyle A \displaystyle=V\Lambda V^{T};
\displaystyle\Lambda \displaystyle=V^{T}AV.

Ponieważ macierz kowariancji \Sigma wektora losowego X jest symetryczna, możemy zastosować do niej rozkład spektralny: \Sigma=V\Lambda V^{T}. Pomnóżmy wektor X przez macierz V^{T}: V^{T}X. Macierz kowariancji dla takiego wektora to:

\text{Var}(V^{T}X)=V^{T}\text{Var}(X)V=V^{T}\Sigma(X)V=\Lambda.

Ponieważ macierz \Sigma jest nieujemnie określona, wszystkie jej wartości własne są nieujemne: \lambda _{i}\geq 0. Uporządkujmy wartości własne \lambda _{i} i odpowiadające im wektory własne v_{i} tak, żeby \lambda _{1}\geq\lambda _{2}\geq\ldots\geq\lambda _{p}\geq 0. Oznaczmy dla tak ustawionych wektorów własnych:

Y=V^{T}X.

3.2.1. Analiza składowych głównych – wersja populacyjna

Definicja 3.1

Mamy wektor losowy X\in\mathbb{R}^{p} oraz macierz kowariancji \text{Var}(X)=\Sigma=V\Lambda V^{T}.

Składowymi głównymi (principal components) nazywamy elementy wektora [Y_{1},\ldots,Y_{p}]^{T}=Y=V^{T}X.

Kierunkami głównymi (rotations) nazywamy kolumny macierzy V=[v_{1},\ldots,v_{p}].

Stwierdzenie 3.2

Własności składowych głównych:

  • wsółrzędne wektora Y są nieskorelowane;

  • wariancje poszczególnych Y_{i} równe są \lambda _{i};

  • Y_{i} ustawione są od 1 do p w kolejności nierosnących wariancji;

  • Y_{i} to kombinacje liniowe zmiennych losowych X_{1},\ldots,X_{p};

Stwierdzenie 3.3

Kierunki główne to unormowane wektory, w kierunku których obserwujemy największą wariancję danych, będące wzajemnie do siebie prostopadłe:

  1. jeżeli t_{1}\in\mathbb{R}^{p}, t_{1}^{T}t_{1}=1 \Rightarrow \text{Var}(t_{1}^{T}X) osiąga maksimum=\lambda _{1} dla t_{1}=v_{1}.

  2. jeżeli t_{2}\in\mathbb{R}^{p}, t_{2}^{T}t_{2}=1, t_{2}^{T}t_{1}=0 \Rightarrow \text{Var}(t_{2}^{T}X) osiąga maksimum=\lambda _{2} dla t_{2}=v_{2}.

V=[v_{1},\ldots,v_{p}] jest bazą ortonormalną przestrzeni \mathbb{R}^{p}.

  1. Zapiszmy t_{1} w tej bazie: t_{1}=\sum _{{i=1}}^{p}c_{i}v_{i}, gdzie c_{i}\in\mathbb{R} współczynniki. Z założeń wynika:

    t_{1}^{T}t_{1}=\sum _{{i=1}}^{p}c_{i}^{2}=1.

    Zauważmy, że:

    \text{Var}(t_{1}^{T}X)=t_{1}^{T}\text{Var}(X)t_{1}=(c_{1}v_{1}^{T}+\ldots+c_{p}v_{p}^{T})\cdot\Sigma\cdot(c_{1}v_{1}+\ldots+c_{p}v_{p})=

    z własności wektorów własnych macierzy,

    =(c_{1}v_{1}^{T}+\ldots+c_{p}v_{p}^{T})\cdot(\lambda _{1}c_{1}v_{1}+\ldots+\lambda _{p}c_{p}v_{p})=\sum _{{i=1}}^{p}\lambda _{i}c_{i}^{2}\leq\lambda _{1}.

    Jeżeli przyjmiemy t_{1}=v_{1}, czyli c_{1}=1, c_{{\geq 2}}=0, otrzymujemy kombinację liniową o maksymalnej wariancji równej \lambda _{1}.

  2. Ponieważ t_{2}^{T}v_{1}=0, możemy zapisać:

    \text{Var}(t_{2}^{T}X)=t_{2}^{T}\text{Var}(X)t_{2}=(c_{2}v_{2}^{T}+\ldots+c_{p}v_{p}^{T})\cdot\Sigma\cdot(c_{2}v_{2}+\ldots+c_{p}v_{p})=
    =\sum _{{i=2}}^{p}\lambda _{i}c_{i}^{2}\leq\lambda _{2}.

    Analogicznie, t_{2}=v_{2}.

Stwierdzenie 3.4

Ponieważ V jest macierzą ortonormalną, możemy interpretować V^{T}X jako współrzędne dla obróconego układu. Dla p=2 obrócone osie byłyby wyznaczone przez v_{1} i v_{2}, przy czym v_{1} byłby kierunkiem, w którym mamy największą zmienność danych, a v_{2} prostopadłym do niego (rysunek 3.1).

\par
Rys. 3.1. Kierunki główne wyznaczją obrócone osie układu współrzędnych.
Definicja 3.2

Całkowity rozrzut danych dla wektora losowego X to suma wariancji jego współrzędnych: \sum _{{i=1}}^{p}\text{Var}(X_{i}). Wariancje poszczególnych X_{i} można interpretować jako ilość informacji, jaką przechowuje dana zmienna: im większa wariancja, tym lepiej możemy różnicować obserwowane wielkości.

Uwaga 3.1

Ślady macierzy \Sigma i \Lambda równają się sobie, czyli całkowite rozrzuty danych dla X i Y są równe:

\sum _{{i=1}}^{p}\lambda _{i}=\text{tr}(\Lambda)=\text{tr}(V^{T}\Sigma V)=\text{tr}(V^{T}V\Sigma)=\text{tr}(\Sigma)

.

Istotnym parametrem diagnostycznym przy rozważaniu analizy składowych głównych jest:

\frac{\lambda _{1}+\ldots+\lambda _{k}}{\lambda _{1}+\ldots+\lambda _{p}},

czyli część całkowitego rozrzutu danych wyjaśniona przez k pierwszych składowych głównych. Na jego podstawie dokonuje się redukcji wymiaru danych: z p zmiennych zostaje utworzone k kombinacji liniowych tych zmiennych, które wyjaśniają np. 90\% zmienności wyjściowych danych.

3.2.2. Analiza składowych głównych – wersja próbkowa

Podejście próbkowe do analizy danych różni się od populacyjnego tym, że w podejściu populacyjnym do analizy brana jest zmienna losowa, a w podejściu próbkowym jej realizacje. Dlatego teraz zamiast wektora zmiennych losowych X będziemy rozpatrywać macierz jego n realizacji:

X=\left(\begin{array}[]{ccc}X_{{11}}&\ldots&X_{{1p}}\\
X_{{21}}&\ldots&X_{{2p}}\\
&\ldots&\\
X_{{n1}}&\ldots&X_{{np}}\\
\end{array}\right)\quad=\quad\left(\begin{array}[]{c}X_{1}^{T}\\
X_{2}^{T}\\
\ldots\\
X_{n}^{T}\\
\end{array}\right).

Do analizy potrzebna będzie macierz kowariancji próbkowej. Zdefiniujmy scentrowaną macierz X jako:

X_{c}=\left(\begin{array}[]{ccc}X_{{11}}-\overline{X}_{{.1}}&\ldots&X_{{1p}}-\overline{X}_{{.p}}\\
X_{{21}}-\overline{X}_{{.1}}&\ldots&X_{{2p}}-\overline{X}_{{.p}}\\
&\ldots&\\
X_{{n1}}-\overline{X}_{{.1}}&\ldots&X_{{np}}-\overline{X}_{{.p}}\\
\end{array}\right)\quad=\quad\left(\begin{array}[]{c}X_{{c1}}^{T}\\
X_{{c2}}^{T}\\
\ldots\\
X_{{cn}}^{T}\\
\end{array}\right),

gdzie \overline{X}_{{.i}}=\frac{1}{n}\sum _{{j=1}}^{n}X_{{ji}}, i=1,\ldots,p.

Zauważmy, że macierz kowariancji próbkowej możemy wyrazić za pomocą macierzy:

S=\text{var}(X)=\frac{1}{n-1}X_{c}^{T}X_{c}=\frac{1}{n-1}\sum _{{i=1}}^{n}X_{{ci}}X_{{ci}}^{T},

która jest nieobciążonym estymatorem macierzy kowariancji:

\Sigma=\mathbb{E}[(X-\mathbb{E}X)(X-\mathbb{E}X)^{T}].

Macierz S jest symetryczna i nieujemnie określona. Znajdźmy składowe główne dla podejścia próbkowego tą samą metodą jak dla podejścia populacyjnego:

V^{T}SV=\Lambda=\frac{1}{n-1}V^{T}X_{c}^{T}X_{c}V=\frac{1}{n-1}(X_{c}V)^{T}X_{c}V=\frac{1}{n-1}Y^{T}Y.
Wniosek 3.1

Składowe główne dla problemu próbkowego równe są wektorom [Y_{1},\ldots,Y_{p}]=Y=X_{c}V, macierz kowariancji próbkowej dla Y jest równa \Lambda.

3.2.3. Rozkład na wartości szczególne (Singular Value Decomposition)

Rozkład SVD posłuży nam do tańszej obliczeniowo konstrukcji składowych głównych w wersji próbkowej.

Twierdzenie 3.2

Rozkład na wartości szczególne Dla dowolnej macierzy A\in\mathbb{R}^{{m\times n}} m\geq n, \exists U macierz ortonormalna \in\mathbb{R}^{{m\times n}} oraz V macierz ortonormalna \in\mathbb{R}^{{n\times n}} takie, że A=U\Sigma V^{T}, gdzie \Sigma\in\mathbb{R}^{{m\times n}} jest macierzą diagonalną:

\Sigma=\left(\begin{array}[]{cc}\Sigma^{{\prime}}&0\\
0&0\\
\end{array}\right)\quad,\quad\Sigma^{{\prime}}=\text{diag}(\sigma _{i})\text{ }\in\mathbb{R}^{{k\times k}},
\sigma _{1}\geq\ldots\geq\sigma _{k}>\sigma _{{k+1}}=\ldots=\sigma _{n}=0,

gdzie k jest rzędem macierzy A. Rozkład taki nazywamy szerokim rozkładem SVD, w odróżnieniu od wąskiego rozkładu SVD, w którym skracamy macierze do istotnych obliczeniowo:

\left(\begin{array}[]{c}\\
A\\
\\
\end{array}\right)_{{m\times n}}=\left(\begin{array}[]{c}\\
U\\
\\
\end{array}\right)_{{m\times m}}\left(\begin{array}[]{c}\\
\Sigma\\
\\
\end{array}\right)_{{m\times n}}\left(\begin{array}[]{c}\\
V\\
\\
\end{array}\right)_{{n\times n}}^{T}=
=\left(\begin{array}[]{ccc}&|&\\
\left(\begin{array}[]{c}U_{1}\\
\end{array}\right)_{{m\times k}}&|&\left(\begin{array}[]{c}U_{2}\\
\end{array}\right)_{{m\times(m-k)}}\\
&|&\\
\end{array}\right)\left(\begin{array}[]{cc}\Sigma^{{\prime}}&0\\
&\\
0&0\\
\end{array}\right)\left(\begin{array}[]{c}\left(\begin{array}[]{c}V_{1}\\
\end{array}\right)^{T}_{{n\times k}}\\
\\
\left(\begin{array}[]{c}V_{2}\\
\end{array}\right)^{T}_{{n\times(n-k)}}\\
\end{array}\right)=
=U_{1}\Sigma^{{\prime}}V_{1}^{T}.

Zauważmy, że macierz A^{T}A jest symetryczna i nieujemnie określona:

\forall t\in\mathbb{R}^{n}\quad t^{T}(A^{T}A)t=(At)^{t}(At)\geq 0.

Zatem, korzystając z rozkładu spektralnego dla A^{T}A otrzymujemy:

V^{T}(A^{T}A)V=\text{diag}(\lambda _{i})=\text{diag}(\sigma _{1}^{2},\ldots,\sigma _{n}^{2}), (3.1)

gdzie założymy, że \sigma _{i} to nieujemne pierwiastki z \lambda _{i}:

\sigma _{1}\geq\ldots\geq\sigma _{k}>\sigma _{{k+1}}=\ldots=\sigma _{n}=0.

Zauważmy, że V_{1}^{T}A^{T}AV_{1} jest podmacierzą V^{T}(A^{T}A)V o niezerowych wyrazach na przekątnej:

V_{1}^{T}A^{T}AV_{1}=\left(\begin{array}[]{ccc}\sigma _{1}^{2}&&0\\
&\ldots&\\
0&&\sigma _{k}^{2}\\
\end{array}\right)

Zdefiniujmy U_{1} jako:

U_{1}=AV_{1}\text{ diag}(\sigma _{1}^{{-1}},\ldots,\sigma _{k}^{{-1}}),

skąd otrzymujemy:

U_{1}\text{ diag}(\sigma _{1},\ldots,\sigma _{k})=AV_{1}.
U_{1}^{T}U_{1}=\left(\begin{array}[]{ccc}\sigma _{1}^{{-1}}&&0\\
&\ldots&\\
0&&\sigma _{k}^{{-1}}\\
\end{array}\right)\underbrace{V_{1}^{T}A^{T}AV_{1}}_{{\text{diag}(\sigma _{1}^{2},\ldots,\sigma _{k}^{2})}}\left(\begin{array}[]{ccc}\sigma _{1}^{{-1}}&&0\\
&\ldots&\\
0&&\sigma _{k}^{{-1}}\\
\end{array}\right)=I_{k}.

Uzupełniamy dowolnie U_{1} do ortonormalnej macierzy n\times n : U=\left(\begin{array}[]{ccc}U_{1}&|&U_{2}\\
\end{array}\right). Wtedy:

U^{T}AV=\left(\begin{array}[]{c}U_{1}^{T}\\
U_{2}^{T}\\
\end{array}\right)A\left(\begin{array}[]{ccc}V_{1}&|&V_{2}\\
\end{array}\right)=\left(\begin{array}[]{cc}U_{1}^{T}AV_{1}&U_{1}^{T}AV_{2}\\
U_{2}^{T}AV_{1}&U_{2}^{T}AV_{2}\\
\end{array}\right)=

ponieważ ze wzoru (3.1) wynika, że \forall i takiego, że v_{i}\in V_{2}, v_{i}^{T}(A^{T}A)v_{i}=(Av_{i})^{T}(Av_{i})=\sigma^{2}_{i}=0, a norma euklidesowa wektora jest równa zero wtedy i tylko wtedy gdy wektor jest równy zero, otrzymujemy:

=\left(\begin{array}[]{ccc}\text{diag}(\sigma _{1}^{{-1}},\ldots,\sigma _{k}^{{-1}})\underbrace{V_{1}^{T}A^{T}AV_{1}}_{{=\text{diag}(\sigma _{1}^{{2}},\ldots,\sigma _{k}^{{2}})}}&|&0\\
U_{2}^{T}U_{1}\text{ diag}(\sigma _{1},\ldots,\sigma _{k})&|&0\\
\end{array}\right)=
=\left(\begin{array}[]{ccc}\text{diag}(\sigma _{1},\ldots,\sigma _{k})&|&0_{{k\times(n-k)}}\\
0_{{(m-k)\times k}}&|&0_{{(m-k)\times(n-k)}}\\
\end{array}\right)=\Sigma.

Z równości U^{T}AV=\Sigma, ponieważ U i V są macierzami ortonormalnymi, wynika:

A=U\Sigma V^{T}=U_{1}\Sigma^{{\prime}}V_{1}^{T}.
Stwierdzenie 3.5

Wróćmy do analizy składowych głównych. Do scentrowanej macierzy danych X_{c} o wymiarze n\times p użyjmy wąskiego rozkładu SVD i oznaczmy:

X_{c}=U\Lambda V^{T};

wtedy:

\text{var}(X_{c})=S=\frac{1}{n-1}X_{c}^{T}X_{c}=\frac{1}{n-1}V\Lambda^{T}\underbrace{U^{T}U}_{{=I_{p}}}\Lambda V^{T}=
=\frac{1}{n-1}V\Lambda^{2}V^{T}=VDV^{T}.
Wniosek 3.2

Zauważmy, że:

  1. Składowe główne w wersji próbkowej przy użyciu rozkładu SVD:

    Y=X_{c}V=U\Lambda V^{T}V=U\Lambda=[\lambda _{1}U_{1},\ldots,\lambda _{p}U_{p}].

    Obliczanie składowych głównych z tego wzoru jest tańsze obliczeniowo.

  2. Widać związek pomiędzy rozkładem SVD dla X=U\Sigma V^{T} oraz rozkładem spektralnym dla X^{T}X=V\Sigma^{2}V^{T}.

  3. Podobnie jest dla XX^{T}=U\Sigma\underbrace{V^{T}V}_{{=I}}\Sigma U^{T}=U\Sigma^{2}U^{T}.

3.2.4. Kolejna zaleta analizy składowych głównych

Wróćmy do analizy składowych głównych w wersji populacyjnej.

Stwierdzenie 3.6

Przy założeniu, że wektor losowy X\in\mathbb{R}^{p} jest scentrowany \mathbb{E}X=0, możemy zapisać \text{Var}(X)=\mathbb{E}(XX^{T}). Korzystając z rozkładu spektralnego, oznaczmy \text{Var}(X)=\Sigma=V\Lambda V^{T}. Wtedy:

\forall\  k\leq p\quad\text{układ }v_{1},\ldots,v_{k}\quad\text{minimalizuje}\quad\mathbb{E}||X-\sum _{{i=1}}^{k}(X^{T}a_{i})a_{i}||^{2}
wśród wszystkich układów ortonormalnych a_{1},\ldots,a_{k}.

Czyli w sensie minimalizacji błędu średniokwadratowego najlepszym k-wymiarowym przybliżeniem X jest rzut ortogonalny X na k pierwszych kierunków głównych.

\mathbb{E}(X-\sum _{j}(X^{T}a_{j})a_{j})^{T}(X-\sum _{i}(X^{T}a_{i})a_{i})=
=\mathbb{E}X^{T}X-\mathbb{E}\sum _{i}(X^{T}a_{i})(a_{i}^{T}X)-\mathbb{E}\sum _{i}(X^{T}a_{i})(X^{T}a_{i})+\underbrace{\mathbb{E}(X^{T}a_{j})a_{j}^{T}\sum _{i}(X^{T}a_{i})a_{i}}_{{a_{1},\ldots,a_{k}\text{są ortonormalne}}}=
=\mathbb{E}X^{T}X-\mathbb{E}\sum _{i}(X^{T}a_{i})^{2}-\mathbb{E}\sum _{i}(X^{T}a_{i})^{2}+\mathbb{E}\sum _{j}(X^{T}a_{j})^{2}=
=\mathbb{E}X^{T}X-\mathbb{E}\sum _{{j=1}}^{k}(X^{T}a_{j})^{2}.\quad\text{To wyrażenie chcemy zminimalizować.}

Czyli maksymalizujemy po a_{1},\ldots,a_{k}:

\mathbb{E}\sum _{{j=1}}^{k}(X^{T}a_{j})^{2}=\sum _{{j=1}}^{k}a_{j}^{T}\mathbb{E}(XX^{T})a_{j}=
=\sum _{{j=1}}^{k}a_{j}^{T}[\sum _{{i=1}}^{p}\lambda _{i}v_{i}v_{i}^{T}]a_{j}=\sum _{{j=1}}^{k}\sum _{{i=1}}^{p}\lambda _{i}(v_{i}^{T}a_{j})^{2}=\clubsuit

Przyjrzyjmy się współczynnikom przy \lambda _{i}, są to kwadraty współczynników a_{j} w bazie ortonormalnej v_{i}, więc sumują się do jedynki:

\displaystyle(a_{1}^{T}v_{1})^{2}\quad+\quad(a_{1}^{T}v_{2})^{2}\quad+\ldots+\quad(a_{1}^{T}v_{p})^{2}\quad=1
\displaystyle\ \ \ +\ \ \ \ \quad\quad\ \ \ \ \ \ +\ \ \ \ \ \ \ \ \ \ \ \quad\quad\ \ \ \ \ \ \ +
\displaystyle(a_{2}^{T}v_{1})^{2}\quad+\quad(a_{2}^{T}v_{2})^{2}\quad+\ldots+\quad(a_{2}^{T}v_{p})^{2}\quad=1
\displaystyle\text{ }\qquad\ldots
\displaystyle\ \ \ +\ \ \ \ \quad\quad\ \ \ \ \ \ +\ \ \ \ \ \ \ \ \ \ \ \quad\quad\ \ \ \ \ \ \ +
\displaystyle\underbrace{(a_{k}^{T}v_{1})^{2}}_{{=h_{1}}}\quad+\quad\underbrace{(a_{k}^{T}v_{2})^{2}}_{{=h_{2}}}\quad+\ldots+\quad\underbrace{(a_{k}^{T}v_{p})^{2}}_{{=h_{p}}}\quad=1
\displaystyle\text{ }\qquad\ldots
\displaystyle\ \ \ +\ \ \ \ \quad\quad\ \ \ \ \ \ +\ \ \ \ \ \ \ \ \ \ \ \quad\quad\ \ \ \ \ \ \ +
\displaystyle\underbrace{(a_{p}^{T}v_{1})^{2}}_{{=1}}\quad+\quad\underbrace{(a_{p}^{T}v_{2})^{2}}_{{=1}}\quad+\ldots+\quad\underbrace{(a_{p}^{T}v_{p})^{2}}_{{=1}}\quad=1
\displaystyle\text{w każdej kolumnie można uzupełnić do bazy, wtedy suma}=1;

Czyli otrzymujemy:

\forall i=1,\ldots,p\quad h_{i}\leq 1;\text{ jednocześnie }\sum _{{i=1}}^{k}h_{i}=k;
\clubsuit=\sum _{{i=1}}^{p}\lambda _{i}h_{i}\leq\lambda _{1}+\lambda _{2}+\ldots\lambda _{k}.

Jeśli podstawimy a_{1}=v_{1},a_{2}=v_{2},\ldots,a_{k}=v_{k}, otrzymujemy h_{1}=1,\ldots,h_{k}=1,h_{{k+1}}=0,\ldots,h_{{p}}=0, dla których osiągane jest wyliczone maksimum.

3.3. Przykłady w programie R

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.