Uten å prøve å gi en full primer på PCA, fra et optimaliseringssynspunkt, er den primære objektive funksjonen Rayleighkvotienten. Matrisen som figurerer i kvotienten er (noen multiple av) eksemplet på kovariansmatrisen $$ \ newcommand {\ m} [1] {\ mathbf {# 1}} \ newcommand {\ x} {\ m {x}} \ newcommand {\ S} {\ m {S}} \ newcommand {\ u} {\ m {u}} \ newcommand {\ reals} {\ mathbb {R}} \ newcommand {\ Q} {\ m {Q} } \ newcommand {\ L} {\ boldsymbol {\ Lambda}} \ S = \ frac {1} {n} \ sum_ {i = 1} ^ n \ x_i \ x_i ^ T = \ m {X} ^ T \ m {X} / n $$ der hver $ \ x_i $ er en vektor av $ p $ -funksjoner og $ \ m {X} $ er matrisen slik at $ i $ th-raden er $ \ x_i ^ T $.

PCA søker å løse en sekvens av optimaliseringsproblemer. Den første i sekvensen er det ubegrensede problemet $$ \ begin {array} {ll} \ text {maximize} & \ frac {\ u ^ T \ S \ u} {\ u ^ T \ u} \ ;, \ u \ in \ reals ^ p \ >. \ end {array} $$

Siden $ \ u ^ T \ u = \ | \ u \ | _2 ^ 2 = \ | \ u \ | \ | \ u \ | $, det ovennevnte ubegrensede problemet tilsvarer det begrensede problemet $$ \ begin {array} {ll} \ text {maximize} & \ u ^ T \ S \ u \\\ text {subject to} & \ u ^ T \ u = 1 \ >. \ End {array} $$

Her er matrisealgebraen inn. Siden $ \ S $ er en symmetrisk positiv semidefinit matrise (ved konstruksjon! ) den har en egenverdi-spaltning av formen $$ \ S = \ Q \ L \ Q ^ T \ >, $$ der $ \ Q $ er en ortogonal matrise (så $ \ Q \ Q ^ T = \ m {I } $) og $ \ L $ er en diagonal matrise med ikke-negative oppføringer $ \ lambda_i $ slik at $ \ lambda_1 \ geq \ lambda_2 \ geq \ cdots \ geq \ lambda_p \ geq 0 $.

Derfor, $ \ u ^ T \ S \ u = \ u ^ T \ Q \ L \ Q ^ T \ u = \ m {w} ^ T \ L \ m {w} = \ sum_ {i = 1} ^ p \ lambda_i w_i ^ 2 $. Siden $ \ u $ er begrenset i problemet til å ha en norm på en, er det også $ \ m {w} $ siden $ \ | \ m {w} \ | _2 = \ | \ Q ^ T \ u \ | _2 = \ | \ u \ | _2 = 1 $, i kraft av at $ \ Q $ er ortogonal.

Men hvis vi vil maksimere mengden $ \ sum_ {i = 1} ^ p \ lambda_i w_i ^ 2 $ under begrensningene at $ \ sum_ {i = 1} ^ p w_i ^ 2 = 1 $, så det beste vi kan gjøre er å sette $ \ m {w} = \ m {e} _1 $, det vil si $ w_1 = 1 $ og $ w_i = 0 $ for $ i > 1 $.

Nå som vi sikkerhetskopierer den tilsvarende $ \ u $, som vi først søkte, får vi den $$ \ u ^ \ star = \ Q \ m {e} _1 = \ m {q} _1 $$ hvor $ \ m {q} _1 $ betegner den første kolonnen på $ \ Q $, dvs. egenvektoren som tilsvarer den største egenverdien på $ \ S $. Verdien av den objektive funksjonen blir da også lett å se som $ \ lambda_1 $.

De gjenværende hovedkomponentvektorene blir deretter funnet ved å løse sekvensen (indeksert av $ i $) av optimaliseringsproblemer $$ \ begin {array} {ll} \ text {maximize} & \ u_i ^ T \ S \ u_i \\\ text {subject to} & \ u_i ^ T \ u_i = 1 \\ & \ u_i ^ T \ u_j = 0 \ quad \ forall 1 \ leq j < i \ >. \ End {array} $$ Så problemet er det samme, bortsett fra at vi legger til den ekstra begrensningen at løsningen må være ortogonal til all av de tidligere løsningene i sekvensen. Det er ikke vanskelig å utvide argumentet ovenfor induktivt for å vise at løsningen på $ i $ th-problemet faktisk er $ \ m {q} _i $, $ i $ th egenvektor på $ \ S $.

PCA-løsningen uttrykkes også ofte i form av dekomponering av enestående verdi på $ \ m {X} $. For å se hvorfor, la $ \ m {X} = \ m {U} \ m {D} \ m {V} ^ T $. Deretter $ n \ S = \ m {X} ^ T \ m {X} = \ m {V} \ m {D} ^ 2 \ m {V} ^ T $ og så $ \ m {V} = \ m {Q} $ (strengt tatt, for å signere flips) og $ \ L = \ m {D} ^ 2 / n $.

Hovedkomponentene er funnet ved å projisere $ \ m {X} $ på hovedkomponentvektorene. Fra SVD-formuleringen akkurat gitt, er det lett å se at $$ \ m {X} \ m {Q} = \ m {X} \ m {V} = \ m {U} \ m {D} \ m {V } ^ T \ m {V} = \ m {U} \ m {D} \ >. $$

Enkelheten i representasjon av både hovedkomponentvektorene og selve hovedkomponentene når det gjelder SVD for matriksen av funksjoner er en grunn til at SVD har så fremtredende i noen behandlinger av PCA.

Løsningen som presenteres av kardinal fokuserer på prøvekovariansmatrisen. Et annet utgangspunkt er rekonstruksjonsfeilen av dataene ved hjelp av et q -dimensjonalt hyperplan. Hvis p -dimensjonale datapunktene er $ x_1, \ ldots, x_n $, er målet å løse

$$ \ min _ {\ mu, \ lambda_1, \ ldots, \ lambda_n, \ mathbf {V} _q} \ sum_ {i = 1} ^ n || x_i - \ mu - \ mathbf {V} _q \ lambda_i || ^ 2 $$

for en $ p \ ganger q $ matrise $ \ mathbf {V} _q $ med ortonormale kolonner og $ \ lambda_i \ i \ mathbb {R} ^ q $. Dette gir den beste rangeringen q -rekonstruksjon målt ved den euklidiske normen, og kolonnene i $ \ mathbf {V} _q $ -løsningen er de første q hovedkomponentvektorene .

For fast $ \ mathbf {V} _q $ er løsningen for $ \ mu $ og $ \ lambda_i $ (dette er regresjon) $$ \ mu = \ overline {x} = \ frac { 1} {n} \ sum_ {i = 1} ^ n x_i \ qquad \ lambda_i = \ mathbf {V} _q ^ T (x_i - \ overline {x}) $$

For å lette noteringen kan anta at $ x_i $ har vært sentrert i følgende beregninger. Vi må da minimere

$$ \ sum_ {i = 1} ^ n || x_i - \ mathbf {V} _q \ mathbf {V} _q ^ T x_i || ^ 2 $$

over $ \ mathbf {V} _q $ med ortonormale kolonner. Merk at $ P = \ mathbf {V} _q \ mathbf {V} _q ^ T $ er projeksjonen på q -dimensjonale kolonneplass. Derfor tilsvarer problemet å minimere
$$ \ sum_ {i = 1} ^ n || x_i - P x_i || ^ 2 = \ sum_ {i = 1} ^ n || x_i || ^ 2 - \ sum_ {i = 1} ^ n || Px_i || ^ 2 $$ over rang q anslag $ P $. Det vil si at vi må maksimere $$ \ sum_ {i = 1} ^ n || Px_i || ^ 2 = \ sum_ {i = 1} ^ n x_i ^ TPx_i = \ text {tr } (P \ sum_ {i = 1} ^ n x_i x_i ^ T) = n \ text {tr} (P \ mathbf {S}) $$ over rang q anslag $ P $, hvor $ \ mathbf {S} $ er eksemplet på kovariansmatrisen. Nå $$ \ text {tr} (P \ mathbf {S}) = \ text {tr} (\ mathbf {V} _q ^ T \ mathbf {S} \ mathbf {V} _q) = \ sum_ {i = 1 } ^ q u_i ^ T \ mathbf {S} u_i $$ hvor $ u_1, \ ldots, u_q $ er $ q $ (ortonormale) kolonnene i $ \ mathbf {V} _q $, og argumentene som presenteres i @ kardinalens svar viser at maksimum oppnås ved å ta $ u_i $ s å være $ q $ egenvektorer for $ \ mathbf {S} $ med $ q $ største egenverdier.

Rekonstruksjonsfeilen antyder en rekke nyttige generaliseringer, for eksempel sparsomme hovedkomponenter eller rekonstruksjoner av lavdimensjonale manifolder i stedet for hyperplaner. For detaljer, se Avsnitt 14.5 i Elementene for statistisk læring.

Se NIPALS ( wiki) for en algoritme som ikke eksplisitt bruker en matrisedekomponering. Jeg antar at det er det du mener når du sier at du vil unngå matrisealgebra, siden du virkelig ikke kan unngå matrisealgebra her :)