Review of Linear Algebra

Review of Linear Algebra

+ Review of Linear Algebra Introduction to Matlab 10-701/15-781 Machine Learning Fall 2010 Recitation by Leman Akoglu 9/16/10 + Outline Linear Algebra Basics Matrix Calculus Singular

Value Decomposition (SVD) Eigenvalue Low-rank Matlab Decomposition Matrix Inversion essentials Basic concepts Vector in Rn is an ordered set of n real numbers. e.g. v = (1,6,3,4) is in R4 A column vector: A row vector: matrix is an

object in Rmxn with m rows and n columns, each entry filled with a (typically) real number: 1 6 3 4 1 6 3 4 m-by-n 1 2 8

4 78 6 9 3 2 Basic concepts Vector norms: A norm of a vector ||x|| is informally a measure of the length of the vector. Common norms: L1, L2 (Euclidean) Linfinity Basic concepts We will use lower case letters for vectors The elements are referred by xi. Vector dot (inner) product: If uv=0, ||u||2 != 0, ||v||2 != 0 u and v are orthogonal

If uv=0, ||u||2 = 1, ||v||2 = 1 u and v are orthonormal Vector outer product: Basic concepts We will use upper case letters for matrices. The elements are referred by Ai,j. Matrix e.g. product: a11 a12 b11 b12 , B A a21 a22 b21 b22 a11b11 a12b21 a11b12 a12b22

AB a21b11 a22b21 a21b12 a22b22 Special matrices a 0 0 0 b 0 0 0 c a c 0 0 b d

f 0 0 e g i 0 0 h j diagonal a b 0 d 0 0

tri-diagonal 1 0 0 0 1 0 0 0 1 c e f a 0 b c d e

upper-triangular 0 0 lower-triangular f I (identity matrix) Basic concepts Transpose: You can think of it as flipping the rows and columns OR reflecting vector/matrix on line e.g. T a a b b

T a b a c c d b d + Linear independence A set of vectors is linearly independent if none of them can be written as a linear combination of the others. Vectors v1,,vk are linearly | | c1 0if c1v1+ | independent

+ckvk = 0 implies c1==c =0 v1 vk2 v3 c2 0 | c 0 | | 3 e.g. 1 0 0 u 2 3 0 1 3 v 0

(u,v)=(0,0), i.e. the columns are linearly independent. x3 = 2x1 + x2 + Span of a vector space If all vectors in a vector space may be expressed as linear combinations of a set of vectors v1,,vk, then v1,,vk spans the space. The cardinality of this set is the dimension of the vector space. 2 1 0 0

2 2 0 2 1 2 0 2 0 0 1 e.g. (0,0,1) (0,1,0) (1,0,0) A basis is a maximal set of linearly independent vectors and a minimal set of spanning vectors of a vector space +

Rank of a Matrix rank(A) (the rank of a m-by-n matrix A) is The maximal number of linearly independent columns =The maximal number of linearly independent rows =The dimension of col(A) =The dimension of row(A) If A is n by m, then rank(A)<= min(m,n) If n=rank(A), then A has full row rank If m=rank(A), then A has full column rank +

Inverse of a matrix Inverse of a square matrix A, denoted by A-1 is the unique matrix s.t. AA-1 =A-1A=I (identity matrix) If A-1 and B-1 exist, then (AB)-1 = B-1A-1, (AT)-1 = (A-1)T For orthonormal matrices For diagonal matrices + Dimensions

By Thomas Minka. Old and New Matrix Algebra Useful for Statistics + Examples http://matrixcookbook.com/ + Singular Value Decomposition (SVD) Any matrix A can be decomposed as A=UDVT, where D is a diagonal matrix, with d=rank(A) non-zero

elements The fist d rows of U are orthogonal basis for col(A) The fist d rows of V are orthogonal basis for row(A) Applications of the SVD Matrix Pseudoinverse Low-rank matrix approximation + Eigen Value Decomposition Any symmetric matrix A can be decomposed as A=UDUT, where D is diagonal, with d=rank(A) non-zero elements The fist d rows of U are orthogonal basis for col(A)=row(A)

Re-interpreting Ab First stretch b along the direction of u1 by d1 times Then further stretch it along the direction of u2 by d2 times + Low-rank Matrix Inversion In many applications (e.g. linear regression, Gaussian model) we need to calculate the inverse of covariance matrix XTX (each row of nby-m matrix X is a data sample)

If the number of features is huge (e.g. each sample is an image, #sample n<<#feature m) inverting the m-by-m XTX matrix becomes an problem Complexity Matlab of matrix inversion is generally O(n 3) can comfortably solve matrix inversion with m=thousands, but not much more than that + Low-rank Matrix Inversion With the help of SVD, we actually do NOT need to explicitly invert X TX

Decompose X=UDVT Then XTX = VDUTUDVT = VD2VT Since V(D2)VTV(D2)-1VT=I We know that (XTX )-1= V(D2)-1VT Inverting a diagonal matrix D2 is trivial + http://matrixcookbook.com/ Basics

Derivatives Decompositions Distributions + Review of Linear Algebra Introduction to Matlab +

MATrix LABoratory Mostly Very If used for mathematical libraries easy to do matrix manipulation in Matlab this is your first time using Matlab Strongly suggest you go through the Getting Started part of Matlab help Many useful basic syntax + Installing Matlab Matlab licenses are expensive; but free for you! Available for installation by contacting

[email protected] SCS students only Available by download at my.cmu.edu Windows XP SP3+ MacOS X 10.5.5+ ~4GB! + Making Arrays % A simple array >> [1 2 3 4 5] ans: 1 2 3 4 5 >> [1,2,3,4,5] ans: 1 2 3 4 5 >> v = [1;2;3;4;5] v= 1 2 3 4

5 >> v ans: 1 2 3 4 5 >> 1:5 ans: 1 2 3 4 5 >> 1:2:5 ans: 1 3 5 >> 5:-2:1 ans: 5 3 1 >> rand(3,1) ans: 0.0318 0.2769 0.0462 + Making Matrices % All the following are equivalent >> [1 2 3; 4 5 6; 7 8 9] >> [1,2,3; 4,5,6; 7,8,9]

>> [[1 2; 4 5; 7 8] [3; 6; 9]] >> [[1 2 3; 4 5 6]; [7 8 9]] ans: 1 2 3 456 789 + Making Matrices % Creating all ones, zeros, identity, diagonal matrices >> zeros( rows, cols ) >> ones( rows, cols ) >> eye( rows ) >> diag([1 2 3]) % Creating Random matrices >> rand( rows, cols ) % Unif[0,1] >> randn( rows, cols) % N(0, 1) % Make 3x5 with N(1, 4) entries >> 2 * randn(3,5) + 1 % Get the size >> [rows, cols] = size( matrix );

+ Accessing Elements Unlike C-like languages, indices start from 1 (NOT 0) >> A = [1 2 3; 4 5 6; 7 8 9] ans: 1 2 3 456 789 % Access Individual Elements >> A(2,3) ans: 6 % Access 2nd column ( : means all elements) >> A(:,2) ans: 2 5 8 + Accessing Elements A=

123 456 789 Matlab has columnorder >> A([1, 3, 5]) ans: 1 7 5 >> A( [1,3], 2:end ) ans: 2 3 89 >> A( A > 5) = -1 ans: 1 2 3 4 5 -1 -1 -1 -1 >> A( A > 5) = -1 ans: 7 8 6 9 >> [i j] = find(A>5) i= 3 j= 1 3 2

2 3 3 3 + Matrix Operations A= 1 2 3 456 789 >> A + 2 * (A / 4) ans: 1.5000 3.0000 4.5000 6.0000 7.5000 9.0000 10.5000 12.0000 13.5000 >> A ./ A ans: 1 1 1 111 111

>> A >> A*A is same as A^2 >> A.*B >> inv(A) >> A/B, A./B, A+B, % Solving Systems (A+eye(3)) \ [1;2;3] % inv(A+eye(3)) * [1; 2; 3] ans: -1.0000 -0.0000 1.0000 + Plotting in Matlab % Lets plot a Gaussian N(0,1) % Generate 1 million random data points d = randn(1000000,1); % Find the histogram x = min(d):0.1:max(d); c = histc(d, x); p = c / 1000000;

% Plot the pdf plot(x, p); + Other things to know if, for statements scripts and functions Useful operators >, <, >=, <=, ==, &, |, &&, ||, +, -, /, *, ^, , ./, , .*, .^, \ Useful Functions sum, mean, var, not, min, max, find, exists, pause, exp, sqrt, sin, cos, reshape, sort, sortrows, length, size, length, setdiff, ismember, isempty, intersect, plot, hist, title, xlabel, ylabel, legend, rand, randn, zeros, ones, eye, inv, diag, ind2sub, sub2ind, find, logical, repmat, num2str, disp, svd, eig, sparse, clear, clc, help

Recently Viewed Presentations

  • Calculating Average Weekly Wages

    Calculating Average Weekly Wages

    Any fringe benefits that do not continue to be paid by the employer during the disability must be included in AWW calculation - but-Those fringe benefits are only included to the extent that their inclusion will not result in a...
  • Meiosis and Sexual Reproduction

    Meiosis and Sexual Reproduction

    The zygote (the only diploid portion of the life cycle) goes through meiosis immediately after it is formed and makes new haploid cells. In haploid life cycles, meiosis in a diploid zygote results in the formation of the first cell...
  • Theory of Robot Theatre? - Computer Action Team

    Theory of Robot Theatre? - Computer Action Team

    Output symbolsrepresent elementary robot/theatre behaviors such as humanoid robot's arm-up motion or a rotation of the stage of the theatre synchronized with changing lights. ... Proceed recursively and hierarchically, creating higher and higher behaviors in the hierarchy.
  • Objectives - Ncdoi

    Objectives - Ncdoi

    Slide PS-OBJECTIVES (cont'd) Describe four methods by which problems are solved. Outline the critical steps in a problem-solving model. Apply force field analysis as an aid to diagnosing a problem.
  • Abrasion - Woodbridge Township School District

    Abrasion - Woodbridge Township School District

    Abrasion - an injury in which the superficial, or top, layer of skin has been removed due to motion against a rough surface. ... Subdural hematoma— swelling below the brain's outer membrane. Forensic Science II: Physical Trauma, Chapter 7
  • Supervising Classified Employees - Hungerford Law

    Supervising Classified Employees - Hungerford Law

    Your first response? You see an Educational Assistant over-react to a 2nd-grade boy out-of-line and not paying attention. The EA's voice is harsh, the child is berated in front of the class, and the EA pushes the boy back in...
  • Geography 360 Principles of Cartography

    Geography 360 Principles of Cartography

    Arial 굴림 Geog360 Geography 360 Principles of Cartography Outlines: Digital Elevation Model Phenomenon, data, map DEM DEM Slide 6 Earth's topography in different data structure Slide 8 How is DEM generated? TIN TIN How is DEM used? Where do I...
  • 3eme préparatoire

    3eme préparatoire

    aimer - adorer - préférer - détester manger - boire - demander - commander -acheter - avoir - vouloir - prendre. le - la - les - l' le - la - les - l' de / d' du -...