1.2 Vectors and Vector Spaces 7 3 a+b 1 -0.5a Figure 1.1 A set S of vectors v1,v2,...,vn in V is said to span some subspace Vo of V if and only if S is a subset of Vo and every vector vo in Vo is linearly dependent on the vectors in S.The set S is said to be a spanning set for Vo.A basis for a vector space V is a linearly independent spanning set for V.The number of vectors in the basis for a vector space is called the dimension of the vector space.If,for example,the number of vectors in the basis is n,we say that the vector space is n-dimensional. An important aspect of the concepts just discussed lies in the representation of any vector inm as a linear combination of the basis vectors.For example,any vector T1 X= T2 T3 in3 can be represented as a linear combination of the basis vectors 0
1.2 Vectors and Vector Spaces 7 Figure 1.1 A set S of vectors v1; v2; : : : ; vn in V is said to span some subspace V0 of V if and only if S is a subset of V0 and every vector v0 in V0 is linearly dependent on the vectors in S. The set S is said to be a spanning set for V0. A basis for a vector space V is a linearly independent spanning set for V . The number of vectors in the basis for a vector space is called the dimension of the vector space. If, for example, the number of vectors in the basis is n, we say that the vector space is n-dimensional. An important aspect of the conceptsjust discussed liesin the representation of any vector in <m as a linear combination of the basis vectors. For example, any vector x = 2 6 4 x1 x2 x3 3 7 5 in <3 can be represented as a linear combination of the basis vectors 2 6 4 1 0 0 3 7 5; 2 6 4 0 1 0 3 7 5, and 2 6 4 0 0 1 3 7 5
8 Chapter 1 A Brief Review of Matrices and Vectors Vector Norms A vector norm on a vector space V is a function that assigns to each vector v in V a nonnegative real number,called the norm of v,denoted by v.By definition,the norm satisfies the following conditions: 1.vl>0forv≠0：=0, 2.llevll =cvll for all scalars c and vectors v,and 3.lu+vl≤lull+lvll. There are numerous norms that are used in practice.In our work,the norm most often used is the so-called 2-norm,which,for a vector x in real m,space is defined as x=i+玲++2] The reader will recognize this expression as the Euclidean distance from the origin to point x,which gives this expression the familiar name of the Euclidean norm.The expression also is recognized as the length of a vector x,with origin at point 0.Based on the multiplication of two column vectors discussed earlier,we see that the norm also can be written as llxl=[xTx]1/2 The well known Cauchy-Schwartz inequality states that xy≤Ibxlly. In words,this result states that the absolute value of the inner product of two vectors never exceeds the product of the norms of the vectors.This result is used in several places in the book.Another well-known result used in the book is the expression xTy cos日=xIyl where 0 is the angle between vectors x and y,from which we have that the inner product of two vectors can be written as xy =llxll llyll cos 6. Thus,the inner product of two vectors can be expressed as a function of the norms of the vectors and the angle between the vectors. From the preceding results we have the definition that two vectors inm are orthogonal if and only if their inner product is zero.Two vectors are orthonormal if,in addition to being orthogonal,the length of each vector is 1.From the concepts just discussed
8 Chapter 1 A Brief Review of Matrices and Vectors Vector Norms A vector norm on a vector space V is a function that assigns to each vector v in V a nonnegative real number, called the norm of v, denoted by kvk. By de®nition, the norm satis®es the following conditions: 1. kvk > 0 for v 6= 0; k0k = 0; 2. kcvk = jcj kvk for all scalars c and vectors v, and 3. ku + vk · kuk + kvk : There are numerous norms that are used in practice. In our work, the norm most often used is the so-called 2-norm, which, for a vector x in real <m, space is de®ned as kxk = £ x 2 1 + x 2 2 + ¢ ¢ ¢ + x 2 m ¤1=2 : The reader will recognize this expression as the Euclidean distance from the origin to point x, which gives this expression the familiar name of the Euclidean norm. The expression also is recognized as the length of a vector x, with origin at point 0. Based on the multiplication of two column vectors discussed earlier, we see that the norm also can be written as kxk = £ x T x ¤1=2 : The well known Cauchy-Schwartz inequality states that ¯ ¯x T y ¯ ¯ · kxk kyk : In words, this result states that the absolute value of the inner product of two vectors never exceeds the product of the norms of the vectors. This result is used in several places in the book. Another well-known result used in the book is the expression cos µ = x T y kxk kyk where µ is the angle between vectors x and y, from which we have that the inner product of two vectors can be written as x T y =kxk kyk cos µ: Thus, the inner product of two vectors can be expressed as a function of the norms of the vectors and the angle between the vectors. From the preceding results we have the de®nition that two vectors in <m are orthogonal if and only if their inner product is zero. Two vectors are orthonormal if, in addition to being orthogonal, the length of each vector is 1. From the concepts just discussed
1.3 Eigenvalues and Eigenvectors 9 we see that an arbitrary vector a is turned into a vector an of unit length by performing the operation an allal.Clearly,then,an=1.A set of vectors is said to be an orthogonal set if every two vectors in the set are orthogonal.A set of vectors is orthonormal if every two vectors in the set are orthonormal Some Important Aspects of Orthogonality Let B =[v1,v2,...,vn}be an orthogonal or orthonormal basis in the sense defined in the previous section.Then,an important result in vector analysis is that any vector v can be represented with respect to the orthogonal basis B as V=a1v1+a2V2+··+anVn where the coefficients are given by vTvi Qi vTvi vTvi llval The key importance of this result is that,if we represent a vector as a linear combination of orthogonal or orthonormal basis vectors,we can determine the coefficients directly from simple inner product computations.It is possible to convert a linearly independent spanning set of vectors into an orthogonal spanning set by using the well-known Gram- Schmidt process.There are numerous programs available that implement the Gram- Schmidt and similar processes,so we will not dwell on the details here. 1.3 Eigenvalues and Eigenvectors Properties ofeigenvalues and eigenvectors are used extensively in Digital Image Process- ing,2nd ed..The following discussion is a brief overview of material fundamental to a clear understanding of the relevant material discussed in the book.We will limit discus- sion to real numbers,but the following results also are applicable to complex numbers. Definition:The eigemalues of a real matrix M are the real numbers A for which there is a nonzero vector e such that Me Ae.The eigemvectors of M are the nonzero vectors e for which there is a real number A such that Me =Ae.If Me Ae for e0,then e is an eigenvector of M associated with eigenvalue A,and vice versa. The eigenvectors and corresponding eigenvalues of M constitute the eigensystem of M.Numerous theoretical and truly practical results in the application of matrices and vectors stem from this beautifully simple definition
1.3 Eigenvalues and Eigenvectors 9 we see that an arbitrary vector a is turned into a vector an of unit length by performing the operation an = a= kak : Clearly, then, kank = 1: A set of vectors is said to be an orthogonal set if every two vectors in the set are orthogonal. A set of vectors is orthonormal if every two vectors in the set are orthonormal. Some Important Aspects of Orthogonality Let B = fv1;v2; : : : ;vng be an orthogonal or orthonormal basis in the sense de®ned in the previous section. Then, an important result in vector analysis is that any vector v can be represented with respect to the orthogonal basis B as v = ®1v1 + ®2v2 + ¢ ¢ ¢ + ®nvn where the coef®cients are given by ®i = v T vi v T i vi = v T vi kvik 2 : The key importance of this result is that, if we represent a vector as a linear combination of orthogonal or orthonormal basis vectors, we can determine the coef®cients directly from simple inner product computations. It is possible to convert a linearly independent spanning set of vectors into an orthogonal spanning set by using the well-known GramSchmidt process. There are numerous programs available that implement the GramSchmidt and similar processes, so we will not dwell on the details here. 1.3 Eigenvalues and Eigenvectors Properties of eigenvalues and eigenvectors are used extensively in Digital Image Processing, 2nd ed.. The following discussion is a brief overview of material fundamental to a clear understanding of the relevant material discussed in the book. We will limit discussion to real numbers, but the following results also are applicable to complex numbers. De®nition: The eigenvalues of a real matrix M are the real numbers ¸ for which there is a nonzero vector e such that Me = ¸e: The eigenvectors of M are the nonzero vectors e for which there is a real number ¸ such that Me = ¸e: If Me = ¸e for e 6= 0, then e is an eigenvector of M associated with eigenvalue ¸, and vice versa. The eigenvectors and corresponding eigenvalues of M constitute the eigensystem of M. Numerous theoretical and truly practical results in the application of matrices and vectors stem from this beautifully simple de®nition
10 Chapter 1 A Brief Review of Matrices and Vectors Example 1.3 Consider the matrix M=[] It is easy to verify that Me1 =Aiel and Me2 A2e2 for A1=1,A2 =2 and e1- 0 and 0 In other words,e is an eigenvector of M with associated eigenvalue A1,and similarly fore2andλ2.☐ The following properties,which we give without proof,are essential background in the use of vectors and matrices in digital image processing.In each case,we assume a real matrix of order m x m although,as stated earlier,these results are equally applicable to complex numbers.We focus on real quantities simply because they play the dominant role in our work. 1.If [1,A2,...,A},q<m,is set of distinct eigenvalues of M,andei is an eigenvec- tor of M with corresponding eigenvalue Ai,i=1,2,...,q,then fe1,e2,...,e is a linearly independent set of vectors.Note an important implication of this property: If an m x m matrix M has m distinct eigenvalues,its eigenvectors will constitute an orthogonal (orthonormal)set,which means that any m-dimensional vector can be expressed as a linear combination of the eigenvectors of M. 2.The numbers along the main diagonal of a diagonal matrix are equal to its eigenval- ues.It is not difficult to show using the definition Me Ae that the eigenvectors can be written by inspection when M is diagonal. 3.A real,symmetric m x m matrix M has a set of m linearly independent eigenvec- tors that may be chosen to form an orthonormal set.This property is of particular importance when dealing with covariance matrices (e.g.,see Section 11.4 and our review of probability)which are real and symmetric. 4.A corollary of Property 3 is that the eigenvalues of an m x m real symmetric matrix are real,and the associated eigenvectors may be chosen to form an orthonormal set of m vectors 5.Suppose that M is a real,symmetric m x m matrix,and that we form a matrix A whose rows are the m orthonormal eigenvectors of M.Then,the product AAT=I because the rows of A are orthonormal vectors.(Recall from the discussion on matrix multiplication that the product of two matrices is formed by the inner product of the rows of one matrix with the column of the other.Since the rows of A and columns of AT are orthonormal,their inner products are either 0 or 1).Thus,we see
10 Chapter 1 A Brief Review of Matrices and Vectors Example 1.3 Consider the matrix M = " 1 0 0 2 # : It is easy to verify that Me1 = ¸1e1 and Me2 = ¸2e2 for ¸1 = 1, ¸2 = 2 and e1 = " 1 0 # and e2 = " 0 1 # : In other words, e1 is an eigenvector of M with associated eigenvalue ¸1, and similarly for e2 and ¸2: ¤ The following properties, which we give without proof, are essential background in the use of vectors and matrices in digital image processing. In each case, we assume a real matrix of order m £ m although, as stated earlier, these results are equally applicable to complex numbers. We focus on real quantities simply because they play the dominant role in our work. 1. If f¸1; ¸2; : : : ; ¸qg; q · m; isset of distinct eigenvalues of M, and ei is an eigenvector of M with corresponding eigenvalue ¸i ; i = 1; 2; : : : ; q; then fe1; e2; : : : ; eq g is a linearly independent set of vectors. Note an important implication of this property: If an m £ m matrix M has m distinct eigenvalues, its eigenvectors will constitute an orthogonal (orthonormal) set, which means that any m-dimensional vector can be expressed as a linear combination of the eigenvectors of M. 2. The numbers along the main diagonal of a diagonal matrix are equal to its eigenvalues. It is not dif®cult to show using the de®nition Me = ¸e that the eigenvectors can be written by inspection when M is diagonal. 3. A real, symmetric m £ m matrix M has a set of m linearly independent eigenvectors that may be chosen to form an orthonormal set. This property is of particular importance when dealing with covariance matrices (e.g., see Section 11.4 and our review of probability) which are real and symmetric. 4. A corollary of Property 3 is that the eigenvalues of an m £ m real symmetric matrix are real, and the associated eigenvectors may be chosen to form an orthonormal set of m vectors. 5. Suppose that M is a real, symmetric m £ m matrix, and that we form a matrix A whose rows are the m orthonormal eigenvectors of M. Then, the product AAT = I because the rows of A are orthonormal vectors. (Recall from the discussion on matrix multiplication that the product of two matrices is formed by the inner product of the rows of one matrix with the column of the other. Since the rows of A and columns of AT are orthonormal, their inner products are either 0 or 1). Thus, we see