WIXLIB

abProf.Fei- ‐FeiLiStanfordVisionLabAnother,veryin- e:hJp://cs229.stanford.edu/secMon/cs229- u/Course/EE263Fei-Fei LiLinear Algebra Review124- ‐Sep- ‐15

Outline Vectorsandmatrices– BasicMatrixOperaMons– SpecialMatrices TransformaMonMatrices– Homogeneouscoordinates– TranslaMon Matrixinverse Matrixrank SingularValueDecomposiMon(SVD)– Useforimagecompression– UseforPrincipalComponentAnalysis(PCA)– ComputeralgorithmFei-Fei LiLinear Algebra Review224- ‐Sep- ‐15

ecommonusesandstandardoperaMonsonthem. Vectorsandmatrices– BasicMatrixOperaMons– SpecialMatrices TransformaMonMatrices– Homogeneouscoordinates– TranslaMon Matrixinverse Matrixrank SingularValueDecomposiMon(SVD)– Useforimagecompression– UseforPrincipalComponentAnalysis(PCA)– ComputeralgorithmFei-Fei LiLinear Algebra Review324- ‐Sep- ‐15

Vector Acolumnvectorwhere ArowvectorwheredenotesthetransposeoperaMonFei-Fei LiLinear Algebra Review424- ‐Sep- ‐15

Vector We’lldefaulttocolumnvectorsinthisclass swhenprogramminginMATLAB e,andwewilluseV’tomean“Vprime”)Fei-Fei LiLinear Algebra Review524- ‐Sep- ‐15

Vectorshavetwomainuses betreatedasavector Vectorscanrepresent paceinterpretaMon,but �distance”cansMllhavevalueFei-Fei LiLinear Algebra Review624- ‐Sep- ‐15

Matrix olumns. If,wesaythatissquare.Fei-Fei LiLinear Algebra Review724- ‐Sep- ‐15

Images s s.Theupperlegcorneris[y,x] (1,1)Fei-Fei LiLinear Algebra Review824- ‐Sep- ‐15

ColorImages sanm nmatrix. ebrightnesses(RGB) Storedasanm n 3matrix Fei-Fei LiLinear Algebra Review924- ‐Sep- ‐15

BasicMatrixOperaMons Wewilldiscuss:– AddiMon– Scaling– Dotproduct– MulMplicaMon– Transpose– Inverse/pseudoinverse– Determinant/traceFei-Fei LiLinear Algebra Review1024- ‐Sep- ‐15

MatrixOperaMons AddiMon– Canonlyaddamatrixwithmatchingdimensions,orascalar. ScalingFei-Fei LiLinear Algebra Review1124- ‐Sep- ‐15

MatrixOperaMons Innerproduct(dotproduct)ofvectors– result– x· yisalso x y Cos(theanglebetweenxandy)Fei-Fei LiLinear Algebra Review1224- ‐Sep- ‐15

MatrixOperaMons Innerproduct(dotproduct)ofvectors– IfBisaunitvector,thenA· BgivesthelengthofAwhichliesinthedirecMonofBFei-Fei LiLinear Algebra Review1324- ‐Sep- ‐15

MatrixOperaMons MulMplicaMon TheproductABis: hatcolumnofB) Manyuses,whichwillbecoveredlaterFei-Fei LiLinear Algebra Review1424- ‐Sep- ‐15

MatrixOperaMons MulMplicaMonexample:– respondingcolumnintherightone.Fei-Fei LiLinear Algebra Review1524- ‐Sep- ‐15

MatrixOperaMons Powers– AAAasA3,etc.– i-Fei LiLinear Algebra Review1624- ‐Sep- ‐15

MatrixOperaMons Transpose–flipmatrix,sorow1becomescolumn1 AusefulidenMty:Fei-Fei LiLinear Algebra Review1724- ‐Sep- ‐15

MatrixOperaMons Determinant–returnsascalar– dbythevectorsintherowsofthematrix– For,– ProperMes:Fei-Fei LiLinear Algebra Review1824- ‐Sep- ‐15

MatrixOperaMons Trace– esinproofs.(Rarelyinthisclassthough.)– ProperMes:Fei-Fei LiLinear Algebra Review1924- ‐Sep- ‐15

SpecialMatrices IdenMtymatrixI– Squarematrix,1’salongdiagonal,0’selsewhere– I· [anothermatrix] [thatmatrix] Diagonalmatrix– e– Adiagonal· [anothermatrix]scalestherowsofthatmatrixFei-Fei LiLinear Algebra Review2024- ‐Sep- ‐15

SpecialMatrices Symmetricmatrix Skew- ‐symmetricmatrix20425Fei-Fei LiLinear Algebra Review212073575024- ‐Sep- ‐15

Outline Vectorsandmatrices– BasicMatrixOperaMons– SpecialMatrices TransformaMonMatrices– Homogeneouscoordinates– trix. Matrixinverse Matrixrank SingularValueDecomposiMon(SVD)– Useforimagecompression– UseforPrincipalComponentAnalysis(PCA)– ComputeralgorithmFei-Fei LiLinear Algebra Review2224- ‐Sep- ‐15

TransformaMon roughmulMplicaMon:x’ Ax lMplicaMonworksoutthisway)Fei-Fei LiLinear Algebra Review2324- ‐Sep- ‐15

RotaMon anew,rotatedcoordinateframe“1”? me’sxaxis,componentindirecMonofyaxis]Fei-Fei LiLinear Algebra Review2424- ‐Sep- ‐15

RotaMon recMonofnewxaxis,componentindirecMonofnewyaxis] Wecandothiseasilywithdotproducts! Newxcoordinateis[originalvector]dot[thenewxaxis] i-Fei LiLinear Algebra Review2524- ‐Sep- ‐15

RotaMon Mon– ]– SomatrixmulMplicaMoncanrotateavectorp:Fei-Fei LiLinear Algebra Review2624- ‐Sep- ‐15

RotaMon hisrotatedleg averotatedthepointright– llusuallythinkoftheminthatsense- ‐- ‐asoperatorstorotatevectorsFei-Fei LiLinear Algebra Review2724- ‐Sep- ‐15

2DRotaMonMatrixFormulaCounter-clockwise rotation by an angle θx ' cos θ x sin θ yy' cos θ y sin θ xP’y’θPyx’x x' cosθ y ' sin θ sin θ x cosθ y P' R PFei-Fei LiLinear Algebra Review2824- ‐Sep- ‐15

TransformaMonMatrices oint:p’ R2R1Sp rtheother,fromrighttole3. Intheexampleabove,theresultis(R2(R1(Sp))) rst,toformasingletransformaMonmatrix:p’ (R2R1S)pFei-Fei LiLinear Algebra Review2924- ‐Sep- ‐15

Homogeneoussystem componentsofavector– .– ButnoMce,wecan’taddaconstant!L Fei-Fei LiLinear Algebra Review3024- ‐Sep- ‐15

Homogeneoussystem– eryvector:– e(notehowthemulMplicaMonworksout,above)– Thisiscalled“homogeneouscoordinates”Fei-Fei LiLinear Algebra Review3124- ‐Sep- ‐15

Homogeneoussystem– d.– omtoo.Fei-Fei LiLinear Algebra Review3224- ‐Sep- ‐15

Homogeneoussystem ng– ingsscaledownastheygetfartherawayinacameraimage– MatrixmulMplicaMoncan’tactuallydivide– MplicaMonFei-Fei LiLinear Algebra Review3324- ‐Sep- ‐15

2DTranslaMonP’PtFei-Fei LiLinear Algebra Review3424- ‐Sep- ‐15

2DTranslaMonusingHomogeneousCoordinatestyPP’tP ( x, y ) ( x, y,1)t (t x , t y ) (t x , t y ,1)tyxFei-Fei LitxP x t x 1 0 t x x P' y t y 0 1 t y y 1 0 0 1 1 I t P T P 0 1 Linear Algebra Review3524- ‐Sep- ‐15

ScalingP’PFei-Fei LiLinear Algebra Review3624- ‐Sep- ‐15

ScalingEquaMonP’syyyP ( x, y) P' (s x x, s y y)PP ( x, y ) ( x, y,1)xP' ( s x x, s y y ) ( s x x, s y y,1)sx x s x x s xP' s y y 0 1 00sy00 x S' 0 0 y P S P 0 1 1 1 SFei-Fei LiLinear Algebra Review3724- ‐Sep- ‐15

Scaling&TranslaMngP’’PP’ S·PP’’ T·P’P’’ T· P’ T· (S· P) T· S· P A· PFei-Fei LiLinear Algebra Review3824- ‐Sep- ‐15

Scaling&TranslaMng 1 0 t x s x 0 0 x P' ' T S P 0 1 t y 0 s y 0 y 0 0 1 0 0 1 1 s x 0 t x x s x x t x x x S t 0 s y t y y s y y t y y y 01 1 0 0 1 1 1 1 AFei-Fei LiLinear Algebra Review3924- ‐Sep- ‐15

TranslaMng&Scaling! Scaling&TranslaMng 1P' ' ' T S P 0 0010t x s xt y 01 0 s xP ' ' ' S T P 0 0 s x 0 0Fei-Fei Li0sy00sy00sy00 x s x0 y 01 1 00 10 01 00sy0010t x x s x x t x t y y s y y t y 1 1 1t x x t y y 1 1 s x t x x s x x s x t x s y t y y s y y s y t y 1 1 1Linear Algebra Review4024- ‐Sep- ‐15

RotaMonP’PFei-Fei LiLinear Algebra Review4124- ‐Sep- ‐15

RotaMonEquaMonsCounter-clockwise rotation by an angle θx ' cos θ x sin θ yy' cos θ y sin θ xP’y’θPyx’x x' cosθ y ' sin θ sin θ x cosθ y P' R PFei-Fei LiLinear Algebra Review4224- ‐Sep- ‐15

RotaMonMatrixProperMes sitedirecMonR RT RT R Idet( R ) 1 lar(a.k.a.orthogonal)unitvectors– (andsoareitscolumns)Fei-Fei LiLinear Algebra Review4324- ‐Sep- ‐15

ProperMes x' cosθ y ' sin θ sin θ x cosθ y A2DrotaMonmatrixis2x2Note: R belongs to the category of normal matricesand satisfies many interesting properties:R RT RT R Idet( R ) 1Fei-Fei LiLinear Algebra Review4424- ‐Sep- ‐15

Scaling RotaMon TranslaMonP’ (TRS)P 1P' T R S P 0 0 cos θ sin θ 0 R 0Fei-Fei Li sin θcos θt S1 00010t x cos θt y sin θ1 0t x s xt y 01 0 x 0 R Sy 1 0 1 0sy0 sin θcos θ00 x 0 y 1 1 0 s x0 01 00sy00 x 0 y 1 1 Thisistheformofthegeneral- ‐purposetransformaMonmatrix x t y 1 1 Linear Algebra Review4524- ‐Sep- ‐15

Outline Vectorsandmatrices– BasicMatrixOperaMons– SpecialMatrices TransformaMonMatrices– Homogeneouscoordinates– TranslaMon Matrixinverse Matrixrank rmaMonmatrixreversesitseffect– Useforimagecompression– UseforPrincipalComponentAnalysis(PCA)– ComputeralgorithmFei-Fei LiLinear Algebra Review4624- ‐Sep- ‐15

Inverse GivenamatrixA,itsinverseA- ‐1isamatrixsuchthatAA- ‐1 A- ‐1A I E.g. Inversedoesnotalwaysexist.IfA- ‐1exists,Aisinver2bleornon- ‐singular.Otherwise,it’ssingular. UsefulidenMMes,formatricesthatareinverMble:Fei-Fei LiLinear Algebra Review4724- ‐Sep- ‐15

MatrixOperaMons Pseudoinverse– SayyouhavethematrixequaMonAX B,whereAandBareknown,andyouwanttosolveforX– ybyit:A- ‐1AX A- ‐1B X A- ‐1B– MATLABcommandwouldbeinv(A)*B– roblemswithcomputerfloaMng- smallandverylargenumberstogether).– Or,yourmatrixmightnotevenhaveaninverse.Fei-Fei LiLinear Algebra Review4824- ‐Sep- ‐15

MatrixOperaMons Pseudoinverse– Fortunately,thereareworkaroundstosolveAX BinthesesituaMons.AndMATLABcandothem!– orXinAX B,bytypingA\B– – MATLABwillreturnthevalueofXwhichsolvestheequaMon IfthereisnoexactsoluMon,itwillreturntheclosestone ei-Fei LiLinear Algebra Review4924- ‐Sep- ‐15

MatrixOperaMons MATLABexample: x A\Bx 1.0000-0.5000Fei-Fei LiLinear Algebra Review5024- ‐Sep- ‐15

Outline Vectorsandmatrices– BasicMatrixOperaMons– SpecialMatrices TransformaMonMatrices– Homogeneouscoordinates– TranslaMon Matrixinverse Matrixrank torto.– Useforimagecompression– UseforPrincipalComponentAnalysis(PCA)– ComputeralgorithmFei-Fei LiLinear Algebra Review5124- ‐Sep- ‐15

Linearindependence Supposewehaveasetofvectorsv1, , vn rsv2 vn,thenv1islinearlydependentontheothervectors.– Monsv2 vn.(E.g.v1 .7 v2- ‐.7 v4) setislinearlyindependent.– Commoncase:asetofvectorsv1, , iculartoeveryothervector(andnon- ‐zero)Fei-Fei LiLinear Algebra Review5224- ‐Sep- ‐15

LinearindependenceLinearlyindependentsetFei-Fei LiNotlinearlyindependentLinear Algebra Review5324- ‐Sep- ‐15

Matrixrank Column/rowrank– Columnrankalwaysequalsrowrank MatrixrankFei-Fei LiLinear Algebra Review5424- ‐Sep- ‐15

Matrixrank onsoftheoutput E.g.ifrankofAis1,thenthetransformaMonp’ Apmapspointsontoaline. ney 2xFei-Fei LiLinear Algebra Review5524- ‐Sep- ‐15

Matrixrank Ifanmxmmatrixisrankm,wesayit’s“fullrank”– Mapsanmx1vectoruniquelytoanothermx1vector– Aninversematrixcanbefound Ifrank m,wesayit’s“singular”– heresultandtellwhattheinputwas– Inversedoesnotexist Inversealsodoesn’texistfornon- ‐squarematricesFei-Fei LiLinear Algebra Review5624- ‐Sep- ‐15

Outline Vectorsandmatrices– BasicMatrixOperaMons– SpecialMatrices TransformaMonMatrices– Homogeneouscoordinates– TranslaMon Matrixinverse Matrixrank dtodiscoverinteresMngstructureinamatrix.– Useforimagecompression– UseforPrincipalComponentAnalysis(PCA)– ComputeralgorithmFei-Fei LiLinear Algebra Review5724- ‐Sep- ‐15

SingularValueDecomposiMon(SVD) atrices . T MATLABcommand:[U,S,V] svd(A)Fei-Fei LiLinear Algebra Review5824- ‐Sep- ‐15

SingularValueDecomposiMon(SVD)TUΣV A .Forexample:Fei-Fei LiLinear Algebra Review5924- ‐Sep- ‐15

SingularValueDecomposiMon(SVD) Beyond2D:– Twillbenxn.– Mon)Fei-Fei LiLinear Algebra Review6024- ‐Sep- ‐15

SingularValueDecomposiMon(SVD) UandVarealwaysrotaMonmatrices.– �eachcolumnisaunitvector. Σisadiagonalmatrix– Thenumberofnonzeroentries rankofA– ThealgorithmalwayssortstheentrieshightolowFei-Fei LiLinear Algebra Review6124- ‐Sep- ‐15

SVDApplicaMons matrices ButSVDofanimagematrixcanalsobeveryuseful retaMonofwhatSVDisdoingFei-Fei LiLinear Algebra Review6224- ‐Sep- ‐15

SVDApplicaMons LookathowthemulMplicaMonworksout,legtoright: Column1ofUgetsscaledbythefirstvaluefromΣ. tribuMontothecolumnsofAFei-Fei LiLinear Algebra Review6324- ‐Sep- ‐15

SVDApplicaMons Eachproductof(columniofU)· (valueifromΣ)· (rowiofVT)producesacomponentofthefinalA.Fei-Fei LiLinear Algebra Review6424- ‐Sep- ‐15

SVDApplicaMons We’rebuildingAasalinearcombinaMonofthecolumnsofU perfectly But,inreal- above)Fei-Fei LiLinear Algebra Review6524- ‐Sep- ‐15

SVDApplicaMons nentsofthedata olumnsoftheoriginalmatrix producethecolumnsofthematrixFei-Fei LiLinear Algebra Review6624- ‐Sep- ‐15

nhasalargeeffectFei-Fei exampleLinear Algebra Review6724- ‐Sep- ‐15