Question? Leave a message!




Linear Algebra for Communications: A gentle introduction

Linear Algebra for Communications: A gentle introduction 39
Linear Algebra for Communications: A gentle introduction Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 1Outline  What is linear algebra, really Vector Matrix Why care  Basis, projections, orthonormal basis  Algebra operations: addition, scaling, multiplication, inverse  Matrices: translation, rotation, reflection, shear, projection etc  Symmetric/Hermitian, positive definite matrices  Decompositions:  Eigendecomposition: eigenvector/value, invariants  Singular Value Decomposition (SVD).  Sneak peeks: how do these concepts relate to communications ideas: fourier transform, least squares, transfer functions, matched filter, solving differential equations etc Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 2What is “Linear” “Algebra”  Properties satisfied by a line through the origin (“onedimensional y case”.  A directed arrow from the origin (v) on the line, when scaled by a cv constant (c) remains on the line v  Two directed arrows (u and v) on the line can be “added” to x create a longer directed arrow (u + v) in the same line.  Wait a minute This is nothing but arithmetic with symbols  “Algebra”: generalization and extension of arithmetic. y  “Linear” operations: addition and scaling. v  Abstract and Generalize u u + v  “Line” ↔ vector space having N dimensions x  “Point” ↔ vector with N components in each of the N dimensions (basis vectors).  Vectors have: “Length” and “Direction”.  Basis vectors: “span” or define the space its dimensionality.  Linear function transforming vectors ↔ matrix.  The function acts on each vector component and scales it  Add up the resulting scaled components to get a new vector  In general: f(cu + dv) = cf(u) + df(v) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 3What is a Vector  Think of a vector as a directed line segment in Ndimensions (has “length” a  and “direction”)   v b  Basic idea: convert geometry in higher  dimensions into algebra  Once you define a “nice” basis along  c  each dimension: x, y, zaxis …  Vector becomes a 1 x N matrix y T  v = a b c  Geometry starts to become linear v algebra on vectors like v x Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 4Examples of Geometry becoming Algebra  Lines are vectors through the origin, scaled and translated: mx + c  Intersection of lines can be modeled as addition of vectors: solution of linear equations.  Linear transformations of vectors can be associated with a matrix A, whose columns represent how each basis vector is transformed.  Ellipses and conic sections: 2 2  ax + 2bxy + cy = d T T T  Let x = x y and A is a symmetric matrix with rows a b and b c T  x Ax = c quadratic form equation for ellipse  This becomes convenient at higher dimensions  Note how a symmetric matrix A naturally arises from such a homogenous multivariate equation… Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 5Scalar vs Matrix Equations  Line equation: y = mx + c  Matrix equation: y = Mx + c  Second order equations: T  x Mx = c T  y = (x Mx)u + Mx T  … involves quadratic forms like x Mx Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 6Vector Addition: A+B A+B v w (x , x ) (y , y ) (x y , x y ) 1 2 1 2 1 1 2 2 A A+B = C (use the headtotail method B to combine vectors) C B A Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 7Scalar Product: av av a(x , x ) (ax ,ax ) 1 2 1 2 av v Change only the length (“scaling”), but keep direction fixed. Sneak peek: matrix operation (Av) can change length, direction and also dimensionality Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 8Vectors: Magnitude (Length) and Phase (direction) T v (x , x , , x ) 1 2 n n 2 v x (Magnitude or “2norm”) i i1 If v1, v is a unit vector Alternate representations: (unit vector = pure direction) Polar coords: (v, ) j Complex numbers: ve y v  “phase” x Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 9T Inner (dot) Product: v.w or w v v  v.w (x , x ).(y , y ) x y x .y w 1 2 1 2 1 1 2 2 The inner product is a SCALAR v.w (x , x ).(y , y ) v  w cos 1 2 1 2 v.w 0 v w T If vectors v, w are “columns”, then dot product is w v Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 10Inner Products, Norms: Signal space  Signals modeled as vectors in a vector space: “signal space”  To form a signal space, first we need to know the inner product between two signals (functions):  Inner (scalar) product: (generalized for functions)   x(t), y(t)  x(t)y (t)dt   = crosscorrelation between x(t) and y(t)  Properties of inner product:  ax(t), y(t) a x(t), y(t)  x(t),ay(t)  a x(t), y(t)  x(t) y(t), z(t) x(t), z(t) y(t), z(t) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 11Signal space …  The distance in signal space is measure by calculating the norm.  What is norm  Norm of a signal (generalization of “length”):  2 x(t) x(t), x(t) x(t) dt E x   = “length” of x(t) ax(t) a x(t)  Norm between two signals: d x(t) y(t) x,y  We refer to the norm between two signals as the Euclidean distance between two signals. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 12Example of distances in signal space  (t) 2 s (a ,a ) 1 11 12 E d 1 s ,z 1  (t) 1 E 3 z (z , z ) 1 2 d E s ,z d 3 2 s ,z 2 s (a ,a ) 3 31 32 s (a ,a ) 2 21 22 Detection in The Euclidean distance between signals z(t) and s(t): AWGN noise: 2 2 d s (t) z(t) (a z ) (a z ) s ,z i i1 1 i2 2 i Pick the “closest” i1,2,3 signal vector Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 13Bases Orthonormal Bases  Basis (or axes): frame of reference vs Basis: a space is totally defined by a set of vectors – any point is a linear combination of the basis OrthoNormal: orthogonal + normal T x1 0 0 x y 0 T Sneak peek: x z 0 y0 1 0 Orthogonal: dot product is zero T y z 0 z0 0 1 Normal: magnitude is one Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 14Projections w/ Orthogonal Basis  Get the component of the vector on each axis:  dotproduct with unit vector on each axis Sneak peek: this is what Fourier transform does Projects a function onto a infinite number of orthonormal basis functions: j j2n (e or e ), and adds the results up (to get an equivalent “representation” in the “frequency” domain). CDMA codes are “orthogonal”, and projecting the composite received signal on each code helps extract the symbol transmitted on that code. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 15Orthogonal Projections: CDMA, Spread Spectrum spread spectrum Baseband Spectrum Radio Spectrum Code B Code A B B A Code A A C C B C B B A B A A C A B Time Sender Receiver Each “code” is an orthogonal basis vector = signals sent are orthogonal Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 16What is a Matrix  A matrix is a set of elements, organized into rows and columns rows a b  columns  c d  Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 17What is a Matrix (Geometrically)  Matrix represents a linear function acting on vectors:  Linearity (a.k.a. superposition): f(au + bv) = af(u) + bf(v) T T  f transforms the unit xaxis basis vector i = 1 0 to a c T T  f transforms the unit yaxis basis vector j = 0 1 to b d T T  f can be represented by the matrix with a c and b d as columns T  Why f(w = mi + nj) = Am n  Column viewpoint: focus on the columns of the matrix a b   c d  T T 0,1 a,c T 1,0 T b,d Linear Functions f : Rotate and/or stretch/shrink the basis vectors Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 18Matrix operating on vectors  Matrix is like a function that transforms the vectors on a plane  Matrix operating on a general point = transforms x and ycomponents  System of linear equations: matrix is just the bunch of coeffs  a b x   x’ = ax + by x'  y’ = cx + dy    c d y y'    Vector (column) viewpoint: T  New basis vector a c is scaled by x, and added to: T  New basis vector b d scaled by y T  i.e. a linear combination of columns of A to get x’ y’  For larger dimensions this “column” or vectoraddition viewpoint is better than the “row” viewpoint involving hyperplanes (that intersect to give a solution of a set of linear equations) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 19Vector Spaces, Dimension, Span  Another way to view Ax = b, is that a solution exists for all vectors b that lie in the “column space” of A,  i.e. b is a linear combination of the basis vectors represented by the columns of A  The columns of A “span” the “column” space  The dimension of the column space is the column rank (or rank) of matrix A.  In general, given a bunch of vectors, they span a vector space.  There are some “algebraic” considerations such as closure, zero etc  The dimension of the space is maximal only when the vectors are linearly independent of the others.  Subspaces are vector spaces with lower dimension that are a subset of the original space  Sneak Peek: linear channel codes (eg: Hamming, Reedsolomon, BCH) can be viewed as kdimensional vector subspaces of a larger Ndimensional space.  kdata bits can therefore be protected with Nk parity bits Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 20Forward Error Correction (FEC): Eg: ReedSolomon RS(N,K) Recover K = K of N RS(N,K) data packets received FEC (NK) Block Size Lossy Network (N) Data = K This is linear algebra in action: design an appropriate kdimensional vector subspace out of an Ndimensional vector space Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 21Matrices: Scaling, Rotation, Identity  Pure scaling, no rotation = “diagonal matrix” (note: x, yaxes could be scaled differently)  Pure rotation, no stretching = “orthogonal matrix” O  Identity (“do nothing”) matrix = unit scaling, no rotation r 0 1 0 r 2 T T 0,1 0,r 2 scaling T T r ,0 1 1,0 cos sin sin cos T sin, cos T 0,1 T cos, sin rotation  T 1,0 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 22Scaling P’ P a.k.a: dilation (r 1), r 0 0 r contraction (r 1) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 23Rotation P P’ cos sin sin cos Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 24Reflections  Reflection can be about any line or point.  Complex Conjugate: reflection about xaxis (i.e. flip the phase  to )  Reflection = two times the projection distance from the line.  Reflection does not affect magnitude Induced Matrix Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 25Orthogonal Projections: Matrices Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 26Shear Transformations  Hold one direction constant and transform (“pull”) the other direction 1 0 0.5 1 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 272D Translation P’ t P P’ P' (x t , y t ) Pt t x y ty P y Shivkumar Kalyanaraman Rensselaer Polytechnic Institute x tx : “shiv rpi” 28Basic Matrix Operations  Addition, Subtraction, Multiplication: creating new matrices (or functions) a b e f a e b f    Just add elements c d g h c g d h  a b e f a e b f    Just subtract elements c d g h c g d h  a b e f ae bg af bh  Multiply each row   by each column c d g h ce dg cf dh  Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 29Multiplication  Is AB = BA Maybe, but maybe not a b e f ae bg ... e f a b ea fc ...    c d g h ... ... g h c d ... ...   Matrix multiplication AB: apply transformation B first, and then again transform using A  Heads up: multiplication is NOT commutative  Note: If A and B both represent either pure “rotation” or “scaling” they can be interchanged (i.e. AB = BA) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 30Multiplication as Composition… Different Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 31Inverse of a Matrix  Identity matrix: AI = A  Inverse exists only for square matrices that are nonsingular 1 0 0   Maps Nd space to another Nd space bijectively   Some matrices have an I 0 1 0 inverse, such that:  1 AA = I  0 0 1  Inversion is tricky:  1 1 1 1 (ABC) = C B A Derived from non commutativity property Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 32Determinant of a Matrix  Used for inversion a b  If det(A) = 0, then A has no inverse  A   Can be found using factorials, pivots, and c d  cofactors  “Volume” interpretation det(A) adbc Sneak Peek: Determinantcriterion for spacetime code design.  Good code exploiting time diversity d b  1 1 A should maximize the minimum   c a ad bc  product distance between codewords.  Coding gain determined by min of determinant over code words. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 33Projection: Using Inner Products (I) T p = a (a x) T a = a a = 1 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 34Projection: Using Inner Products (II) T T p = a (a b)/ (a a) Note: the “error vector” e = bp is orthogonal (perpendicular) to p. T i.e. Inner product: (bp) p = 0 “Orthogonalization” principle: after projection, the difference or “error” is orthogonal to the projection Sneak peek : we use this idea to find a “leastsquares” line that minimizes T the sum of squared errors (i.e. min e e). This is also used in detection under AWGN noise to get the “test statistic”: Idea: project the noisy received vector y onto (complex) transmit vector h: “matched” filter/maxratiocombining (MRC) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 35Schwartz Inequality Matched Filter T  Inner Product (a x) = Product of Norms (i.e. ax)  Projection length = Product of Individual Lengths  This is the Schwartz Inequality  Equality happens when a and x are in the same direction (i.e. cos = 1, when  = 0)  Application: “matched” filter  Received vector y = x + w (zeromean AWGN)  Note: w is infinite dimensional  Project y to the subspace formed by the finite set of transmitted symbols x: y’  y’ is said to be a “sufficient statistic” for detection, i.e. reject the noise dimensions outside the signal space.  This operation is called “matching” to the signal space (projecting)  Now, pick the x which is closest to y’ in distance (ML detection = nearest neighbor) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 36Matched Filter Receiver: Pictorially… Transmitted Signal Received Signal (w/ Noise) Signal + AWGN noise will not reveal the original transmitted sequence. There is a high power of noise relative to the power of the desired signal (i.e., low SNR). If the receiver were to sample this signal at the correct times, the resulting binary message would have a lot of bit errors. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 37Matched Filter (Contd)  Consider the received signal as a vector r, and the transmitted signal vector as s  Matched filter “projects” the r onto signal space spanned by s (“matches” it) Filtered signal can now be safely sampled by the receiver at the correct sampling instants, resulting in a correct interpretation of the binary message Matched filter is the filter that maximizes the signaltonoise ratio it can be shown that it also minimizes the BER: it is a simple projection operation Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 38Matched Filter w/ Repetition Coding hx only spans a 1 1dimensional space h Shivkumar Kalyanaraman Rensselaer Polytechnic Institute Multiply by conjugate = cancel phase : “shiv rpi” 39Symmetric, Hermitian, Positive Definite T  Symmetric: A = A  Symmetric = square matrix  Complex vectors/matrices:  Transpose of a vector or a matrix with complex elements must involve a “conjugate transpose”, i.e. flip the phase as well. 2 H H  For example: x = x x, where x refers to the conjugate transpose of x H  Hermitian (for complex elements): A = A  Like symmetric matrix, but must also do a conjugation of each element (i.e. flip its phase).  i.e. symmetric, except for flipped phase H  Note we will use A instead of A for convenience  Positive definite: symmetric, and its quadratic forms are strictly positive, for nonzero x : T  x Ax 0  Geometry: bowlshaped minima at x = 0 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 40Orthogonal, Unitary Matrices: Rotations  Rotations and Reflections: Orthogonal matrices Q  Pure rotation = Changes vector direction, but not magnitude (no scaling effect)  Retains dimensionality, and is invertible T  Inverse rotation is simply Q  Unitary matrix (U): complex elements, rotation in complex plane H  Inverse: U (note: conjugate transpose).  Sneak peek:  Gaussian noise exhibits “isotropy”, i.e. invariance to direction. So any rotation Q of a gaussian vector (w) yields another gaussian vector Qw.  Circular symmetric (cs) complex gaussian vector w = complex rotation w/ U yields another cs gaussian vector Uw  Sneak peek: The Discrete Fourier Transform (DFT) matrix is both unitary and symmetric.  DFT is nothing but a “complex rotation,” i.e. viewed in a basis that is a rotated version of the original basis.  FFT is just a fast implementation of DFT. It is fundamental in OFDM. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 41T Quadratic forms: x Ax  Linear:  y = mx + c … generalizes to vector equation  y = Mx + c (… y, x, c are vectors, M = matrix) 2  Quadratic expressions in 1 variable: x T  Vector expression: x x (… projection)  Quadratic forms generalize this, by allowing a linear transformation A as well 2 2  Multivariable quadratic expression: x + 2xy + y  Captured by a symmetric matrix A, and quadratic form: T  x Ax  Sneak Peek: Gaussian vector formula has a quadratic form term in its exponent: T 1 exp0.5 (x ) K (x ) 2 2  Similar to 1variable gaussian: exp(0.5 (x ) / ) 1 2  K (inverse covariance matrix) instead of 1/  2  Quadratic form involving (x ) instead of (x ) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 42Rectangular Matrices  Linear system of equations:  Ax = b  More or less equations than necessary.  Not full rank  If full column rank, we can modify equation as: T T  A Ax = A b T  Now (A A) is square, symmetric and invertible. T 1 T  x = (A A) A b … now solves the system of equations  This solution is called the leastsquares solution. Project b onto column space and then solve. T 1 T  (A A) A is sometimes called the “pseudo inverse” T  Sneak Peek: (A A) or (A A) will appear often in communications math (MIMO). They will also appear in SVD (singular value decomposition) T 1 T  The pseudo inverse (A A) A will appear in decorrelator receivers for MIMO  More: http://tutorial.math.lamar.edu/AllBrowsers/2318/LeastSquares.asp  (or Prof. Gilbert Strang’s (MIT) videos on least squares, pseudo inverse): Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 43Invariants of Matrices: Eigenvectors  Consider a NxN matrix (or linear transformation) T  An invariant input x of a function T(x) is nice because it does not change when the function T is applied to it.  i.e. solve this eqn for x: T(x) = x  We allow (positive or negative) scaling, but want invariance w.r.t direction:  T(x) = x  There are multiple solutions to this equation, equal to the rank of the matrix T. If T is “full” rank, then we have a full set of solutions.  These invariant solution vectors x are eigenvectors, and the “characteristic” scaling factors associated w/ each x are eigenvalues. Evectors: T Points on the xaxis unaffected 1 0 T Points on yaxis are flipped 0 1 (but this is equivalent to scaling by 1) Evalues: 1, 1 (also on diagonal of matrix) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 44Eigenvectors (contd)  Eigenvectors are even more interesting because any vector in the domain of T can now be …  … viewed in a new coordinate system formed with the invariant “eigen” directions as a basis.  The operation of T(x) is now decomposable into simpler operations on x,  … which involve projecting x onto the “eigen” directions and applying the characteristic (eigenvalue) scaling along those directions  Sneak Peek:  In fourier transforms (associated w/ linear systems): j  The unit length phasors e are the eigenvectors And the frequency response are the eigenvalues  Why Linear systems are described by differential equations (i.e. d/d and higher orders) j j  Recall d (e )/d = je j  j is the eigenvalue and e the eigenvector (actually, an “eigenfunction”) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 45Eigenvalues Eigenvectors  Eigenvectors (for a square mm matrix S) Example (right) eigenvector eigenvalue  How many eigenvalues are there at most only has a nonzero solution if this is a mth order equation in λ which can have at most m distinct solutions (roots of the characteristic polynomial) – can be complex even though S is Shivkumar Kalyanaraman Rensselaer Polytechnic Institute real. : “shiv rpi” 46Diagonal (Eigen) decomposition – (homework) 2 1  S ;1, 3. Let 1 2  1 2  1 1  1 1   U The eigenvectors and form      1 1  1 1  1/ 21/ 2  1 Recall Inverting, we have U  –1 UU =1. 1/ 2 1/ 2  1 1 1 0 1/ 21/ 2  –1 Then, S=UU =  1 1 0 3 1/ 2 1/ 2  Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 47Example (homework) –1 Let’s divide U (and multiply U ) by 2  1 0  1/ 2 1/ 2 1/ 21/ 2 Then, S=   0 3 1/ 2 1/ 2 1/ 2 1/ 2   1 T Q (Q = Q ) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 48Geometric View: EigenVectors nd  Homogeneous (2 order) multivariable equations:  Represented in matrix (quadratic) form w/ symmetric matrix A: where  Eigenvector decomposition:  Geometry: Principal Axes of Ellipse  Symmetric A = orthogonal evectors  Same idea in fourier transforms  Evectors are “frequencies”  Positive Definite A = +ve real evalues Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 49Why do Eigenvalues/vectors matter  Eigenvectors are invariants of A  Don’t change direction when operated A λt λt  Recall d(e )/dt = λe . λt  e is an invariant function for the linear operator d/dt, with eigenvalue λ  Pair of differential eqns:  dv/dt = 4v – 5u  du/dt = 2u – 3w T  Can be written as: dy/dt = Ay, where y = v u T T  y = v u at time 0 = 8 5 λt  Substitute y = e x into the equation dy/dt = Ay λt λt  λe x = Ae x  This simplifies to the eigenvalue vector equation: Ax = λx  Solutions of multivariable differential equations (the breadandbutter in linear systems) correspond to solutions of linear algebraic eigenvalue equations Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 50Eigen Decomposition  Every square matrix A, with distinct eigenvalues has an eigen decomposition: 1  A = SΛS  … S is a matrix of eigenvectors and  … Λ is a diagonal matrix of distinct eigenvalues Λ = diag( , …  ) 1 N  Follows from definition of eigenvector/eigenvalue:  Ax = x  Collect all these N eigenvectors into a matrix (S): AS = SΛ. or, if S is invertible (if evalues are distinct)… 1  = A = SΛS Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 51Eigen decomposition: Symmetric A  Every square, symmetric matrix A can be decomposed into a product of a T rotation (Q), scaling (Λ) and an inverse rotation (Q ) T  A = QΛQ 1  Idea is similar … A = SΛS  But the eigenvectors of a symmetric matrix A are orthogonal and form an orthogonal basis transformation Q. T  For an orthogonal matrix Q, inverse is just the transpose Q  This is why we love symmetric (or hermitian) matrices: they admit nice decomposition  We love positive definite matrices even more: they are symmetric and all have all eigenvalues strictly positive.  Many linear systems are equivalent to symmetric/hermitian or positive definite transformations. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 52Fourier Methods ≡ Eigen Decomposition  Applying transform techniques is just eigen decomposition  Discrete/Finite case (DFT/FFT):  Circulant matrix C is like convolution. Rows are circularly shifted versions of the first row  C = FΛF where F is the (complex) fourier matrix, which happens to be both unitary and symmetric, and multiplication w/ F is rapid using the FFT.  Applying F = DFT, i.e. transform to frequency domain, i.e. “rotate” the basis to view C in the frequency basis.  Applying Λ is like applying the complex gains/phase changes to each frequency component (basis vector)  Applying F inverts back to the timedomain. (IDFT or IFFT) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 53Fourier /Eigen Decomposition (Continued)  Continuous case:  Any function f(t) can be viewed as a integral (sum) of scaled, timeshifted impulses ∫c()δ(t+) d  h(t) is the response the system gives to an impulse (“impulse response”).  Function’s response is the convolution of the function f(t) w/ impulse response h(t): for linear timeinvariant systems (LTI): f(t)h(t)  Convolution is messy in the timedomain, but becomes a multiplication in the frequency domain: F(s)H(s) Input Output Linear system Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 54Fourier /Eigen Decomposition (Continued)  Transforming an impulse response h(t) to frequency domain gives H(s), the characteristic frequency response. This is a generalization of multiplying by a fourier matrix F  H(s) captures the eigen values (i.e scaling) corresponding to each frequency component s.  Doing convolution now becomes a matter of multiplying eigenvalues for each frequency component;  and then transform back (i.e. like multiplying w/ IDFT matrix F) ikx  The eigenvectors are the orthogonal harmonics, i.e. phasors e ikx  Every harmonic e is an eigen function of every derivative and every finite difference, which are linear operators.  Since dynamic systems can be written as differential/difference equations, eigen transform methods convert them into simple polynomial equations Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 55Applications in Random Vectors/Processes  Covariance matrix K for random vectors X:  Generalization of variance, K is the “covariance” between components ij x and x i j T  K = E(X )(X )  K = K = K is a real, symmetric matrix, with orthogonal ij ji: eigenvectors  K is positive semidefinite. When K is fullrank, it is positive definite.  “White” = no offdiagonal correlations  K is diagonal, and has the same variance in each element of the diagonal  Eg: “Additive White Gaussian Noise” (AWGN)  Whitening filter: eigen decomposition of K + normalization of each eigenvalue to 1 T  (Auto)Correlation matrix R = EXX T  R.vectors X, Y “uncorrelated” = EXY = 0. “orthogonal” Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 56Gaussian Random Vectors  Linear transformations of the standard gaussian vector: t 2  pdf: has covariance matrix K = AA in the quadratic form instead of   When the covariance matrix K is diagonal, i.e., the component random variables are uncorrelated. Uncorrelated + gaussian = independence.  “White” gaussian vector = uncorrelated, or K is diagonal  Whitening filter = convert K to become diagonal (using eigen decomposition)  Note: normally AWGN noise has infinite components, but it is projected onto a finite signal space to become a gaussian vector Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 57Singular Value Decomposition (SVD) Like the eigendecomposition, but for ANY matrix (even rectangular, and even if not full rank) 0 0 : rank of A U (V): orthogonal matrix containing the left (right) singular vectors of A. S: diagonal matrix containing the singular values of A.  ¸  ¸ … ¸  : the entries of . 1 2 Singular values of A (i.e.  ) are related (see next slide) i T T to the eigenvalues of the square/symmetric matrices A A and AA Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 58Singular Value Decomposition For an m n matrix A of rank r there exists a factorization (Singular Value Decomposition = SVD) as follows: T AUV mm mn V is nn T The columns of U are orthogonal eigenvectors of AA . T The columns of V are orthogonal eigenvectors of A A. T T Eigenvalues  …  of AA are the eigenvalues of A A. 1 r  i i Singular values.   diag ... 1 r Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 59SVD, intuition 5 Let the blue circles represent m data points in a 2D Euclidean space. 2nd (right) singular vector Then, the SVD of the mby2 matrix of the data will return … 4 1st (right) singular vector: direction of maximal variance, 3 2nd (right) singular vector: 1st (right) singular vector direction of maximal variance, after removing the projection of the data 2 along the first singular vector. 4.0 4.5 5.0 5.5 6.0 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 60Singular Values 5  2nd (right) 2 singular vector  : measures how much of the data variance 1 4 is explained by the first singular vector.  : measures how much of the data variance 2 is explained by the second singular vector. 3  1 1st (right) singular vector 2 4.0 4.5 5.0 5.5 6.0 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 61SVD for MIMO Channels MIMO (vector) channel: SVD: Rank of H is the number of nonzero singular values t H H = VΛ ΛV Transformed MIMO channel: Change of variables: Diagonalized = Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 62SVD MIMO continued  Represent input in terms of a coordinate system defined by the columns of V (Vx)  Represent output in terms of a coordinate system defined by the columns of U (Uy)  Then the inputoutput relationship is very simple (diagonal, i.e. scaling by singular values)  Once you have “parallel channels” you gain additional degrees of freedom: aka “spatial multiplexing” Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 63SVD example (homework) 11   A 0 1 Let   1 0  Thus m=3, n=2. Its SVD is  0 2 / 6 1/ 3 1 0    1/ 2 1/ 2  1/ 21/ 6 1/ 3 0 3    1/ 21/ 2    1/ 2 1/ 61/ 3 0 0   Note: the singular values arranged in decreasing order. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 64Aside: Singular Value Decomposition, cont’d T A = U V features sig. significant noise noise = objects Can be used for noise rejection (compression): aka lowrank approximation Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 65 significant noiseAside: Lowrank Approximation w/ SVD T AU diag( ,..., ,0,...,0)V k 1 k set smallest rk singular values to zero k k T column notation: sum A u v  k i i i i1 of rank 1 matrices Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 66For more details  Prof. Gilbert Strang’s course videos:  http://ocw.mit.edu/OcwWeb/Mathematics/1806Spring 2005/VideoLectures/index.htm  Esp. the lectures on eigenvalues/eigenvectors, singular value decomposition applications of both. (second half of course)  Online Linear Algebra Tutorials:  http://tutorial.math.lamar.edu/AllBrowsers/2318/2318.asp Shivkumar Kalyanaraman Rensselaer Polytechnic Institute : “shiv rpi” 67
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.ShivJindal
User Type:
Teacher
Country:
India
Uploaded Date:
19-07-2017