Importance of Matrix Decomposition

Matrix Decomposition & Algorithms

Exploring Matrix Decomposition and Algorithms

Working on small parts is very easy rather on single big part, in the same way Decomposition allows us to break matrix into several small pieces of Matrices , it is called Matrix Decomposition. Decomposition allows us to Decompose the Matrix in the form of vectors and matrices.

In order to understand Linear Algebra concepts and apply in Artificial Intelligence and Quantum Computing, you can read following articles.

Linear Algebra in Artificial Intelligence & Quantum Computing

Linear Algebra- How uses in Artificial Intelligence ?

Quantum Computing — required Linear Algebra

Why we need to study Decomposition?

Decomposition is very important in algorithmic perspective in order to understand performance. In computation, these are required to consider time and space complexity to evaluate the performance. Decomposition methods are used to calculate determinant, upper and lower triangle matrices, matrix inversion, eigen values and eigen vectors, etc., to work on various types of matrices (symmetric, non-symmetric, square, non-square ). In a nutshell, decomposition helps us to write optimistic algorithms, and calculate Linear Algebra Object properties and various matrices.

Large mathematical objects can be easily understood better by decomposing into small parts. The best example integers can be decomposed into prime factors.

Different Types of Decomposition exists in Linear Algebra

Types of Decomposition

Kindly note that, there are other decompositions exist in Linear Algebra and not covered in this article.

One of the most widely used decomposition method is “Eigen decomposition”, decomposing a matrix into a set of eigenvectors and eigenvalues. Decomposing the matrix using factorization. The outcome matrices are the factors. Eigenvectors are the factors.

Eigen Decomposition

Let ‘M’ be a square matrix and ‘v’ be a non-zero vector such that multiplication by A alters only the scale of v :

We can form the Matrix ‘A’ using eigenvectors and eigenvalues.

Form Matrix ‘A’ using eigenvectors and eigenvalues

In the following equations explained eigenvectors ,eigenvalues and properties of decomposition.

Eigen Decomposition

Properties of eigenvalues and eigenvectors:

1. The trace of A is equal to the sum of the sum of its eigenvalues.
2. The determinant of A is equal to the product of eigenvalues.
3. The rank of matrix is equal to the number of non-zero eigenvalues of A.
4. The eigenvalues of a diagonal matrix D = diag(d1,d2,…, dn) are just the diagonal entries d1,d2,…dn

Definite/Semi-definite Matrices Based on Eigen decomposition:

Definite, Semi-definite matrices

Eigenvalues and Eigenvectors Example:

Eigen Values and Eigen Vectors Example

Pros & Cons of Eigen decomposition:

Pros: Once you apply eigen decomposition on square matrix then you will get other properties very easily like trace, determinant, rank, diagonals, etc.,

Cons: Eigen Decomposition works only on Square Matrices.

Decomposition can be done for both Square and Non-square matrices.

Eigenvectors for square matrices, but SVD is for all matrices.

Applications of Eigen Decomposition:

The following Algorithms uses Eigenvalues and Eigenvectors in various fields.

1. PCA
2. Page Rank
3. Schrodinger’s Equation

Decomposition Algorithms in Machine Learning:

Decomposition (especially eigen decomposition) used in many algorithms.

The most popular and widely used algorithms which are based on Decomposition methods are PCA and SVD, which are pure Linear Algebra based.

SVD, PCA Algorithms and Applications

Principal Component Analysis is the tool in Exploratory Analysis , Dimensionality Reduction and Prediction models. It can be used in many algorithms as a pre-processing step.

PCA Problem Statement Given a set of points, how do we know if they can be compressed? The answer is to look into the correlation between the points. The tool for doing this is called PCA. The best example for application of SVD , PCA is Image Compression in Computer Vision.

PCA Algorithms using Eigen decomposition works is as follows for Training and testing data sets:

PCA Algorithm for Training Data

PCA Algorithm for Testing Data

Single Value Decomposition:

There are several computer algorithms that can “factorize” a matrix, representing it as the product of some other matrices.

The most useful of these is the Singular Value Decomposition. SVD applied for non-square Matrix.

Representing any matrix A as a product of three matrices:

How SVD Algorithm factorize the Original Matrix:

SVD Decomposition on Matrix (n*m) Dimensions

Schur Decomposition

Schur Decomposition is based on Eigen Decomposition and is decomposed into 3 matrices of the Original matrix. It is defined as follows:

QZ Decomposition

It is also called generalized Schur Decomposition. It is applicable to Square matrices and can be defined as follows.

Suppose A and B are two (N,N) non-symmetric matrices which can be both in real or complex. The QZ decomposition factorizes as

Where Q and Z are unitary and S and T are upper triangular. Unitary means

if X is complex (OR)

if X is real and I is the identity matrix.

The QZ decomposition is also called Generalized Schur Decomposition where S and T are the Schur form of A and B matrices.

The generalized eigenvalues that solve the generalized eigenvalue problem

Where x is an unknown nonzero vector and eigenvalue defined as

In special case B is Identity Matrix I, then reduces to fine Q such that

OR

Suppose B is an identity matrix I, then the problem reduces to traditional eigenvalue problem.

Decomposition on Linear Equations

QR Decomposition

QR decomposition of a Matrix A into a product A = QR of an orthogonal matrix Q and an upper triangular matrix R. It is often used to solve linear least squares problem and is the basis for a particular eigenvalue algorithm, the QR algorithm.

It can be often applied to various matrices like Square matrix and Rectangular matrix. There are several methods for actually computing the QR decomposition, such as Gram-Schmidt, Householder transformations, or Givens rotations.

It decompose the matrix into an orthogonal matrix and a triangular matrix. A QR decomposition of a real square matrix M is a decomposition of M as

M = QR ; Where Q is an orthogonal matrix

and R is an upper triangular matrix. If matrix M is nonsingular, then this factorization or decomposition is unique.

There are several methods exists for computing QR decomposition. Gram-Schmidt is one such method described in this article.

In this method, vectors to be considered as column of the matrix M. That is,

QR Factorization

The QR factorization defined as

Once we find,

, it is easy to write the QR Factorization

Consider the Matrix M of 3 rows and 3 columns

Thus,

LU Decomposition

LU Decomposition is another method to solve a set of simultaneous linear equations. LU can be written as M = LU; Where L is lower triangular and U is upper triangular Matrix.

How does LU decomposition work?

Set of linear equations in the form of AX=b ; and we have to decompose into LU.

Consider Matrix M and it has the form MX=b; By def M = LU and substitute in MX=b; then we Get LUX = b;

LU Decomposition can be used as

Given AX=b

Decompose Matrix M into Lower and upper triangle matrices as follows

The following example decomposing LU.

The [L] Matrix can be found as

After obtaining L and U triangular matrices , we can form actual Matrix by Matrix Multiplication of L and U matrices.

In summary, LU Decomposition can be done as

Applications of LU Decomposition

Major applications of LU decomposition are

1. Solving linear equations
2. Inverting a matrix
3. Computing the determinant

Cholesky Decomposition

Cholesky Decomposition with positive definite matrices. Let us revise positive definite in Matrices. A symmetric n*n matrix A is positive definite if the quadratic for all non-zero vectors x or, equivalently, if all the eigenvalues of A are positive. i.e.,

Positive definite matrices can be expressed in the form for a non-singular matrix X. i.e.,

Cholesky decomposition is commonly used to solve the normal equations that characterize the least squares solution to the overdetermined linear system Ax=b. Normal equation like

The Cholesky Decomposition is the particular form of the factorization in which X is upper triangular with positive diagonal elements; it is written as

A variant of Cholesky decomposition is the factorization in Lower triangular and D is diagonal. This factorization exists and is unique for positive definite matrices. If D is allowed to have non-positive diagonal entries, the factorization exists for some indefinite matrices.

Where L is unit lower triangular (i.e., has unit diagonal) and D is diagonal. If D allows to have non-positive diagonal entries, the decomposition exists for some indefinite matrices.

Note that, when A is positive definite the Cholesky factor is given by

Cholesky Decomposition Computation

Decomposition can be computed by a form of Gaussian elimination that takes advantage of the Symmetry and definiteness. Equating (i,j) elements in the equation i.e.,

These equations can be solved to yield R a column at a time, according to the following algorithm:

The above algorithm requires flops and n square roots, where a flop is any of the four elementary scalar arithmetic operations +,-,*, and /.

Applications

To work on block sizes in programming languages. For example: In modern libraries such as LAPACK,3 the factorization is implemented in partitioned form, which introduces another level of looping in order to extract the best performance from the memory hierarchies of modern computers. To illustrate, we describe a partitioned Cholesky factorization algorithm. For a given block size r, we can write

Rank Factorization (RF)

Let us define few concepts to learn Rank Factorization.

Let M be a matrix with dimensions (m,n). Then the column space of C(M) is

and the row space of M is

Notation Row rank of M dim (R(M)) and Column Rank of M is dim(C(M)).

For any matrix M, the rank of M equals the column rank of M.

Rank

The Rank of a Matrix M is common value of row rank of M and the column rank of M and is denoted by

Full Row Rank

A matrix M of dimensions (m,n) is said to be of full row rank if its rows are linearly independent. i.e., its rank is m. Similarly M is said to be full column rank if its columns are linearly independent.

Let us define left and right inverse of matrix M. A left matrix of a matrix M is any matrix B such that BM = I. A right inverse of Matrix M is any matrix C such that MC = I.

A matrix B is said to be an inverse of M if it is both a left and right inverse of M.

Properties of Rank

Let M be a matrix of dimensions (m,n) over F, Then M has the right inverse. XM = 0 => X =0. M is of full row rank. In the similar way M has left inverse. MX = 0 => X =0 . M is of full column rank.

Defining Rank Factorization

Let M be a matrix of dimensions(m,n) with rank ≥1. Then (P,Q) is said to be rank factorization of M if P of dim(m,r) , Q is of dim(r,n) and M = PQ.

Properties Of Rank Factorization

1. Every non-null matrix has a rank-factorization.
2. A null matrix cannot have a rank-factorization, since there cannot be a matrix with 0 rows.
3. Rank-factorization of a matrix is not unique.
4. If (B,C) is a rank-factorization of M, then Transport of B, C i.e.,

is also rank-factorization of Transpose of M.

When a Factorization is a Rank-Factorization

Let M = PQ where P is a (m,k) and Q is (k,n) dimensions. Then the rank of M is is at most k.

The following are equivalent:

1. The rank of m is k,
2. (P,Q) is a rank-factorization of M
3. P is of full column rank and Q is of full row rank
4. The columns of P form a basis of C(M)
5. The row of Q form a basis of R(M).

Conclusion

Linear Algebra is the most essential subject in Algorithms, Computation (Classical and Quantum Computers) and storage space while computing. Decomposition plays vital role in algorithms and easily compute various types of matrices and can work on specific elements in the Matrices.

Thanks for reading my article. Let me know if there are any corrections required.