1 Inner products and norms - Princeton University

1 ORF 523 Lecture 2 Spring 2017, Princeton UniversityInstructor: AhmadiScribe: G. HallThursday, February 9, 2017 When in doubt on the accuracy of these notes, please cross check with the instructor s notes,onaaa. Princeton . edu/ orf523. Any typos should be emailed to we review basic math concepts that you will need throughout the course. Inner products and norms Positive semidefinite matrices Basic differential calculus1 Inner products and Inner DefinitionDefinition 1( Inner product).A function .,. :Rn Rn Ris an Inner product if1. x,x 0, x,x = 0 x= 0(positivity)2. x,y = y,x (symmetry)3.

2 X+y,z = x,z + y,z (additivity)4. rx,y =r x,y for allr R(homogeneity)Homogeneity in the second argument follows: x,ry = ry,x =r y,x =r x,y using properties (2) and (4) and again (2) respectively, and x,y+z = y+z,x = y,x + z,x = x,y + x,z using properties (2), (3) and again (2). Examples The standard Inner product is x,y =xTy= xiyi, x,y Rn. The standard Inner product between matrices is X,Y = Tr(XTY) = i jXijYijwhereX,Y Rm :Here,Rm nis the space of realm nmatrices. Tr(Z) is the trace of a real squarematrixZ, , Tr(Z) = :The matrix Inner product is the same as our original Inner product between two vectorsof lengthmnobtained by stacking the columns of the two matrices.

3 A less classical example inR2is the following: x,y = 5x1y1+ 8x2y2 6x1y2 6x2y1 Properties (2), (3) and (4) are obvious, positivity is less obvious. It can be seen bywriting x,x = 5x21+ 8x22 12x1x2= (x1 2x2)2+ (2x1 2x2)2 0 x,x = 0 x1 2x2= 0 and 2x1 2x2= 0 x1= 0 andx2= Properties of Inner productsDefinition 2(Orthogonality).We say thatxandyare orthogonal if x,y = 1(Cauchy Schwarz).Forx,y Rn| x,y | ||x|| ||y||,where||x||:= x,x is the length ofx(it is also a norm as we will show later on).2 Proof:First, assume that||x||=||y||= 1.||x y||2 0 x y,x y = x,x + y,y 2 x,y 0 x,y , consider anyx,y Rn.

4 If one of the vectors is zero, the inequality is trivially they are both nonzero, then: x||x||,y||y|| 1 x,y ||x|| ||y||.(1)Since (1) holds x,y, replaceywith y: x, y ||x|| || y|| x, y ||x|| ||y||using properties (1) and (2) respectively. DefinitionDefinition 3(Norm).A functionf:Rn Ris a norm (x) 0,f(x) = 0 x= 0(positivity) ( x) =| |f(x), R(homogeneity) (x+y) f(x) +f(y)(triangle inequality)Examples: The 2-norm:||x||= ix2i The 1-norm:||x||1= i|xi| The inf-norm:||x|| = maxi|xi| Thep-norm:||x||p= ( i|xi|p)1/p,p 1 Lemma any Inner product .,. and definef(x) = x,x.

5 Thenfis a :Positivity follows from the homogeneity,f( x) = x, x =| | x,x We prove triangular inequality by contradiction. If it is not satisfied, then x, x+y,x+y > x,x + y,y x+y,x+y > x,x + 2 x,x y,y + y,y 2 x,y >2 x,x y,y which contradicts :Not every norm comes from an Inner Matrix normsMatrix norms are functionsf:Rm n Rthat satisfy the same properties as vector Rm n. Here are a few examples of matrix norms : The Frobenius norm:||A||F= Tr(ATA) = i,jA2i,j The sum-absolute-value norm:||A||sav= i,j|Xi,j| The max-absolute-value norm:||A||mav= maxi,j|Ai,j|Definition 4(Operator norm).

6 An operator (or induced) matrix norm is a norm||.||a,b:Rm n Rdefined as||A||a,b= maxx||Ax|| ||x||b 1,where||.||ais a vector norm onRmand||.||bis a vector norm :When the same vector norm is used in both spaces, we write||A||c= max||Ax|| ||x||c :4 ||A||2= max(ATA), where maxdenotes the largest eigenvalue. ||A||1= maxj i|Aij|, , the maximum column sum. ||A|| = maxi j|Aij|, , the maximum row that not all matrix norms are induced norms . An example is the Frobenius normgiven above as||I|| = 1 for any induced norm, but||I||F= induced norm is submultiplicative, ,||AB|| ||A|| ||B||.

7 Proof:We first show that||Ax|| ||A|| ||x||. Suppose that this is not the case, then||Ax||>||A|| |x|| 1||x||||Ax||>||A|| Ax||x|| >||A||butx||x||is a vector of unit norm. This contradicts the definition of||A||.Now we proceed to prove the claim.||AB||= max||x|| 1||ABx|| max||x|| 1||A|| ||Bx||=||A||max||x|| 1||Bx||=||A|| ||B||. Remark:This is only true for induced norms that use the same vector norm in both spaces. Inthe case where the vector norms are different, submultiplicativity can fail to hold. , the induced norm|| || ,2,and the matricesA=[ 2/2 2/2 2/2 2/2]andB=[1 01 0].

8 In this case,||AB|| ,2>||A|| ,2 ||B|| , , the image of the unit circle byA(notice thatAis a rotation matrix of angle /4)stays within the unit square, and so||A|| ,2 1. Using similar reasoning,||B|| ,2 implies that||A|| ,2||B|| ,2 1. However,||AB|| ,2 2, as||ABx|| = 2 forx= (1,0) of a norm that is not submultiplicative:||A||mav= maxi,j|Ai,j|This can be seen as any submultiplicative norm satisfies||A2|| ||A|| this case,A=(1 11 1)andA2=(2 22 2)So||A2||mav= 2>1 =||A|| :Not all submultiplicative norms are induced norms . An example is the Dual normsDefinition 5(Dual norm).

9 Let||.||be any norm. Its dual norm is defined as||x|| = ||y|| can think of this as the operator norm dual norm is indeed a norm. The first two properties are straightforward to prove. Thetriangle inequality can be shown in the following way:||x+z|| = max||y|| 1(xTy+zTy) max||y|| 1xTy+ max||y|| 1zTy=||x|| +||z|| Examples:1.||x||1 =||x|| 62.||x||2 =||x||23.||x|| =||x|| : The proof of (1) is left as an exercise. Proof of (2): We have||x||2 = ||y||2 implies thatxTy ||x|| ||y|| ||x||andy=x||x||achieves this bound. Proof of (3): We have||x|| = ||y|| 1 Soyopt= sign(x) and the optimal value is||x|| Positive semidefinite matricesWe denote bySn nthe set of all symmetric (real)n DefinitionDefinition matrixA Sn nis positive semidefinite (psd) (notation:A 0) ifxTAx 0, x Rn.

10 Positive definite (pd) (notation:A 0) ifxTAx >0, x Rn, x6= negative semidefinite if Ais psd. (Notation:A 0) negative definite if Ais pd. (Notation:A 0.)Notation:A 0 meansAis psd;A 0 means thatAij 0, for alli, :Whenever we consider a quadratic formxTAx, we can assume without loss ofgenerality that the matrixAis symmetric. The reason behind this is that any matrixAcanbe written asA=(A+AT2)+(A AT2)whereB:=(A+AT2)is the symmetric part ofAandC:=(A AT2)is the anti-symmetricpart ofA. Notice thatxTCx= 0 for anyx :The matrixM=(511 2)is indefinite. To see this, considerx= (1,0)Tandx= (0,1) Eigenvalues of positive semidefinite matricesTheorem eigenvalues of a symmetric real-valued matrixAare :Letx Cnbe a nonzero eigenvector ofAand let Cbe the correspondingeigenvalue; ,Ax= x.