ml(Math-3)

Learning Outcomes:

• Eigendecompositon of a square matrix.
• Necessary conditions for eigendecomposition.
• Spectral decomposition of the symmetric matrix.

Note: Like eigen-pairsm, spectral decomposition is again very important concepts in many ML algorithms. Some of these algorithms can be listes as: PCA, Spectral Clustering, Statistical ML algorithms, reinforcement learning, image processing, etc.

Eigen-decomposition

• Let A be a square matrix of order n. Also let {$v_1,v_2,...,v_n$} be the n Linearly Independent eigenvectors of A. Then the matrix A can be decomposed as: $A=PD{P}^{-1}$ where P is the matrix whose columns are the eigenvectors of A and D is the diagonal matrix whose diagonal elements are the corresponding eigenvalues of A.
• The $i^{th}$ column of P is the eigenvector $v_i$ of A, and D is a diagonal matrix whose diagonal elements are the corresponding eigenvalues of A. $\Rightarrow D_{ii}={\lambda }_i$ $({\lambda }_i\text{ is the eigenvalue corresponding to the eigenvector }{v}_i)$

Note: Every square matrix does not possess the property of eigen-decomposition. The necessary and sufficient conditions for the eigen-decomposition of a square matrix are:

Example for reference:

Not Eigen-Decomposable

Necessary conditions for eigen-decomposition:

• We need AM = GM for each eigenvalue of A.
  • The matrix A should have n linearly independent eigenvectors.
  • The eigenvectors of A forms a basis of n-dimensional vector space.

Spectral Decomposition

• Let A be a $n\times n$ symmetric matrix. Then, the eigen-decomposition of A is guaranteed $\Rightarrow A=PD{P}^{-1}$ where P is the matrix whose columns are the eigenvectors of A and D is the diagonal matrix whose diagonal elements are the corresponding eigenvalues of A.

• Consider ${\lambda }_1,{\lambda }_2,...,{\lambda }_n$ be the eigenvalues of A and $v_1,v_2,...,v_n$ be the corresponding eigenvectors of A. Then, the spectral decomposition of A is given by:

  Note: Each matrix $v_i{v_i}^T$ is the projection onto 1-D subspace spanned by $v_i$. In other words, $P(x)=v_i{v_i}^{T}x$ Orthogonal Projection maps x onto the line spanned by $v_i$.

Example for reference:

Spectral Decomposition Spectral Decomposition

Singular Value Decomposition (SVD)

Singular Values:

• Let $A\in {\mathbb{R}}^{m\times n}$ . Consider the matrix $A^{T}A.Itisasymmetric$n \times n$matrixwhichispossitivesemidefinite.Theeigenvaluesof$A^{T}Aare $${\sigma}_1 \geq {\sigma}_2 \geq ... \geq {\sigma}_n \geq 0$$ Let, $${\sigma}_1 = \sqrt{{\lambda}_1}$$ $$\Rightarrow {\sigma}_1 \geq {\sigma}_2 \geq ... \geq {\sigma}_n \geq 0$$ The numbers{\sigma}_1, {\sigma}_2, …, {\sigma}_n$ are called the singular values of A.

Singular Value Decomposition:

• Let A be a $m\times n$ matrix. Then, the Singular Value Decomposition of A is given by: $A=UD{V}^T$ where U is a $m\times m$ orthogonal matrix, D is a $m\times n$ diagonal matrix and V is a $n\times n$ orthogonal matrix. $A_{m\times n}=U_{m\times m}{D}_{m\times n}{V}_{n\times n}^T$ $r=rank(A)\le min(m,n)$
  • V is the matrix whose columns are the eigenvectors of $A^{T}A$.
    • We can have eigenvectors $v_1,v_2,...,v_n$ of $A^{T}A$ such that $A^{T}A{v}_i={{\sigma }_i}^2{v}_i$ Moreover, these $v_i$ are pairwise orthogonal to each other.
  • U is the matrix whose columns are the eigenvectors of $A{A}^T$.
    • Now take the orthonormal eigenvectors of $A{A}^T$ as $u_1,u_2,...,u_m$ such that $A{A}^T{u}_i={{\sigma }_i}^2{u}_i$ Moreover, these $u_i$ are pairwise orthogonal to each other.
  • D or $\sum$ is the diagonal matrix whose diagonal elements are the singular values of A.
    • The diagonal elements of D are the square roots of the eigenvalues of $A^{T}A$ or $A{A}^T$.

Example for reference:

SVDExample1 SVDExample2

Applications of SVD:

Properties of SVD:

• Let $A\in {\mathbb{R}}^{m\times n}$ with rank(A) = r and $A=UD{V}^T$ be the SVD.
  • Only the first r (= rankA) singular values are non-zero.
  • The range(A) is given by the first ‘r’ columns of U.
  • The null(A) is given by the last ‘n-r’ columns of V.(i.e. the solution space of AX = 0).
  • The $range(A^T)$ is given by the first ‘r’ columns of V.
  • The $null(A^T)$ is given by the last ‘m-r’ columns of U.

Pseudo-Inverse:

Example for reference:

Operator and Matrix Norms:

• If V(F) and W(F) are vector spaces and the set defined as $\mathbb{T}=\{T:V\to W\text{ such that T is linear}\}$

  The set $\mathbb{T}$ is a vector space over the field F. The norm $||T|{|}_{op}=ma{x}_{X\in V,X\ne 0}\frac{||T(X)|{|}_W}{||X|{|}_V}$ is called the operator norm on the space $\mathbb{T}$. For a matrix $A\in {\mathbb{R}}^{m\times n}$, we define the matrix p-norm as $||A|{|}_p=ma{x}_{X\ne 0}\frac{||AX|{|}_p}{||X|{|}_p}$ where $||X|{|}_p$ is the p-norm of the vector X.

Spectral and Frobenius Norms:

Matrix Norms:

Example for all the above concepts:

Rank of a Matrix:

• The rank of a matrix A is the maximum number of linearly independent columns in A. $rank(A)=dim(range(A))$ It is the number of L.I. rows or columns in A.

  $$A=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$$

  is having rank 3.

  $$A_2=\left[\begin{array}{ccc}2& 1& -1\\ 1& 0& 1\\ 1& 1& -2\end{array}\right]$$

• Let $A\in {\mathbb{R}}^{m\times n}$. Then,

  • $rank(A_T)=rank(A)$
  • $rank(PAQ)=rank(A)$ for invertible matrices P and Q.
  • $rank(AB)\le min(rank(A),rank(B))$
  • rank(\begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}) \leq rank(A) + rank(B)$ = rank(A_{11}) + rank(A_{22}) where $A_{11},A_{12},A_{22}$ are block matrices.

Rank and Matrix Factorization

Low Rank Approximation:

• Let $A\in {\mathbb{R}}^{m\times n}$ (often large), having $rank(A)\le min(m,m)$. The low-rank approximation of A is to find another matrix $A_k\in {\mathbb{R}}^{m\times n}$ which is having rank $k\le r$ and approximate A.
• To find the “best” $A_k$ we must define how closely $A_k$ approximates A. The simplest metric is the Frobenius norm of $A-A_k$.This criterion leads to the following low-rank approximation problem:

Convexity

Measure of quality of approximation:

• A measure of quality of the approximation is given by

Example

Application of Image Processing

• A sequence of low rank approximations follows. We see the input image, the low rank approximation, the error, and the threshold for the spectrum. The image matrix has rank 266. Using a rank of 25 produces a reasonable approximation.

Learning Outcomes:

• One of the most popular and widely used matrix decomposition method is the Singular Value Decomposition (SVD).
• All matrices have an SVD, which makes it more stable than other methods, such as the eigendecomposition.
• It is having applications in order to deal with big-data. More specifically some of these application include compressing, denoising, an ddata reduction.

Colab