CS 236756 - Technion - Intro to Machine Learning

---

Tal Daniel¶

Tutorial 03 - Linear Algebra & SVD¶

---

Agenda

---

• Linear Algebra Refresher
• Eigen Values and Vectors Decomposition
• Singular Value Decomposition (SVD)
• Recommended Videos
• Credits

Useful Resource

---

The Matrix Cookbook

Linear Algebra Refresher

---

Vectors

---

• Geometric object that has both a magnitude and direction
  • $ x = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \end{bmatrix} = (x_1, x_2, ..., x_n)^{T} \in \mathcal{R}^n$
• Magnitude of a vector: $||x|| = \sqrt{x^{T}x} = \sqrt{x_1^2 +x_2^2 +... +x_n^2}$
• Cardinality of a vector - the number of non zero elements

Inner Product Space

---

• A mapping $\langle \cdot, \cdot \rangle : V \times V \rightarrow F$ that satisfies:
  • Conjucate Symmetry: $\langle x, y \rangle = \overline{\langle y, x \rangle} $
  • Linearity in the First Argument:
    • $\langle a \cdot x, y \rangle = a \cdot \langle x, y \rangle$
    • $\langle x + z, y \rangle = \langle x, y \rangle + \langle z, y \rangle$
  • Positive-definiteness:
    • $\langle x, x \rangle \geq 0$
    • $\langle x, x \rangle = 0 \rightarrow x=0$

• Common Inner Products:
  • Real Vector: $\langle x, y \rangle = x^{T} y$
  • Real Matrix: $\langle A, B \rangle = \textit{trace}(AB^{T})$
  • Random Variables: $\langle x, y \rangle = \mathbb{E}[x \cdot y]$

• Properties of Dot Product:
  • Distributiveness:
    • $(a + b)\cdot c = a \cdot c + b \cdot c$
    • $a \cdot (b+c) = a\cdot b + a\cdot c$
  • Linearity: $(\lambda a)\cdot b= a \cdot (\lambda b) = \lambda(a \cdot b)$
  • Symmetry: $a \cdot b= b\cdot a$
  • Non-Negativity: $\forall a \neq 0, a\cdot a >0 , a \cdot a =0 \iff a=0$

Outer Product

---

• Let:
  • $a = (a_1, a_2, ..., a_n)^{T}$
  • $b = (b_1, b_2, ..., b_n)^{T}$
• The outer product $ab^{T}$: $$ ab^{T} = \begin{bmatrix} a_{1} \\ a_{2} \\ \vdots \\ a_{n} \end{bmatrix} [b_1, b_2, ..., b_n] = \begin{pmatrix} a_1 b_1 & a_1 b_2 & \cdots & a_1 b_n \\ a_2 b_1 & a_2 b_2 & \cdots & a_2 b_n \\ \vdots & \vdots & \ddots & \vdots \\ a_n b_1 & a_n b_2 & \cdots & a_n b_n \end{pmatrix} $$

Vector Norms

---

• A norm on a vector sapce $\Omega$ is a function $f: \Omega \rightarrow \mathcal{R}$ with the following properties:
  • Positive Scalability: $f(ax) = |a|f(x)$
  • Triangle Inequality: $f(x+y) \leq f(x) + f(y)$
  • If $f(x) = 0 \rightarrow x = 0$
• $l_1$ norm: $||x||_1 = \sum_{i=1}^n |x_i| $

• $l_2$ norm: $||x||_2 = \sqrt{\sum_{i=1}^n |x_i|^2} $
  • For Vectors: $||x||_2^2 = x^{T}x$
  • $l_2$-distance: $||x -y||_2^2 = (x-y)^{T}(x-y)= ||x||_2^2 -2x^{T}y + ||y||_2^2$
• $l_p$ norm: $||x||_p = (\sum_{i=1}^n |x_i|^p)^{\frac{1}{p}} $
• $l_{\infty}$ norm: $||x||_{\infty} = \max{(|x_1|, |x_2|, ..., |x_n|)} $

Linear Dependency

---

• Given a set of vectors $X =\{x_1, x_2, ..., x_n \}$, a linear combination of vectors is written as:

$$ ax = a_1 x_1 + a_2 x_2 + ... +a_n x_n $$

• $x_i \in X$ is linearly dependent if it can be written as linear combination of $X \setminus \{x_i\}$

Basis

---

• A basis is a linearly independent set of vectors that spans the "whole sapce"
• Every vector in the space can be written as a linear combination of vectors in the basis
  • For example, the standard basis (unit vectors): $\{e_i \in \mathcal{R}^n | e_i =(0, 0, ..., 0, 1,0, ..., 0)^{T}\}$
    • $x^{T} = (3 ,2 ,5)^{T} = 3(1,0,0)^{T}+2(0,1,0)^{T}+5(0,0,1)^{T} = 3e_1^T +2e_2^T +5e_3^T$

• Projection of a vector: $x\cdot e_i = x^T e_i = e_i^T x$
• The basis vectors suffice:
  • Orthogonal - $e_i^T e_j = 0$
  • Normalized - $e_i^T e_i = 1$
  • Orthogonal + Normalized = Orthonormal
  • If $A$ is orthogonal then:
    • $A$ is a square matrix
    • The columns of $A$ are orthonormal vectors
    • $A^TA = AA^T = I \rightarrow A^T= A^{-1}$

• Change of Basis - suppose that we have a basis not necessarily orthonormal $B=\{b_1, b_2, ..., b_n\}, b_i \in \mathcal{R}^m $
  • Vector in the new basis is represented with a matrix-vector multiplication
  • The Identity matrix $I$ maps a vector to itself
  • Basis change can be decomposed to: rotation matrix and scale matrix
  • Using an orthonormal basis means only a rotation around the origin
  • Gram-Schmidt Orthonormaliztion Process: Link

By Lucas V. Barbosa - Own work, Public Domain, Link

Matrix Operations

---

• Addition
  • Commutative: $A + B = B +A$
  • Associative: $(A+B) + C = A + (B+C)$
• Multiplication - PAY ATTENTION TO DIMENSTIONS
  • Associative: $A(BC) = (AB)C$
  • Distributive: $A(B+C) = AB + AC$
  • Non-comutative (!): $AB \neq BA$

• Transpose
  • $(A^{T})_{ij}$
  • $(A^{T})^T = A$
  • $(AB)^{T} = B^{T}A^{T}$
• Inverse - MAKE SURE CONDITIONS APPLY
  • Positive Semi-definite (PSD) - Matrix $M$ is called PSD if for every non-zero column vector $z$, the scalar $z^T M z \geq 0$
  • Every positive definite matrix is invertible and its inverse is also positive definite
  • $(A^{-1})^{-1} = A$
  • $(AB)^{-1} = B^{-1} A^{-1}$
  • $(A^T)^{-1} = A^{-T}$
  • Inverse of 2x2 matrix: see tutorial 1

Matrix Rank

---

• The rank of a matrix is the maximal number of linearly independent columns or rows of a matrix
• $ A \in \mathcal{R}^{m \times n} \rightarrow \textit{rank}(A) \leq \min(m,n)$
• $\textit{rank}(A) = \textit{rank}(A^T)$
• $\textit{rank}(A^T A) = \textit{rank}(A)$
• $\textit{rank}(A + B) \leq \textit{rank}(A) + \textit{rank}(B)$
• $\textit{rank}(AB) \leq \min(\textit{rank}(A), \textit{rank}(B))$
• A is full rank if $\textit{rank}(A) = \min(m,n)$
• Singular Matrix - has dependent rows (and at least one zero eigen-value)

Range & Nullspace

---

• Range (of a matrix) - the span of the columns of the matrix, denoted by the set: $$\mathcal{R}(A) = \{y|y= Ax\} $$
• Nullspace (of a matrix) - the set of vectors that when multiplied by the matrix result in 0, given by the set: $$\mathcal{N}(A) = \{x|Ax=0\} $$

Determinant

---

Let $A = \begin{pmatrix}x_1 & y_1 & z_1 \\ x_2 & y_2 & z_2 \\ x_3 & y_3 & z_3 \end{pmatrix} $, a square matrix, then: $$det(A) = |A| = \begin{vmatrix} x_1 & y_1 & z_1 \\ x_2 & y_2 & z_2 \\ x_3 & y_3 & z_3 \end{vmatrix} = x_1 \begin{vmatrix} y_1 & z_2 \\ y_3 & z_3 \end{vmatrix} -x_2 \begin{vmatrix} y_1 & z_1 \\ y_3 & z_3 \end{vmatrix} +x_3\begin{vmatrix} y_1 & z_1\\ y_2 & z_2 \end{vmatrix}$$
$$ = x_1 (y_2z_3 - z_2 y_3) -x_2(y_1z_3 - z_1y_3) +x_3(y_1z_2 - z_1 y_2) $$

• $det(A) = 0 \iff A$ is singular (at least one eigen-value is zero)
• If $A$ is diagonal, then $det(A)$ is the prodcut of the diagonal elements (the eigen-values)
• $det(AB) = det(A)det(B)$
• $det(A^{-1}) = det(A)^{-1}$
• $det(\lambda A) = \lambda^n det(A)$

Solve Linear Equation Analytically

---

• Definitions:
  • $A \in \mathcal{R}^{n \times n}$
  • $x, b \in \mathcal{R}^{n \times 1}$
• The problem: find the solution of $Ax = b$
• Solution: if $A$ is PSD (and thus invertible), then $x = A^{-1} b$
• What if $A \in \mathcal{R}^{m \times n}$, $x \in \mathcal{R}^{n \times 1}$, $b \in \mathcal{R}^{m \times 1}$ ?
  • $A$ is no longer invertible!
• The problem redefined: find $x$ that minimzes the distance from $Ax$ to $b$, or more formally: $$ \underset{x}{\mathrm{argmin}} ||Ax - b ||_2^2$$ (also called least-squares solution)

Reminder (Tutorial 01) - Vector & Matrix Derivatives

---

• $\nabla_x Ax = A^{T}$
• $\nabla_x x^{T} A x = (A + A^{T}) x$
• $\frac{\partial}{\partial A} \ln |A| = A^{-T}$
• $\frac{\partial}{\partial A} Tr[AB] = B^{T}$

Exercise 1 - Least-Squares Solution

---

Given $A \in \mathcal{R}^{m \times n}$, $x \in \mathcal{R}^{n \times 1}$, $b \in \mathcal{R}^{m \times 1}$

Find $x$ that minimizes the distance from $Ax$ to $b$, or more formally: $$ \underset{x}{\mathrm{argmin}} ||Ax - b ||_2^2$$

Solution 1

---

$$ ||Ax - b ||_2^2 = (Ax-b)^T (Ax-b) = x^TA^TAx -x^TA^Tb-b^TAx +b^Tb $$$$\frac{\partial ||Ax - b ||_2^2}{\partial x} = 2A^TAx-2A^Tb = 0 \rightarrow x = (A^TA)^{-1}A^Tb $$

Solve Linear Equation Non-Analytically

---

Eigenvalues and Eigenvectors

---

• Definition: Matrix $A$ with Eigenvalue $\lambda \in \mathbb{C}$ and Eigenvector $x \in \mathbb{C}^n$ if $$Ax=\lambda x, x \neq 0 $$
• Finding eigenvalues and eigenvectors
  • Find eigenvalues by finding the roots of the polynomial generated by: $$det(\lambda I -A) = |\lambda I -A| =0 $$
  • For each eigenvalue $\lambda$, find its corresponding eigenvector $x$ by solving: $$ Ax = \lambda x$$

• Example: $M = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} \rightarrow |\lambda I -M| = \begin{vmatrix} 2 - \lambda & 1 \\ 1 & 2 - \lambda \end{vmatrix} = 3 - 4 \lambda + \lambda^2 \rightarrow \lambda_{1,2} = 1, 3 \rightarrow x_{\lambda = 1}= \begin{bmatrix} 1 \\ -1 \end{bmatrix} , x_{\lambda=3} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$

• Eigenvalues Properties

  • $det(\Lambda) = |\Lambda| = \prod_{i=1}^n \lambda_i$
  • $\textit{rank}(A) = \sum_{i=1}^n \mathbb{1}_{\lambda_i \neq 0}$
  • Eigenvalues of a diagonal matrix are the diagonal entries
  • A (square) matrix is said to be diagonalizable if it can be rewritten as: $A = X \Lambda X^{-1}$

• Eigenvalues of Symmetric Matrices:

  • Eigenvalues are real
  • Eigenvectors of real symmetric matrices are orthonormal

Eigen Decomposition

---

• Eigen-decomposition (also spectral decomposition) - factorization of a matrix into a canonical form, that is, the matrix is represented in terms of its eigenvalues and eigenvectors.
• Only diagonalizable matrices can be factorized
• Formally:
  • Denote $\Lambda$ as a matrix with eigenvalues on the diagonal
  • Denote $Q$ as a matrix where the columns are the eigenvectors
  • Let $A$ be a square $n \times n$ matrix with $N$ linearly independent columns. Then $A$ can factorized as: $$A = Q \Lambda Q^{-1} $$

What If A Is Non-Square?

Singular Value Decomposition (SVD)

---

• In linear algebra, the singular-value decomposition (SVD) is a factorization of a real or complex matrix. It is the generalization of the eigendecomposition of a positive semidefinite normal matrix (for example, a symmetric matrix with positive eigenvalues) to any $ m\times n$ matrix via an extension of the polar decomposition.
• Definition: $$ A_{[m \times n]} = U_{[m \times r]} \Sigma_{[r \times r]} (V_{[n \times r]})^T $$

• $A$ - Input Data matrix
  • $m \times n$ matrix (e.g. $m$ documents and $n$ terms that can appear in each document)
• $U$ - Left Singular vectors
  • $m \times r$ matrix (e.g. $m$ documents and $r$ concepts)
  • $U = eig(AA^T)$

• $\Sigma$ - Singular values
  • $r \times r$ diagonal matrix (strength of each 'concept')
  • $r$ represnts the rank of matrix $A$
  • $\Sigma = diag\left(\sqrt{eigenvalues(A^TA)}\right)$
  • Singular Values definition: the singular values of a matrix $X \in \mathbb{R}^{M \times N}$ are the square root of the eigenvalues of the matrix $X^TX \in \mathbb{R}^{N \times N}$. If $X \in \mathbb{R}^{N \times N}$ already, then the singular values are the eigenvalues.
• $V$ - Right Singular vectors
  • $n \times r$ matrix (e.g. $n$ terms and $r$ concepts)
  • $V = eig(A^TA)$

• Illustration:

  First, we see the unit disc in blue together with the two canonical unit vectors. We then see the action of M, which distorts the disk to an ellipse. The SVD decomposes M into three simple transformations: an initial rotation $V^{*}$, a scaling $\Sigma$ along the coordinate axes, and a final rotation $U$. The lengths $\sigma_1$ and $\sigma_2$ of the semi-axes of the ellipse are the singular values of $M$, namely $\Sigma_{1,1}$ and $\Sigma_{2,2}$.

• By Kieff - Own work, Public Domain, Link

• Another way to look at SVD: $$ A \approx U\Sigma V^T = \sum_i \sigma_i u_i \circ v_i^T $$

• SVD Properties
  • It is always possible to decompose a real matrix $A$ to $A = U\Sigma V^T$ where
    • $U, \Sigma, V$ are uniuqe
    • $U, V$ are column orthonormal
      • $U^T U = I, V^T V = I$
    • $\Sigma$ is diagonal
      • Entries (the singular values) are positive and sorted in decreasing order ($\sigma_1 \geq \sigma_2 \geq ... \geq 0$)
  • Proof of uniqueness

• Image Source

SVD Example - Users-to-Movies

---

We are given a dataset of user's rating (1 to 5) for several movies of 3 genres (concepts) and we wish to use SVD to decompose to the following components:

• User-to-Concept - which genres the users prefer: $U$ matrix
• Concepts - what is the strength of each genre in the dataset: $\Sigma$ - strength of each concept (the singular values)
• Movie-to-Concept - for each movie, what genres are the most dominant: $V$ matrix

Recommended Videos

---

Warning!

• These videos do not replace the lectures and tutorials.
• Please use these to get a better understanding of the material, and not as an alternative to the written material.

Video By Subject¶

• Basic Linear Algebra - Mathematics for Machine Learning full Course || Linear Algebra || Part-1
• SVD - Lecture 47 — Singular Value Decomposition | Stanford University

Credits

---

• Inspired by slides by Elad Osherov and slides from MMDS
• Icons from Icon8.com - https://icons8.com
• Datasets from Kaggle - https://www.kaggle.com/