Matrix Decomposition with SciPy

Introduction to Matrix Decomposition

Welcome to the final lesson of our course on utilizing the SciPy library for linear algebra tasks. In this lesson, we will explore matrix decomposition, a crucial technique in linear algebra that simplifies complex matrix operations. We will specifically focus on two popular decompositions: LU decomposition, which breaks down a matrix into three simpler matrices (a lower triangular (L), an upper triangular (U), and a permutation (P) matrix), and Singular Value Decomposition (SVD), which factors a matrix into an orthogonal matrix, a diagonal matrix of singular values, and the transpose of another orthogonal matrix. These decompositions play significant roles in solving matrix equations, finding matrix inverses efficiently, and addressing various applications in data science and engineering. While there are other decomposition methods, these are among the most prevalent and widely used.

Understanding LU Decomposition

A

Performing LU Decomposition with SciPy

Let's walk through the process of performing LU decomposition using the scipy.linalg.lu function. First, ensure you have imported the necessary libraries, specifically NumPy for handling arrays and SciPy for LU decomposition. Python import numpy as np from scipy.linalg import lu Next, define the matrix A that we want to decompose. In our case, this will be a simple 3x3 matrix: Python A = np.array([[4, 3, 2], [6, 3, 4], [2, 1, 3]]) We'll now use scipy.linalg.lu to decompose matrix A into P, L, and U matrices. Python P, L, U = lu(A) Explanation: lu(A) computes the LU decomposition of matrix A . The function returns three matrices: P, L, and U .

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

The resulting matrices are:

text

[[0. 1. 0.]
 [1. 0. 0.]
 [0. 0. 1.]]

[[0. 1. 0.]
 [1. 0. 0.]
 [0. 0. 1.]]

text

[[1.00000000e+00 0.00000000e+00 0.00000000e+00]
 [6.66666667e-01 1.00000000e+00 0.00000000e+00]
 [3.33333333e-01 5.55111512e-17 1.00000000e+00]]

[[1.00000000e+00 0.00000000e+00 0.00000000e+00]
 [6.66666667e-01 1.00000000e+00 0.00000000e+00]
 [3.33333333e-01 5.55111512e-17 1.00000000e+00]]

text

[[ 6.          3.          4.        ]
 [ 0.          1.         -0.66666667]
 [ 0.          0.          1.66666667]]

[[ 6.          3.          4.        ]
 [ 0.          1.         -0.66666667]
 [ 0.          0.          1.66666667]]

After obtaining the LU decomposition, it's essential to verify that these matrices correctly represent the original matrix A. We do this through matrix recomposition.

To recompose the matrix, multiply matrices L and U, and then apply the permutation matrix P.

Python

recomposed = np.dot(L, U)
recomposed = np.dot(P, recomposed)

recomposed = np.dot(L, U)
recomposed = np.dot(P, recomposed)

Compare the recomposed matrix with the original matrix to check for consistency.

Python

if np.allclose(recomposed, A):
    print("Verification successful: LU decomposition and recomposition are correct!")
else:
    print("Verification failed: There is a discrepancy in the decomposed matrices.")

if np.allclose(recomposed, A):
    print("Verification successful: LU decomposition and recomposition are correct!")
else:
    print("Verification failed: There is a discrepancy in the decomposed matrices.")

The np.allclose() function checks if two arrays are element-wise equal within a tolerance, ensuring the recomposition matches the original A.

Another vital decomposition technique is Singular Value Decomposition (SVD), which factors a matrix $A$ into three matrices: $U$ , $\Sigma$ , and $V^T$ . SVD is powerful for data compression, noise reduction, and solving ill-posed problems.

U: An orthogonal matrix whose columns are the left singular vectors.
$\Sigma$ : A diagonal matrix with singular values on the diagonal.
V^T: The transpose of an orthogonal matrix whose columns are the right singular vectors.

Performing SVD on matrix $A$ :

Python

from scipy.linalg import svd

U, Sigma, VT = svd(A)

The resulting matrices are:

text

[[-0.52604938 -0.58275167 -0.61941306]
 [-0.77729892  0.03392956  0.62821586]
 [-0.34507743  0.81194167 -0.47082087]]

[[-0.52604938 -0.58275167 -0.61941306]
 [-0.77729892  0.03392956  0.62821586]
 [-0.34507743  0.81194167 -0.47082087]]

Sigma:

text

[10.03662777  1.71082968  0.5823786 ]

[10.03662777  1.71082968  0.5823786 ]

VT:

text

[[-0.74309281 -0.42395937 -0.51775625]
 [-0.29432853 -0.48778945  0.82184681]
 [ 0.60098568 -0.76309889 -0.23768949]]

[[-0.74309281 -0.42395937 -0.51775625]
 [-0.29432853 -0.48778945  0.82184681]
 [ 0.60098568 -0.76309889 -0.23768949]]

To verify the SVD decomposition, we recompose the original matrix A from the components U, Sigma, and VT.

First, we need to convert Sigma from a 1D array to a 2D diagonal matrix, as scipy.linalg.svd returns singular values in 1D form:

Python

Sigma_matrix = np.zeros((U.shape[0], VT.shape[0]))
np.fill_diagonal(Sigma_matrix, Sigma)

Sigma_matrix = np.zeros((U.shape[0], VT.shape[0]))
np.fill_diagonal(Sigma_matrix, Sigma)

Then, recompose the matrix:

Python

recomposed_svd = np.dot(U, np.dot(Sigma_matrix, VT))

recomposed_svd = np.dot(U, np.dot(Sigma_matrix, VT))

Check if the recomposed matrix recomposed_svd equals the original matrix A:

Python

if np.allclose(recomposed_svd, A):
    print("Verification successful: SVD decomposition and recomposition are correct!")
else:
    print("Verification failed: There is a discrepancy in the decomposed matrices.")

if np.allclose(recomposed_svd, A):
    print("Verification successful: SVD decomposition and recomposition are correct!")
else:
    print("Verification failed: There is a discrepancy in the decomposed matrices.")

The np.allclose() function verifies that the original matrix is accurately reconstructed.

In this lesson, you learned about LU decomposition and Singular Value Decomposition (SVD), essential tools for matrix operations in scientific computing. We walked through the process of decomposing a matrix into its lower, upper triangular, permutation, and singular value matrices. You also verified the decomposition through matrix recomposition to ensure accuracy.

There are other types of matrix decompositions, such as QR decomposition and Cholesky decomposition, but we focused on the most popular and widely used ones. By completing this final lesson, you have equipped yourself with vital techniques employed in numerical analysis and data science. Continue practicing these skills through the upcoming practice exercises and apply them to real-world problems. Congratulations on reaching the end of this comprehensive course on linear algebra with SciPy! Your journey towards mastering computational mathematics begins here.

Introduction to Matrix Decomposition

Understanding LU Decomposition

Performing LU Decomposition with SciPy

Join the 1M+ learners on CodeSignal

Output

Verifying Decomposed Matrices

Introduction to Singular Value Decomposition (SVD)

Output

Verifying Decomposed Matrices (SVD)

Overview, Summary, and Next Steps