Pattern Recognition and Machine Learning

Exercise 12.1

Section12.2.2

AppendixC

12.1.PrincipalComponentAnalysis 563

amongstallpossibledirectionsorthogonaltothosealreadyconsidered.Ifwecon-

siderthegeneralcaseofanM-dimensionalprojectionspace,theoptimallinearpro-

jectionforwhichthevarianceoftheprojecteddataismaximizedisnowdefinedby

theMeigenvectorsU1,..., UMofthedatacovariancematrixS correspondingtothe

Mlargesteigenvalues>'1,... ,AM.Thisis easilyshownusingproofbyinduction.

Tosummarize,principalcomponentanalysisinvolvesevaluatingthemeanx

andthecovariancematrixSofthedatasetandthenfindingtheM eigenvectorsofS

correspondingtotheMlargesteigenvalues.Algorithmsforfindingeigenvectorsand

eigenvalues,aswellasadditionaltheoremsrelatedtoeigenvectordecomposition,

canbefoundinGolubandVanLoan(1996). Notethatthecomputationalcostof

computingthefulleigenvectordecompositionfora matrixofsizeDxDisO(D3).

IfweplantoprojectourdataontothefirstM principalcomponents,thenweonly

needtofindthefirstMeigenvaluesandeigenvectors.Thiscanbedonewithmore

efficienttechniques,suchasthepowermethod(GolubandVanLoan,1996),that

scalelikeO(MD^2 ),oralternativelywecanmakeuseoftheEMalgorithm.

12.1.2 Minimum-error formulation

WenowdiscussanalternativeformulationofpeAbasedonprojectionerror

minimization.Todothis,weintroducea completeorthonormalsetofD-dimensional

basisvectors{Ui}wherei= 1,...,Dthatsatisfy

(12.7)

Becausethisbasisis complete,eachdatapointcanberepresentedexactlybya linear

combinationofthebasisvectors

D

Xn= Laniui

i=l

(12.8)

wherethecoefficientsaniwillbedifferentfordifferentdatapoints. Thissimply

correspondstoa rotationofthecoordinatesystemtoa newsystemdefinedbythe

{Ui},andtheoriginalDcomponents{Xnl'...,XnD}arereplacedbyanequivalent

set{anl'...,anD}.TakingtheinnerproductwithUj,andmakinguseoftheor-

thonormalityproperty,weobtainanj= x;Uj,andsowithoutlossofgeneralitywe

canwrite

D

Xn= L (X~Ui)Ui·

i=l

(12.9)

(12.10)

Ourgoal,however,istoapproximatethisdatapointusinga representationin-

volvinga restrictednumberM <Dofvariablescorrespondingtoa projectiononto

a lower-dimensionalsubspace. TheM-dimensionallinearsubspacecanberepre-

sented,withoutlossofgenerality,bythefirstM ofthebasisvectors,andsowe

approximateeachdatapointXnby

M D

xn=L ZniUi+ L biUi

i=l i=M+l