ReviewofLinearAlgebra

IntroductiontoMatlabMachineLearningGroup

Fall2014OutlineLinearAlgebraBasicsMatrixCalculusSingularValueDecomposition(SVD)EigenvalueDecompositionLow-rankMatrixInversionMatlabessentialsBasicconceptsVectorinRnisanorderedsetofnrealnumbers.e.g.v=(1,6,3,4)isinR4Acolumnvector:Arowvector:m-by-nmatrixisanobjectinRmxnwithmrowsandncolumns,eachentryfilledwitha(typically)realnumber:BasicconceptsVectornorms:Anormofavector||x||isinformallyameasureofthe“length”ofthevector.Commonnorms:L1,L2(Euclidean)LinfinityBasicconceptsVectordot(inner)product:Vectorouterproduct:WewilluselowercaselettersforvectorsTheelementsarereferredbyxi.Ifu?v=0,||u||2!=0,||v||2!=0

uandvareorthogonalIfu?v=0,||u||2=1,||v||2=1

uandvareorthonormalBasicconceptsMatrixproduct:Wewilluseuppercaselettersformatrices.TheelementsarereferredbyAi,j.e.g.Specialmatricesdiagonalupper-triangulartri-diagonallower-triangularI(identitymatrix)BasicconceptsTranspose:Youcanthinkofitas“flipping”therowsandcolumns OR“reflecting”vector/matrixonlinee.g.Linearindependence(u,v)=(0,0),i.e.thecolumnsarelinearlyindependent.Asetofvectorsislinearlyindependentifnoneofthemcanbewrittenasalinearcombinationoftheothers.Vectorsv1,…,vkarelinearlyindependentifc1v1+…+ckvk=0impliesc1=…=ck=0e.g.x3=?2x1+x2SpanofavectorspaceIfallvectorsinavectorspacemaybeexpressedaslinearcombinationsofasetofvectorsv1,…,vk,thenv1,…,vk

spansthespace.Thecardinalityofthissetisthedimensionofthevectorspace.Abasisisamaximalsetoflinearlyindependentvectorsandaminimalsetofspanningvectorsofavectorspace(0,0,1)(0,1,0)(1,0,0)e.g.RankofaMatrixrank(A)(therankofam-by-nmatrixA)isThemaximalnumberoflinearlyindependentcolumns=Themaximalnumberoflinearlyindependentrows=Thedimensionofcol(A)=Thedimensionofrow(A)IfAisnbym,thenrank(A)<=min(m,n)Ifn=rank(A),thenAhasfullrowrankIfm=rank(A),thenAhasfullcolumnrankInverseofamatrix

InverseofasquarematrixA,denotedbyA-1istheuniquematrixs.t.AA-1=A-1A=I(identitymatrix)

IfA-1andB-1exist,then(AB)-1=B-1A-1,(AT)-1=(A-1)T

FororthonormalmatricesFordiagonalmatricesDimensionsByThomasMinka.OldandNewMatrixAlgebraUsefulforStatisticsExamples/

SingularValueDecomposition

(SVD)AnymatrixAcanbedecomposedasA=UDVT,whereDisadiagonalmatrix,withd=rank(A)non-zeroelements ThefistdrowsofUareorthogonalbasisforcol(A)ThefistdrowsofVareorthogonalbasisforrow(A)ApplicationsoftheSVDMatrixPseudoinverseLow-rankmatrixapproximationEigenValueDecompositionAnysymmetricmatrixAcanbedecomposedasA=UDUT,where

Disdiagonal,withd=rank(A)non-zeroelementsThefistdrowsofUareorthogonalbasisforcol(A)=row(A)Re-interpretingAb

Firststretchbalongthedirectionofu1byd1timesThenfurtherstretchitalongthedirectionofu2byd2timesLow-rankMatrixInversionInmanyapplications(e.g.linearregression,Gaussianmodel)weneedtocalculatetheinverseofcovariancematrixXTX(eachrowofn-by-mmatrixXisadatasample)Ifthenumberoffeaturesishuge(e.g.eachsampleisanimage,#samplen<<#featurem)invertingthem-by-mXTXmatrixbecomesanproblemComplexityofmatrixinversionisgenerallyO(n3)Matlabcancomfortablysolvematrixinversionwithm=thousands,butnotmuchmorethanthatLow-rankMatrixInversion

WiththehelpofSVD,weactuallydoNOTneedtoexplicitlyinvertXTXDecomposeX=UDVTThenXTX=VDUTUDVT=VD2VTSinceV(D2)VTV(D2)-1VT=IWeknowthat(XTX)-1=V(D2)-1VTInvertingadiagonalmatrixD2istrivial/

BasicsDerivativesDecompositionsDistributions…MATrixLABoratoryMostlyusedformathematicallibrariesVeryeasytodomatrixmanipulationinMatlabIfthisisyourfirsttimeusingMatlabStronglysuggestyougothroughthe“GettingStarted”partofMatlabhelpManyusefulbasicsyntaxMakingArrays%Asimplearray>>[12345]ans:12345>>[1,2,3,4,5]ans:12345>>v=[1;2;3;4;5]v=12345

>>v’ ans:12345>>1:5ans:12345>>1:2:5ans:135>>5:-2:1ans:531>>rand(3,1)ans:0.03180.27690.0462MakingMatrices%Allthefollowingareequivalent>>[123;456;789]>>[1,2,3;4,5,6;7,8,9]>>[[12;45;78][3;6;9]]>>[[123;456];[789]]ans: 123 456 789MakingMatrices%Creatingallones,zeros,identity,diagonalmatrices>>zeros(rows,cols)>>ones(rows,cols)>>eye(rows)>>diag([123])%CreatingRandommatrices>>rand(rows,cols)%Unif[0,1]>>randn(rows,cols)%N(0,1)%Make3x5withN(1,4)entries>>2*randn(3,5)+1%Getthesize>>[rows,cols]=size(matrix);AccessingElementsUnlikeC-likelanguages,indicesstartfrom1(NOT0)>>A=[123;456;789]ans: 123 456 789%AccessIndividualElements>>A(2,3)ans:6%Access2ndcolumn(:meansallelements)>>A(:,2)ans: 2 5 8AccessingElementsA= 123 456 789Matlabhascolumn-order>>A([1,3,5]) ans:175>>A([1,3],2:end)ans: 23 89>>A(A>5)=-1ans: 123 45-1 -1-1-1>>A(A>5)=-1ans:7869>>[ij]=find(A>5)i=3j= 13 22 33 3MatrixOperationsA= 123 456 789>>A+2*(A/4)ans: 1.50003.00004.5000 6.00007.50009.0000 10.500012.000013.5000>>A./Aans: 111 111 111>>A’>>A*AissameasA^2>>A.*B>>inv(A)>>A/B,A./B,A+B,…%SolvingSystems(A+eye(3))\[1;2;3]%inv(A+eye(3))*[1;2;3]ans: -1.0000 -0.0000 1.0000PlottinginMatlab%LetsplotaGauss