1.
Introduction
2.
What is a Singular Decomposition Function?
3.
Mathematical Proof of Singular Decomposition
4.
Implementation of Singular Value Decomposition
5.
Application of Singular Value Decomposition
6.
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Singular Value Decomposition

Tushar Tangri
0 upvote

## Introduction

The most extensively used multivariate statistical approach is the singular value decomposition (SVD). Edward Lorenz initially introduced the approach to meteorology in a 1956 publication, referring to the approach as empirical orthogonal function (EOF) assessment. It's also referred to as principal-component analysis nowadays (PCA). All three titles are still in use, and they relate to about the same set of Data Library operations.

The goal of SVD is to minimize a dataset with a substantial possible value to a dataset with significantly fewer values but still retain a significant portion of the original data's variability.SVD analysis, especially with multivariate datasets, leads to a more refined version of these correlations and can give insight into variations in the fields of data being investigated.

Before determining the SVD of a data set, there are a few things to keep in mind. The data must first contain abnormalities. The data should also be de-trended. W.hen the data’s long-term patterns, the first structure frequently catches them. The data should be de-trended before using SVD analysis if the goal is to uncover correlations independent of trends.

## What is a Singular Decomposition Function?

The factorization of a matrix A into the product of three matrices A = UDVT. The column of U and V is orthonormal, and the matrix D is diagonal with accurate positive entries, known as singular value decomposition. The SVD is valid for a variety of activities. We'll give some instances here.

First, data matrix A is often near a low-rank matrix, and it is essential to locate a low-rank matrix that is a reasonable approximation towards the data matrix. We'll show that we can extract the matrix B of rank k that best approximates A in the singular value decomposition; in fact, we can do this for any rank k.

## Mathematical Proof of Singular Decomposition

Singular Value Decomposition mathematically states that for any matrix A∈R n×m A∈Rn×m, we have A=UΣV⊤ , where

U∈Rn×n is an orthogonal matrix whose columns are the eigenvectors of AA⊤

(AAT = UDVTVDUT = UD2UT

V∈Rm×m is an orthogonal matrix whose columns are the eigenvectors of A⊤A

(ATA = VDUTUDVT = VD2VT)

Σ∈Rn×m is an all-zero matrix except for the first r diagonal elements σi=Σii, i=1,…,r (called singular values) that are the square roots of the eigenvalues of A⊤A and of AA⊤ (these two matrices have the same eigenvalues).

D = diag( 1 , 2 ,..., n ) ordered so that 1 ≥ 2 ≥ ... ≥ n (if is a singular value of A, it’s square is an eigenvalue of A T A) - If U = (u1 u2 ... un ) and V = (v1 v2 ... vn ), then

The sum here goes from 1 to r, where r is the rank of the A here.

As shown above, the singular values are sorted in descending order, and the eigenvectors are sorted in decreasing order of their eigenvalues.

Let’s understand this with the help of an example stated below:

Let’s take a matrix A:

The eigenvalues of AAT , ATA are:

The eigenvectors of AAT , ATA are:

The expansion of A is:

Based on the above formulae, we get:

## Implementation of Singular Value Decomposition

We can understand the implementation of singular value code with this simple example stated below.

Step 1: We import the required libraries. We use the most popular libraries that are numpy and linear algebra libraries, part of numpy.

We use eigh, which is used to find the hermitian matrixes for eigenvalues and eigenvectors. We use the norm function to find the norm of a vector.

import numpy as np
from numpy.linalg import eigh, norm

Step 2: We create an array as you can see if you have arrays inside an array that's like a

matrix because each of these arrays of numbers is thought of as rows of a matrix, and you put commas and then enclose them again by brackets that give you a two-dimensional array and which is a matrix.

A = np.array([[-5, 2, 3],
[2, 5, 1],
[-3, 1, -5]])

Step 3: Perform the matrix multiplication, which in the case of standard value decomposition is:

A.T@A

Output:

array([[38, -3,  2],
[-3, 30,  6],
[ 2,  6, 35]])

We use the symbol ‘@’ for matrix multiplication here, and we find a symmetric matrix indeed.

Step 4: We take the eigenvalues and eigenvectors here.

eigh(A.T@A)

Output:

(array([25., 39., 39.]), array([[ 0.26726124, -0.96362411,  0.        ],
[ 0.80178373,  0.22237479,  0.5547002 ],
[-0.53452248, -0.14824986,  0.83205029]]))

This gives us some integer eigenvalues, and the same procedure can be used for any matrix size.

Step 5: We assign the second matrix of arrays to a variable V here, and we print V to see the values taken here.

ev, V =eigh(A.T@A)
V

Output:

array([[ 0.26726124, -0.96362411,  0.        ],
[ 0.80178373,  0.22237479,  0.5547002 ],
[-0.53452248, -0.14824986,  0.83205029]])

Each of the columns here is the eigenvectors for A.T@A.

Step 6: We find the first eigenvector here using the following code. This gives us row vectors of the column vector.

V[:,0]

Output:

array([ 0.26726124,  0.80178373, -0.53452248])

Step 7: Define the matrix U, and we do it starting from the Oth index. We apply A to the column vector of V and divide it by its size.

u0 =A@V[:,0]/norm(A@V[:,0])
u1 =A@V[:,1]/norm(A@V[:,1])
u2 =A@V[:,2]/norm(A@V[:,2])

Step 8: We create U as a 2-dimensional matrix, and we divide it with its transpose cause we want columns here and not rows, so these are taken as column vectors.

U=np.array([u0,u1,u2]).T

Using the below code, we get a diagonal matrix we round it to five decimal places to make our observations look simpler.

np.round(U.T@A@V, decimals=5)

Output:

array([[ 5.   ,  0.   , -0.   ],
[-0.   ,  6.245,  0.   ],
[-0.   , -0.   ,  6.245]])

Step 9: When we multiply T and V to the other size, we get the SVD of our equation. We print U to take a look at what U looks like.

#A = U@D@V.T is the SVD
U

Output:

array([[-0.26726124,  0.77151675,  0.57735027],
[ 0.80178373, -0.15430335,  0.57735027],
[ 0.53452248,  0.6172134 , -0.57735027]])

We have successfully found the SVD here of the given matrix using python. Now let’s jump to some real-world applications of SVD.

## Application of Singular Value Decomposition

1. Dimensionality Reduction
The first and most essential application is to reduce data dimensionality; the SVD is a very convenient method, and PCA is identical to the SVD. You may wish to decrease the dimensionality of your data for the following reasons:
→ You want to visualize your data in 2D or 3D;
→ The method you're going to employ works much better in the lower dimensional space;
→ For performance reasons, reducing dimensions makes your algorithm quicker.
→ It's usually worth trying to use the SVD before an ML technique in many machine learning tasks.

2. Image Compression
We can take advantage of this. A digitized image is just a large number matrix. For example, in a black-and-white image, they may be the gray levels, or in a color image, the color levels. Let's imagine our image has a resolution of 1000 x 2000 pixels. This necessitates the use of two million numbers.
We would only need to keep ten u's (10000 numbers), ten v's (20000 numbers), and 10's if the picture could be adequately represented by, say, a tenth term SVD decomposition (10 numbers). Our storage costs reduce, resulting in a compression ratio of more than 650:1.

3. Web-Searching
Google and other search engines employ massive matrices of cross-references to figure out which pages connect to which other pages and what phrases appear on each page. When you run a Google search, the pages with your key terms that have a lot of links to them generally rank higher.
However, there are many trillions of web pages out there, and keeping a billion-by-billion matrix, much alone navigating through it, is difficult. This is where SVD shines. When it comes to searching, the fundamental dimensions that the Digital world is taking are all that matter.
As a result, the first few single values give a very excellent approximation for the vast matrix, can be searched fast (only a few billion entries), and provide compression algorithms of millions to one.

4. Latent Semantic Indexing
When processing a corpus of text, we can decompose it into a term x document matrix, which can then be decomposed using the SVD.
The lowered estimation encapsulates (in some way) the ambiguity in our text, which has several advantages such as noise filtering, fixing the issue of synonyms, and so on. This has a wide range of applications in the field of information retrieval.

1. Is SVD applicable to all matrices?
Unlike the more often used spectral decomposition in Linear Algebra, singular value decomposition is specified for all matrices (rectangular or square).
Those who are conversant with eigenvectors and eigenvalues Recognize that requirements on the matrix are required to guarantee that the eigenvectors are orthogonal.

2. Is SVD persistent in all matrices?
The SVD is always true for every rectangular or square matrix, but the eigendecomposition is only valid for square matrices; it isn't always true among even square matrices.

3. Is SVD essential for persistent matrix reduction?
Significant is the fraction of a vector's linear transformation corresponding to a substantial single value. Positive singular values can be utilized to establish the effectual rank of matrix A by counting smaller values as zeros, in addition to what you mention in your query.

## Conclusion

Going through this article, we can conclude that Singular Value Decomposition (SVD) is a popular approach for decomposing a matrix into many component matrices, revealing many of the original matrix's valuable and intriguing features.

Recommended Problems:

We can use SVD to identify the matrix's rank, measure a linear system's susceptibility to numerical error, or find the best lower-rank estimate to the matrix.