ml(Math-2)

Relevance in Machine Learning

• Linear transformations are used in both abstract mathematics, as well as computer science. Linear transformations within calculus are used as way of tracking change, also known as derivatives.
• Linear transformations are often used in machine learning applications. They are useful in the modeling of 2D and 3D animation, where an objects size and shape needs to be transformed from one viewing angle to the next.
• An object can be rotated and scaled withing a space using a type of linear transformation known as geometric transformations.
• Linear transformations also used to project the data from one spce to another. Sometimes, a dataset is not linearly seperable in its original space, therefore we need to transform (project) the data in another space with different dimensions. This can be done either using linear transformations or kernels.

Linear Transformations

• Let V and W be vectors spaces over a field F of dimensions n and m, respectively.
• A linear transformation is mapping $T:V^{(}n)\to W^{(}m)(F)$ such that:
  1. $T(v_1+v_2)=T(v_1)+T(v_2)\forall v_1\&v_2\in V$
  2. $T(\alpha V)=\alpha T(v)\forall v\in V\&\alpha \in F$

Example

• $T:{\mathbb{R}}^2\to {\mathbb{R}}^2$ such that $T(x_1,x_2)=(x_1,x_1+x_2)$
• $T:{\mathbb{R}}^3\to {\mathbb{R}}^2$ such that $T(x_1,x_2,x_3)=(x_2,x_1,0)$

Remarks:

• A linear Map from T to itself is called a linear operator.
• A linear map from a vector space to underlying field is called a linear functional.

The Matrix Representation of a Linear Transformation

Suppose $V(F)$ and $W(F)$ are finite dimensional vector spaces with bases {v*{1}, v*{2}, …, v*{n}} and {w*{1}, w*{2}, …, w*{m}}, respectively. Let $T:V\to W$ be a linear map. Then the matrix of T,with enteries $a_{ij}\in F$, is defined by:

$$T(v_j)=a_{1j}{w}_1+a_{2j}{w}_2+...+a_{mj}{w}_m$$

for j = 1,2,3,…,n.

It shows that the $j^{th}$ column of the matrix A of linear map T consists of the coordinates of $T(v_j)$ in the chosen basis of W. Conversely, every matrix $A\in {\mathbb{R}}^{m\times n}$ induced a linear map $T:{\mathbb{R}}^n\to {\mathbb{R}}^m$ given by $T(v)=Av$.

Example

• Consider a linear map $T:{\mathbb{R}}^2\to {\mathbb{R}}^2$ such that $T(x_1,x_2)=(2x_1-7x_2,4x_1+3x_2)$.
• The matrix representation of T relative to basis $B=\{(1,3),(2,5)\}$. Solution: $T(1,3)=(-19,13)=a_{11}(1,3)+a_{21}(2,5)$ $T(2,5)=(-31,23)=a_{12}(1,3)+a_{22}(2,5)$ Gives, $a_{11}=121a_{12}=201a_{21}=-70a_{22}=-116$ Hence, $$A=\left(\begin{array}{cc}121& 201\\ -70& -116\end{array}\right)$$

Null Space and Range of a Linear Map

• Let $T:V\to W$ be a linear map. The null space of T, is defined as $null(T)=\{v\in V:T(v)=0\}$ and the range of T is defined as $range(T)=\{w\in W|\exists v\in VsuchthatT(v)=w\}$ Remarks:
  • Nullspace of T is also called kernel of T denoted by $ker(T)$.
  • $Null(T)$ is a subspace of V.
  • $Range(T)$ is a subspace of W.
  • The dimension of $Null(T)$ is called the nullity of T, denoted by $nullity(T)$.
  • The dimension of $Range(T)$ is called the rank of T, denoted by $rank(T)$.

The Rank-Nullity Theorem

• For a linear map $T:V\to W$, the rank-nullity theorem states that $dim(range(T))+dim(null(T))=dim(V)$

Example

• Determine the range and nullspace of the linear map $T:{\mathbb{R}}^3\to {\mathbb{R}}^4$ defined by $T(x_1,x_2,x_3)=(x_1-x_2+x_3,x_2-x_3,x_1,2x_1-5x_2+5x_3)$.

Solution: $Range(T)=\{(1,0,1,2),(1,-1,0,-5)\}$ $Nullspace(T)=\{(0,1,1)\}$

Metric Spaces

• It is a generalization of the notion of distance from Euclidean space.

Definition:

• A metric on a set S is a function $d:S\times S\to \mathbb{R}$ such that
  1. $d(x,y)\ge 0\forall x,y\in S$ and $d(x,y)=0⟺x=y$
  2. $d(x,y)=d(y,x)\forall x,y\in S$
  3. $d(x,z)\le d(x,y)+d(y,z)\forall x,y,z\in S$

Example

• Take $S={\mathbb{R}}^n$ and define $d(x,y)=|x-y|$ then $(S,d)$ forms a metric space.

Norm Spaces

• A norm on a real vector space V is a function $||.||:V\to \mathbb{R}$ such that
  1. $||x||\ge 0\forall x\in V$ and $||x||=0⟺x=0$
  2. $||\alpha x||=|\alpha |||x||\forall x\in V$ and $\alpha \in \mathbb{R}$
  3. $||x+y||\le ||x||+||y||\forall x,y\in V$
• A normed space is a pair $(V,||.||)$ where V is a vector space and $||.||$ is a norm on V.

Relation between Metric and Norm Spaces

• Every normed space is a metric space, but not every metric space is a normed space.

Example

• Let $X=\{0,1\}$ $d(x,y)=\{\begin{array}{ll}1& \text{if }x\ne y\\ 0& \text{otherwise}\end{array}$ $(X,d)\text{ is a metric space but not a normed space}$

Examples of some norms on ${\mathbb{R}}^n$

• $||x|{|}_1={\sum }_{i=1}^n|x_i|$
• $||x|{|}_2=\sqrt{{\sum }_{i=1}^n{x}_i^2}$
• $||x|{|}_{\infty }=ma{x}_{1\le i\le n}|x_i|$
• $||x|{|}_p=({\sum }_{i=1}^n|x_i{|}^p{)}^{1/p}$

Convex functions

• A function $f:{\mathbb{R}}^n\to \mathbb{R}$ is said to be convex if for all $x,y\in {\mathbb{R}}^n$ and $\alpha \in [0,1]$, we have $f(\alpha x+(1-\alpha )y)\le \alpha f(x)+(1-\alpha )f(y)$

Convex Sets

• A set is said to be convex, if the line joining any two points in the set lies entirely in the set. $x_1,x_2\in S\Rightarrow \alpha x_1+(1-\alpha )x_2\in S\forall \alpha \in [0,1]$

Inner Product Spaces

• An inner product on a real vector space V is a function $<.,.>:V\times V\to \mathbb{R}$ such that
  1. $<x,y>=<y,x>\forall x,y\in V$
  2. $<x,x>\ge 0\forall x\in V$ and $<x,x>=0⟺x=0$
  3. $<x+y,z>=<x,z>+<y,z>\forall x,y,z\in V$
  4. $<\alpha x,y>=\alpha <x,y>\forall x,y\in V$ and $\alpha \in \mathbb{R}$
• A vector space together with an inner product is called an inner product space.

Examples of Inner Products

$V={\mathbb{R}}^n(\mathbb{R})$ $<X,Y>={\sum }_{i=1}^n{x}_i{y}_i$ $=x_1{y}_1+x_2{y}_2+...+x_n{y}_n$ $X=(x_1,x_2,...,x_n)$ $Y=(y_1,y_2,...,y_n)$ $X.Y=|X||Y|cos(\theta )$

$l_{0}norm$

• The $l_0$ norm of a vector is the number of non-zero elements in the vector.

• It is denoted by $||x|{|}_0$

• It is not a norm in the mathematical sense, but it is used in the context of compressive/compressed sensing.

  $X=(1,2,0,0,3,0,0,4)\in {\mathbb{R}}^8$

2. ${||\alpha x||}_0\ne |\alpha |||x|{|}_0\text{for}\alpha \ne 1$ $\alpha =2$ $L.H.S=4$ $R.H.S=2x4=8$ $L.H.S\ne R.H.S$

• In real finite dimensional vector spaces, any symmetric, compact, convex region centred at the origin is a norm.

Orthogonal Vectors

• In an inner product space $V,<.,.>$, two vectors $x,y\in V$ are said to be orthogonal if $<x,y>=0$

Example

• Vectors $(1,0,0)$ and $(0,1,0)$ are orthogonal in ${\mathbb{R}}^3(\mathbb{R})$ with the inner product taken as usual dot product of vectors.

Orthogonal Complement

• If $W\subset V$ is an inner product space, then the orthogonal complement of W, denoted by $W^{\perp }$, is the set of vectors in V that are orthogonal to every element of W: $W^{\perp }=\{v\in V|v\perp w\forall w\in W\}$

Important Remarks:

• There is no requirement on W to be a subspace of V. However, if $W^{\perp }$ is always a subspace of V.
• If W is also a subspace of V, then $V=W\oplus W^{\perp }$ Means, every vector $v\in V$ can be uniquely written as $v=v_w+v_{w^{\perp }}$ where $v_w\in W$ and $v_{w^{\perp }}\in W^{\perp }$.

Example

• In ${\mathbb{R}}^3$ with inner product as usual dot product of vectors in ${\mathbb{R}}^3$, if we take $W=L[(1,0,0)]=\{(x_1,x_2,x_3)\in {\mathbb{R}}^3|x_2=0=x_3\}$ then, $W^{\perp }=L[(0,1,0),(0,0,1)]$ $=\{(x_1,x_2,x_3)\in {\mathbb{R}}^3|x_1=0\}$

Orthogonal Projection

• The linear transformation $P:V\to W$ is called the orthogonal projection onto W, where for any $v\in V$, we have $P_w(v)=\frac{<v,w_1>}{||w_1|{|}^2}{w}_1+\frac{<v,w_2>}{||w_2|{|}^2}{w}_2+...+\frac{<v,w_n>}{||w_n|{|}^2}{w}_n$ where $w_1,w_2,...,w_n$ is an orthonormal basis of W.

Example

• Let $w_1=(3,0,1)$ and $w_2=(0,1,0)$ $W=L[(3,0,1),(0,1,0)]$ Take a vector $v=(0,3,10)\in {\mathbb{R}}^3$ $P_w(v)=\frac{<v,w_1>}{||w_1|{|}^2}{w}_1+\frac{<v,w_2>}{||w_2|{|}^2}{w}_2$ $v-P_w(v)=(0,3,10)-(3,3,1)$ $=(-3,0,9)\in W^{\perp }$

Properties:

• For any $v\in V$, $v-P_w(v)\perp W$.
• $P_w(w)=w\forall w\in W$.
• $P_w^2=P_w$.
• For any $v\in V$, $||P_w(v)||\le ||v||$.
• For any $v\in V$, $||v-P_w(v)||\le ||v-w||$. or $P_w(v)=ar{g}_{w\in W}min||v-w||$

Progection

• Any linear map P that satisfies $P^2=P$ is called a projection, so $P_W$ is a projection.

Applications:

• Property 5 shows that orthogonal projection solves the minimization problem of finding the closest point in W to a given $v\in V$. This is quite usefull in ML where we need to find the closest vector in a subspace to a given vector in space.

Example

• Find the closest point to $v=(2,4,0,-2)$ in $W=L[(1,1,0,0),(0,0,1,1)]$ Solution:
• Take $w_1=(1,1,0,0)$ and $w_2=(0,0,1,1)$ $P_w(v)=\frac{<v,w_1>}{||w_1|{|}^2}{w}_1+\frac{<v,w_2>}{||w_2|{|}^2}{w}_2$ $=3\ast (1,1,0,0)-1\ast (0,0,1,1)$ $=(3,3,0,0)-(0,0,1,1)$ $=(3,3,-1,-1)$

Eigenvalues and Eigenvectors

Motivation:

1. $A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$ $x=\left(\begin{array}{c}1\\ 3\end{array}\right)$ $y=Ax=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)\left(\begin{array}{c}1\\ 3\end{array}\right)=\left(\begin{array}{c}7\\ 5\end{array}\right)$

   

2. $A=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$ $x=\left(\begin{array}{c}1\\ 1\end{array}\right)$ $y=Ax=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)\left(\begin{array}{c}1\\ 1\end{array}\right)=\left(\begin{array}{c}3\\ 3\end{array}\right)$

   

Definition:

• Let $A\in {\mathbb{R}}^{n\times n}$, we say that a non-zero vector $v\in {\mathbb{R}}^n$ is an eigenvector of A corresponding to eigenvalue $\lambda$ (a scalar) if $Av=\lambda v$
• The above relation tells that when the matrix (linear transformation) A applied on v, then it scales v by a amount $\lambda$.

How to find Eigenvalues and Eigenvectors:

$$A=\left(\begin{array}{ccc}2& -2& 3\\ 1& 1& 1\\ 1& 3& -1\end{array}\right)$$

$Av=\lambda v$ $(A-\lambda I)v=\vec{0}$ $det(A-\lambda I)=0$

$$A-\lambda I=\left(\begin{array}{ccc}2-\lambda & -2& 3\\ 1& 1-\lambda & 1\\ 1& 3& -1-\lambda \end{array}\right)$$

$det(A-\lambda I)=(2-\lambda )((1-\lambda )(-1-\lambda )-3)+2((-1-\lambda )-1)+3(3-(1-\lambda ))$ $det(A-\lambda I)=0$ $\Rightarrow \lambda =3,1,-2$

• $\lambda =3$

  (A - 3I)v = {0} \Rightarrow \begin{pmatrix} -1 & -2 & 3 \\ 1 & -2 & 1 \\ 1 & 3 & -4 \end{pmatrix} \dot \begin{pmatrix} v_{1} \\ v_{2} \\ v_{3} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}

  $\Rightarrow v_1=V_2=v_3$

  For $\lambda =3$, the eigenvector is (1,1,1).

• $\lambda =1$

  $$(A-I)v=0\Rightarrow \left(\begin{array}{ccc}1& -2& 3\\ 1& 0& 1\\ 1& 3& -2\end{array}\right)\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)$$

  $\Rightarrow v_1=v_2=v_3$

  For $\lambda =1$, the eigenvector is (1,-1,-1).

• $\lambda =-2$

  $$(A+2I)v=0\Rightarrow \left(\begin{array}{ccc}0& -2& 3\\ 1& 3& 1\\ 1& 3& 1\end{array}\right)\left(\begin{array}{c}{v}_1\\ v_2\\ v_3\end{array}\right)=\left(\begin{array}{c}0\\ 0\\ 0\end{array}\right)$$

  $\Rightarrow v_1=-v_2=v_3$

  For $\lambda =-2$, the eigenvector is (1,-1,1).

Properties:

$AX=\lambda X$

1. $A^{-1}X=A^{-1}(\lambda X)=A^{-1}X=\frac{1}{\lambda }X$
2. $AX=\lambda X\Rightarrow A^{2}X=A(\lambda X)=\lambda (\lambda X)={\lambda }^{2}X$ $A^{k}X={\lambda }^{k}X$
3. Trace(A) = Sum of Eigenvalues of A.
4. Determinant(A) = Product of Eigenvalues of A.

Colab

Quadratic Forms

• Let $A\in {\mathbb{R}}^{n\times n}$ be a symmetric matrix. The expression $q(x)=X^{T}AX$ is called a quadratic form.

Example:

• Given $$A=\left(\begin{array}{ccc}1& -1& 2\\ -1& 3& 1\\ 2& 1& 4\end{array}\right)$$ Then for $X=(x_1,x_2,x_3{)}^T$, we have $q(X)=X^{T}AX$ $={x_1}^2+{3x_2}^2+{4x_3}^2-2x_1{x}_2+2x_1{x}_3+2x_2{x}_3$ Similarly if $q(X)=x_1^2+4x_1{x}_2+x_2^2+2x_3^2+6x_2{x}_3$ then associated matrix A to this quadratic form is given as $$A=\left(\begin{array}{ccc}1& 2& 0\\ 2& 1& 3\\ 0& 3& 2\end{array}\right)$$

Rayleigh Quotient

• For a n x n real matrix A, we have $R_A(X)=\frac{X^{T}AX}{X^{T}X}$ where $X\ne 0$ Furthermore, we have
  • Scale invariance: For any $X\ne 0$ and any scalar $\alpha \ne 0$, we have $R_A(\alpha X)=R_A(X)$
  • If X is an eigenvector of A with eigenvalue $\lambda$, then $R_A(X)=\lambda$
  • ${\lambda }_{min}(A)=mi{n}_{X\ne 0}{R}_A(X)$
  • For any X such that $||X|{|}_2=1$, we have ${\lambda }_{min}(A)\le X^{T}AX\le {\lambda }_{max}(A)$ This equality holds iff X is corresponding eigenvector.
  • For any $X\ne 0$, we have ${\lambda }_{min}(A)\le R_A(X)\le {\lambda }_{max}(A)$

Positive Semi-Definite (PSD) matrices

• A symmetris matrix $A\in {\mathbb{R}}^{n\times n}$ is said to be positive semi-definite if for all $X\in {\mathbb{R}}^n$, we have $q(X)=X^{T}AX\ge 0$

Properties:

• A symmetric matrix is positive (semi-) definite if and only if its all eigenvalues are positive (non-negative).
• A symmetric matrix is positive (semi-) definite if and only if all pivots are positive (non-negative).

Example

• Let $$A=\left(\begin{array}{cc}1& 3\\ 3& 10\end{array}\right)$$ then $X^{T}AX=x_1^2+6x_1{x}_2+10x_2^2=(x_1+3x_2{)}^2+9x_2^2\ge 0$ Hence, A is PSD matrix.

Positive Definite (PD) matrices

• A symmetric matrix $A\in {\mathbb{R}}^{n\times n}$ is said to be positive definite if for all $X\in {\mathbb{R}}^n$, we have $q(X)=X^{T}AX>0$

Example

$$A=\left(\begin{array}{cc}1& 3\\ 3& 10\end{array}\right)$$

Important Results:

• Suppose $A\in {\mathbb{R}}^{n\times n}$. Then $A^{T}A$ is PSD. Moreover, if $Nullspace(A)=0$, then $A^{T}A$ is PD.
• If A is PSD and $ϵ>0$, then $A+ϵI$ is PD.

Example

$Ax=b$ $A^{T}Ax=A^{T}b$ $Mx=\vec{b}$

The geometry of PD quadratic forms

• The isocontour of $q(X)=X^{T}AX$ is an ellipsoids s.t. the axes points in the direction of the eigenvectors of A, and the radii of these axes are proportional to the inverse square root of the corresponding eigenvalues.