LinearAlgebraPrimerProfessorFei-FeiLiStanfordVisionLab11-Dec-251Another,veryin-depthlinearalgebrareviewfromCS229isavailablehere:http://AndavideodiscussionoflinearalgebrafromEE263ishere(lectures3and4):http://OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm11-Dec-252OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm11-Dec-253Vectorsandmatricesarejustcollectionsoforderednumbersthatrepresentsomething:movementsinspace,scalingfactors,pixelbrightnesses,etc.We’lldefinesomecommonusesandstandardoperationsonthem.VectorAcolumnvectorwhereArowvectorwheredenotesthetransposeoperation11-Dec-254VectorWe’lldefaulttocolumnvectorsinthisclassYou’llwanttokeeptrackoftheorientationofyourvectorswhenprogramminginMATLABYoucantransposeavectorVinMATLABbywritingV’.(Butinclassmaterials,wewillalwaysuseVTtoindicatetranspose,andwewilluseV’tomean“Vprime”)11-Dec-255VectorshavetwomainusesVectorscanrepresentanoffsetin2Dor3DspacePointsarejustvectorsfromtheorigin11-Dec-256Data(pixels,gradientsatanimagekeypoint,etc)canalsobetreatedasavectorSuchvectorsdon’thaveageometricinterpretation,butcalculationslike“distance”canstillhavevalueMatrix

11-Dec-257Images11-Dec-258MATLABrepresentsanimageasamatrixofpixelbrightnessesNotethatmatrixcoordinatesareNOTCartesiancoordinates.Theupperleftcorneris[y,x]=(1,1)=ColorImagesGrayscaleimageshaveonenumberperpixel,andarestoredasanm×nmatrix.Colorimageshave3numbersperpixel–red,green,andbluebrightnessesStoredasanm×n×3matrix11-Dec-259=BasicMatrixOperationsWewilldiscuss:AdditionScalingDotproductMultiplicationTransposeInverse/pseudoinverseDeterminant/trace11-Dec-2510MatrixOperationsAdditionCanonlyaddamatrixwithmatchingdimensions,orascalar.Scaling11-Dec-2511MatrixOperationsInnerproduct(dotproduct)ofvectorsMultiplycorrespondingentriesoftwovectorsandadduptheresultx·yisalso|x||y|Cos(theanglebetweenxandy)11-Dec-2512MatrixOperationsInnerproduct(dotproduct)ofvectorsIfBisaunitvector,thenA·BgivesthelengthofAwhichliesinthedirectionofB11-Dec-2513MatrixOperationsMultiplicationTheproductABis:Eachentryintheresultis(thatrowofA)dotproductwith(thatcolumnofB)Manyuses,whichwillbecoveredlater11-Dec-2514MatrixOperationsMultiplicationexample:11-Dec-2515Eachentryofthematrixproductismadebytakingthedotproductofthecorrespondingrowintheleftmatrix,withthecorrespondingcolumnintherightone.MatrixOperationsPowersByconvention,wecanrefertothematrixproductAAasA2,andAAAasA3,etc.Obviouslyonlysquarematricescanbemultipliedthatway11-Dec-2516MatrixOperationsTranspose–flipmatrix,sorow1becomescolumn1Ausefulidentity:11-Dec-2517DeterminantreturnsascalarRepresentsarea(orvolume)oftheparallelogramdescribedbythevectorsintherowsofthematrixFor,Properties:11-Dec-2518MatrixOperationsTraceInvarianttoalotoftransformations,soit’susedsometimesinproofs.(Rarelyinthisclassthough.)Properties:11-Dec-2519MatrixOperationsSpecialMatricesIdentitymatrixISquarematrix,1’salongdiagonal,0’selsewhereI

?

[anothermatrix]=[thatmatrix]DiagonalmatrixSquarematrixwithnumbersalongdiagonal,0’selsewhereAdiagonal?

[anothermatrix]scalestherowsofthatmatrix11-Dec-2520SpecialMatricesSymmetricmatrixSkew-symmetricmatrix11-Dec-2521OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm11-Dec-2522Matrixmultiplicationcanbeusedtotransformvectors.Amatrixusedinthiswayiscalledatransformationmatrix.TransformationMatricescanbeusedtotransformvectorsinusefulways,throughmultiplication:x’=AxSimplestisscaling:(Verifytoyourselfthatthematrixmultiplicationworksoutthisway)11-Dec-2523RotationHowcanyouconvertavectorrepresentedinframe“0”toanew,rotatedcoordinateframe“1”?Rememberwhatavectoris:[componentindirectionoftheframe’sxaxis,componentindirectionofyaxis]11-Dec-2524RotationSotorotateitwemustproducethisvector:[componentindirectionofnewxaxis,componentindirectionofnewyaxis]Wecandothiseasilywithdotproducts!Newxcoordinateis[originalvector]dot[thenewxaxis]Newycoordinateis[originalvector]dot[thenewyaxis]11-Dec-2525RotationInsight:thisiswhathappensinamatrix*vectormultiplicationResultxcoordinateis[originalvector]dot

[matrixrow1]Somatrixmultiplicationcanrotateavectorp:11-Dec-2526RotationSupposeweexpressapointinacoordinatesystemwhichisrotatedleftIfweusetheresultinthesamecoordinatesystem,wehaverotatedthepointright11-Dec-2527Thus,rotationmatricescanbeusedtorotatevectors.We’llusuallythinkoftheminthatsense--asoperatorstorotatevectors2DRotationMatrixFormulaCounter-clockwiserotationbyanangle

Pxy’P’

x’y11-Dec-2528TransformationMatricesMultipletransformationmatricescanbeusedtotransformapoint:

p’=R2R1SpTheeffectofthisistoapplytheirtransformationsoneaftertheother,fromrighttoleft.Intheexampleabove,theresultis

(R2(R1(Sp)))Theresultisexactlythesameifwemultiplythematricesfirst,toformasingletransformationmatrix:

p’=(R2R1S)p11-Dec-2529HomogeneoussystemIngeneral,amatrixmultiplicationletsuslinearlycombinecomponentsofavectorThisissufficientforscale,rotate,skewtransformations.Butnotice,wecan’taddaconstant!

11-Dec-2530HomogeneoussystemThe(somewhathacky)solution?Sticka“1”attheendofeveryvector:Nowwecanrotate,scale,andskewlikebefore,ANDtranslate(notehowthemultiplicationworksout,above)Thisiscalled“homogeneouscoordinates”11-Dec-2531HomogeneoussystemInhomogeneouscoordinates,themultiplicationworksoutsotherightmostcolumnofthematrixisavectorthatgetsadded.Generally,ahomogeneoustransformationmatrixwillhaveabottomrowof[001],sothattheresulthasa“1”atthebottomtoo.11-Dec-2532HomogeneoussystemOnemorethingwemightwant:todividetheresultbysomethingForexample,wemaywanttodividebyacoordinate,tomakethingsscaledownastheygetfartherawayinacameraimageMatrixmultiplicationcan’tactuallydivideSo,byconvention,inhomogeneouscoordinates,we’lldividetheresultbyitslastcoordinateafterdoingamatrixmultiplication11-Dec-25332DTranslationtPP’11-Dec-253411-Dec-25352DTranslationusingHomogeneousCoordinatesPxytxtyP’ttPScalingPP’11-Dec-2536ScalingEquationPxysxxP’sy

y11-Dec-2537PP’=S?PP’’=T?P’P’’=T?P’=T?(S?P)=T?S?P=A?

PScaling&TranslatingP’’11-Dec-2538Scaling&TranslatingA11-Dec-2539Translating&Scaling

!=Scaling&Translating11-Dec-2540RotationPP’11-Dec-2541RotationEquationsCounter-clockwiserotationbyanangle

Pxy’P’

x’y11-Dec-2542RotationMatrixPropertiesTransposeofarotationmatrixproducesarotationintheoppositedirectionTherowsofarotationmatrixarealwaysmutuallyperpendicular(a.k.a.orthogonal)unitvectors(andsoareitscolumns)11-Dec-2543PropertiesA2Drotationmatrixis2x2Note:Rbelongstothecategoryofnormalmatricesandsatisfiesmanyinterestingproperties:11-Dec-2544Rotation+Scaling+TranslationP’=(TRS)P11-Dec-2545Thisistheformofthegeneral-purposetransformationmatrixOutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm11-Dec-2546TheinverseofatransformationmatrixreversesitseffectGivenamatrixA,itsinverseA-1

isamatrixsuchthatAA-1=A-1A=IE.g.Inversedoesnotalwaysexist.IfA-1exists,Aisinvertibleornon-singular.Otherwise,it’ssingular.Usefulidentities,formatricesthatareinvertible:11-Dec-2547InversePseudoinverseSayyouhavethematrixequationAX=B,whereAandBareknown,andyouwanttosolveforXYoucoulduseMATLABtocalculatetheinverseandpremultiplybyit:A-1AX=A-1B→X=A-1BMATLABcommandwouldbeinv(A)*BButcalculatingtheinverseforlargematricesoftenbringsproblemswithcomputerfloating-pointresolution(becauseitinvolvesworkingwithverysmallandverylargenumberstogether).Or,yourmatrixmightnotevenhaveaninverse.11-Dec-2548MatrixOperationsPseudoinverseFortunately,thereareworkaroundstosolveAX=Binthesesituations.AndMATLABcandothem!Insteadoftakinganinverse,directlyaskMATLABtosolveforXinAX=B,bytypingA\BMATLABwilltryseveralappropriatenumericalmethods(includingthepseudoinverseiftheinversedoesn’texist)MATLABwillreturnthevalueofXwhichsolvestheequationIfthereisnoexactsolution,itwillreturntheclosestoneIftherearemanysolutions,itwillreturnthesmallestone11-Dec-2549MatrixOperationsMATLABexample:11-Dec-2550MatrixOperations>>x=A\Bx=1.0000-0.5000OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm11-Dec-2551Therankofatransformationmatrixtellsyouhowmanydimensionsittransformsavectorto.LinearindependenceSupposewehaveasetofvectorsv1,…,vnIfwecanexpressv1asalinearcombinationoftheothervectorsv2…vn,thenv1islinearlydependentontheothervectors.Thedirectionv1canbeexpressedasacombinationofthedirectionsv2…vn.(E.g.v1=.7

v2-.7

v4)Ifnovectorislinearlydependentontherestoftheset,thesetislinearlyindependent.Commoncase:asetofvectorsv1,…,vnisalwayslinearlyindependentifeachvectorisperpendiculartoeveryothervector(andnon-zero)11-Dec-2552LinearindependenceNotlinearlyindependent11-Dec-2553LinearlyindependentsetMatrixrankColumn/rowrankColumnrankalwaysequalsrowrankMatrixrank11-Dec-2554MatrixrankFortransformationmatrices,theranktellsyouthedimensionsoftheoutputE.g.ifrankofAis1,thenthetransformation

p’=Ap

mapspointsontoaline.Here’samatrixwithrank1:11-Dec-2555Allpointsgetmappedtotheliney=2xMatrixrankIfanmxmmatrixisrankm,wesayit’s“fullrank”Mapsanmx1vectoruniquelytoanothermx1vectorAninversematrixcanbefoundIfrank<m,wesayit’s“singular”Atleastonedimensionisgettingcollapsed.NowaytolookattheresultandtellwhattheinputwasInversedoesnotexistInversealsodoesn’texistfornon-squarematrices11-Dec-2556OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm11-Dec-2557SVDisanalgorithmthatrepresentsanymatrixastheproductof3matrices.Itisusedtodiscoverinterestingstructureinamatrix.SingularValueDecomposition(SVD)Thereareseveralcomputeralgorithmsthatcan“factor”amatrix,representingitastheproductofsomeothermatricesThemostusefuloftheseistheSingularValueDecomposition.RepresentsanymatrixAasaproductofthreematrices:UΣVTMATLABcommand:[U,S,V]=svd(A)11-Dec-2558SingularValueDecomposition(SVD)

UΣVT=AWhereUandVarerotationmatrices,andΣisascalingmatrix.Forexample:11-Dec-2559SingularValueDecomposition(SVD)Beyond2D:Ingeneral,ifAismxn,thenUwillbemxm,Σwillbemxn,andVTwillbenxn.(Notethedimensionsworkouttoproducemxnaftermultiplication)11-Dec-2560SingularValueDecomposition(SVD)UandVarealwaysrotationmatrices.Geometricrotationmaynotbeanapplicableconcept,dependingonthematrix.Sowecallthem“unitary”matrices–eachcolumnisaunitvector.ΣisadiagonalmatrixThenumberofnonzeroentries=rankofAThealgorithmalwayssortstheentrieshightolow11-Dec-2561SVD

ApplicationsWe’vediscussedSVDintermsofgeometrictransformationmatricesButSVDofanimagematrixcanalsobeveryusefulTounderstandthis,we’lllookatalessgeometricinterpretationofwhatSVDisdoing11-Dec-2562SVD

ApplicationsLookathowthemultiplicationworksout,lefttoright:Column1ofUgetsscaledbythefirstvaluefromΣ.Theresultingvectorgetsscaledbyrow1ofVTtoproduceacontributiontothecolumnsofA11-Dec-2563SVD

ApplicationsEachproductof(columniofU)?(valueifromΣ)?(rowiofVT)producesacomponentofthefinalA.11-Dec-2564+=SVD

ApplicationsWe’rebuildingAasalinearcombinationofthecolumnsof

UUsingallcolumnsofU,we’llrebuildtheoriginalmatrixperfectlyBut,inreal-worlddata,oftenwecanjustusethefirstfewcolumnsofUandwe’llgetsomethingclose(e.g.thefirstApartial,above)11-Dec-2565SVD

ApplicationsWecancallthosefirstfewcolumnsof

UthePrincipalComponentsofthedataTheyshowthemajorpatternsthatcanbeaddedtoproducethecolumnsoftheoriginalmatrixTherowsofVTshowhowtheprincipalcomponentsaremixedtoproducethecolumnsofthematrix11-Dec-2566SVD

ApplicationsWecanlookatΣtoseethatthefirstcolumnhasalargeeffect11-Dec-2567whilethesecondcolumnhasamuchsmallereffectinthisexampleSVD

Applications11-Dec-2568Forthisimage,usingonlythefirst10of300principalcomponentsproducesarecognizablereconstructionSo,SVDcanbeusedforimagecompressionPrincipalComponentAnalysisRemember,columnsof

UarethePrincipalComponentsofthedata:themajorpatternsthatcanbeaddedtoproducethecolumnsoftheoriginalmatrixOneuseofthisistoconstructamatrixwhereeachcolumnisaseparatedatasampleRunSVDonthatmatrix,andlookatthefirstfewcolumnsofUtoseepatternsthatarecommonamongthecolumnsThisiscalledPrincipalComponentAnalysis(orPCA)ofthedatasamples11-Dec-2569PrincipalComponentAnalysisOften,rawdatasampleshavealotofredundancyandpatternsPCAcanallowyoutorepresentdatasamplesasweightsontheprincipalcomponents,ratherthanusingtheoriginalrawformofthedataByrepresentingeachsampleasjustthoseweights,youcanrepresentjustthe“meat”ofwhat’sdifferentbetweensamples.Thisminimalrepresentationmakesmachinelearningandotheralgorithmsmuchmoreefficient11-Dec-2570OutlineVectorsandmatricesBasicMatrixOperationsSpecialMatricesTransformationMatricesHomogeneouscoordinatesTranslationMatrixinverseMatrixrankSingularValueDecomposition(SVD)UseforimagecompressionUseforPrincipalComponentAnalysis(PCA)Computeralgorithm11-Dec-2571ComputerscancomputeSVDveryquickly.We’llbrieflydiscussthealgorithm,forthosewhoareinterested.Addendum:HowisSVDcomputed?Forthisclass:tellMATLABtodoit.Usether