# Module 1 Use vector, matrix, or tensor to represent data. A $$M \times N$$ matrix is a 2D array with M rows and N columns. 1D array - row vector or column vector. Some special matrix: diagonal - only diagonal is non 0. Identiy - diagonal with all 1. Sparse (lots of 0), and symmetric (square, a(i,j) = a(j,i) for all i and j). ### Tensor Array of numbers, 0 dimension- scalar, 1 d - vector, 2d - matirx, 3 or higher is usually a tensor. Matrix operation: element by element vector operations - addition and subtractions. Size must be the same for all operands. Matrix and scalar operation, multiply or divide. Inner/outer product. Let $$A = \[a\_{ij}]$$ be a $$M \times N$$ matrix and $$b = \[b\_n]$$ be a $$N \times 1$$ column vector. Inner product: Let $$x$$ and $$y$$ be $$N \times 1$$ vectors: $$x^Ty = \sum\_{n=1}^Nx\_ny\_n$$ Result in a scalar, both x and y have the same dimension. outer product: $$x\_{M\times 1}y\_{1\times N}^T = \[x\_my\_n]\_{M \times N}$$ A $$M \times N$$ matrix. Results in a matrix. x and y do not need to be same dimension Matrix vector product: $$c = Ab = \[c\_i]*{i=1}^M$$ where $$c\_i = \sum*{j=1}^Na\_{ij}b\_j = a\_i^Tb , 1 \leq i \leq M$$ Matrix matrix product: dimension need to match (column of first and row of second) $$C = A\_{M \times N}B\_{N \times P} \implies c\_{m,p} = \sum\_{n=1}^N a\_{mn}b\_{np}$$ ### Vector Space $$x$$ and $$y$$ are linearly independent if $$ax + by = 0$$ implies $$a=b=0$$. Otherwise, $$y = -(a/b)x$$ meaning $$y$$ is scaled version of x. If $${v\_k}$$are $$K$$linearly independe t vectors, and each $$v\_k$$ is a $$M(\geq K) \times 1$$ vector, then $${v\_k}$$span a K dim subspace in $$\R^M$$. $$x$$ and $$y$$ are orthogonal if $$x^Ty=0$$. if $${v\_k}$$ are mutually orthogonal, they can be a set of basis of the subspace. ### Rank rank of a matrix is the number of linear independent column vectors, or linear independnet row vectors. $$rank(A\_{M \times N}) \leq \min {M, N}$$ A matrix is full rank if its rank equal to the smaller of its column numbers or row numbers. Otherwise, a matrix is rank-deficient. ### Vector Norms L2: $$||x||2 = \sqrt{x^Tx} = (\sum\_{i=1}^N x\_i^2)^{1/2}$$ x is a unit vector if $$||x||\_2 = 1$$ Angle: $$\cos \theta = (x^Ty)/(||x|| \cdot ||y||)$$ L1: $$||x||1 = \sum\_{k=1}^m |x\_k|$$ L infinity: $$||x|||*{\infty} = \max*{1\leq k \leq m} |x\_k|$$ ### Hyperplane A hyperplane in an n-dimensional vector space is a (n-1) dim subspace. In the Euclidean space,a plane is a hyperplane in a 3D space, a line is a hyper plane in a 2D space. Hyperplane function $${ x; x\in \R^n, w^Tx+b = \sum\_{i=1}^n w\_ix\_i + b = 0}$$ A hyperplane partition the space into two half spaces: $${x; x\in \R^n, w^Tx = \sum\_{i=1}^nw\_ix\_i < b}$$ and $${x; x\in \R^n, w^Tx = \sum\_{i=1}^nw\_ix\_i > b}$$ Distance from a point to a hyperplane $$r = -(w^Tx^*+b)/|w| = -g(x^*)/|w|$$ ### SVD $$A\_{M \times N} = U\_{M \times r} \Sigma\_{r\times r}V\_{r\times N}^T = \sum\_{i=1}^r\sigma\_iu\_iv\_i^T$$ Singular value: $$\sigma\_1 \geq \sigma\_2 \geq \dots, \geq \sigma\_r \geq 0$$, $$r\leq \min(M,N)$$ $$U^TU = I\_r$$, $$V^TV=I\_r$$, $$UU\_{M \times M}^T \neq I$$, $$VV\_{N\times N}^T \neq I$$ $$u\_m^Tu\_n = v\_m^Tv\_n = \begin{cases} 1 & m=n \ 0 & m \neq n \end{cases}$$ Number of non-zero singular values = rank of matrix. SVD is the procedure for PCA. ### Eigenvalue Decomposition A symmetric matrix may be decomposed as: $$A\_{N\times N} = V\Lambda V^T = \sum\_{n=1}^N \lambda\_n v\_n v\_n^T$$ $$\Lambda\_{N\times N} = diag{\lambda\_1, \dots, \lambda\_N}$$, $$\lambda\_n$$ eigenvalue $$v\_n$$ eigenvector $$Av = \lambda v \implies (A - \lambda I)v = 0$$ $$VV^T = V^TV=I \implies v\_m^Tv\_n = \begin{cases}1 & m=n \ 0 \&m \neq n \end{cases}$$ A is positive definite iff all eigenvalues are posisitve If A is Hermitian (A^H = complex conjugate transpose of A) then all eigenvalues are real numbers. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://tianyi0216.gitbook.io/blog/course_notes/cs-539-notes/module-1.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.