Page 1
CS 229 – Machine Learning https://stanford.edu/~shervine VIP Refresher: Linear Algebra and Calculus • outer product: for x ∈ Rm, y ∈ Rn, we have: ( x y · · · x y ) 1 1 1 n Afshine Amidi and Shervine Amidi xyT = .. .. ∈ Rm×n x .y · · · x .y m 1 m n August 8, 2018 r Matrix-vector multiplication – The product of matrix A ∈ Rm×n and vector x ∈ Rn is a vector of size Rn, such that: General notations aT x ∑ r Vector – We note x ∈ Rn a vector with n entries, where x ∈ R is the ith entry: r,1 n ( x ) i Ax = .. = a x ∈ Rn x1 . c,i i 2 T x = . ∈ Rn a x i=1 . r,m x. n where aT are the vector rows and a are the vector columns of A, and x are the entries r,i c,j i r Matrix – We note A ∈ Rm×n a matrix with n rows and m, where A ∈ R is the entry of x. i,j located in the ith row and jth column: r Matrix-matrix multiplication – The product of matrices A ∈ Rm×n and B ∈ Rn×p is a ( ) A1,1 · · · A1,n matrix of size Rn×p, such that: A = .. .. ∈ Rm×n . . aT b · · · aT b ∑ A · · · A r,1 c,1 r,1 c,p n m,1 m,n . . T n×p AB = . . = ac,ibr,i ∈ R Remark: the vector x defined above can be viewed as a n × 1 matrix and is more particularly . . called a column-vector. aT b · · · aT b i=1 r,m c,1 r,m c,p r Identity matrix – The identity matrix I ∈ Rn×n is a square matrix with ones in its diagonal and zero everywhere else: where aT , bT are the vector rows and a , b are the vector columns of A and B respec- r,i r,i c,j c,j 1 0 · · · 0 tively. . . . . .. 0 . . . r Transpose – The transpose of a matrix A ∈ Rm×n, noted AT , is such that its entries are I = . flipped: . . . . . . . . 0 0 · · · 0 1 ∀i,j, AT = A i,j j,i Remark: for all matrices A ∈ Rn×n, we have A × I = I × A = A. Remark: for matrices A,B, we have (AB)T = BT AT . r Diagonal matrix – A diagonal matrix D ∈ Rn×n is a square matrix with nonzero values in its diagonal and zero everywhere else: r Inverse – The inverse of an invertible square matrix A is noted A−1 and is the only matrix d1 0 · · · 0 such that: . . . . .. D = 0 . . . AA−1 = A−1A = I .. . . . . . . . 0 Remark: not all square matrices are invertible. Also, for matrices A,B, we have (AB)−1 = 0 · · · 0 dn B−1A−1 Remark: we also note D as diag(d1,...,dn). r Trace – The trace of a square matrix A, noted tr(A), is the sum of its diagonal entries: Matrix operations ∑n tr(A) = Ai,i r Vector-vector multiplication – There are two types of vector-vector products: i=1 • inner product: for x,y ∈ Rn, we have: Remark: for matrices A,B, we have tr(AT ) = tr(A) and tr(AB) = tr(BA) ∑n r Determinant – The determinant of a square matrix A ∈ Rn×n, noted |A| or det(A) is xT y = x y ∈ R expressed recursively in terms of A , which is the matrix A without its ith row and jth i i \i,\j i=1 column, as follows: Stanford University 1 Fall 2018
Page 2
CS 229 – Machine Learning https://stanford.edu/~shervine ∑n A = AT and ∀x ∈ Rn, xT Ax > 0 det(A) = |A| = (−1)i+jA |A | i,j \i,\j j=1 Remark: similarly, a matrix A is said to be positive definite, and is noted A 0, if it is a PSD matrix which satisfies for all non-zero vector x, xT Ax > 0. Remark: A is invertible if and only if |A| 6= 0. Also, |AB| = |A||B| and |AT | = |A|. r Eigenvalue, eigenvector – Given a matrix A ∈ Rn×n, λ is said to be an eigenvalue of A if there exists a vector z ∈ Rn\{0}, called eigenvector, such that we have: Matrix properties Az = λz r Symmetric decomposition – A given matrix A can be expressed in terms of its symmetric and antisymmetric parts as follows: r Spectral theorem – Let A ∈ Rn×n. If A is symmetric, then A is diagonalizable by a real orthogonal matrix U ∈ Rn×n. By noting Λ = diag(λ ,...,λ ), we have: A + AT A − AT 1 n A = + ∃Λ diagonal, A = UΛUT ︸ ︷︷2 ︸ ︸ ︷︷2 ︸ Symmetric Antisymmetric r Singular-value decomposition – For a given matrix A of dimensions m × n, the singular- value decomposition (SVD) is a factorization technique that guarantees the existence of U m×m r Norm – A norm is a function N : V −→ [0, + ∞[ where V is a vector space, and such that unitary, Σ m × n diagonal and V n × n unitary matrices, such that: for all x,y ∈ V , we have: A = UΣV T • N(x + y) 6 N(x) + N(y) • N(ax) = |a|N(x) for a scalar Matrix calculus • if N(x) = 0, then x = 0 r Gradient – Let f : Rm×n → R be a function and A ∈ Rm×n be a matrix. The gradient of f For x ∈ V , the most commonly used norms are summed up in the table below: with respect to A is a m × n matrix, noted ∇Af(A), such that: ( ) ∂f(A) Norm Notation Definition Use case ∇Af(A) = i,j ∂Ai,j ∑n Manhattan, L1 ||x|| |x | LASSO regularization Remark: the gradient of f is only defined when f is a function that returns a scalar. 1 i i=1 r Hessian – Let f : Rn → R be a function and x ∈ Rn be a vector. The hessian of f with √√ respect to x is a n × n symmetric matrix, noted ∇2f(x), such that: ( ) x √∑n 2 Euclidean, L2 ||x|| √ x2 Ridge regularization 2 ∂ f(x) 2 i ∇xf(x) = i,j ∂xi∂xj i=1 ( )1 Remark: the hessian of f is only defined when f is a function that returns a scalar. ∑n p p-norm, Lp ||x|| xp Hölder inequality r Gradient operations – For matrices A,B,C, the following gradient properties are worth p i having in mind: i=1 ∇ tr(AB) = BT ∇ f(A) = (∇ f(A))T Infinity, L∞ ||x|| max |x | Uniform convergence A AT A ∞ i i ∇ tr(ABAT C) = CAB + CT ABT ∇ |A| = |A|(A−1)T A A r Linearly dependence – A set of vectors is said to be linearly dependent if one of the vectors in the set can be defined as a linear combination of the others. Remark: if no vector can be written this way, then the vectors are said to be linearly independent. r Matrix rank – The rank of a given matrix A is noted rank(A) and is the dimension of the vector space generated by its columns. This is equivalent to the maximum number of linearly independent columns of A. r Positive semi-definite matrix – A matrix A ∈ Rn×n is positive semi-definite (PSD) and is noted A 0 if we have: Stanford University 2 Fall 2018
Comments (0)
No comments yet. Be the first!