Equivalence of Pseudo-Inverse Matrix calculation and SVD (Singular Value Decomposition) decomposition
This paper provides an explanation of the equivalence between the matrix pseudo inverse and the SVD decomposition. The calculation of the pseudo inverse matrix is detailed, as well as the using SVD for that purpose, with highlighting the properties of the U and V matrices.
The matrix pseudo inverse, also known as the Moore-Penrose inverse, is a generalization of the matrix inverse for non-square matrices. It can be computed using the Singular Value Decomposition (SVD) of a matrix, which decomposes a matrix into the product of three matrices:
a unitary matrix,
a diagonal matrix,
and the conjugate transpose of the unitary matrix.
The pseudo inverse of a matrix can then be computed as the product of the inverse of the diagonal matrix and the conjugate transpose of the unitary matrix.
The matrix pseudo inverse can also be calculated using the following formula: (AtA)^-1 At
where A is a matrix and At is its transpose, it represents the least squares solution for linear regression.
The expression (AtA)^-1 At is known as the “normal equations” method for solving the linear least squares problem. This method is based on the fact that if A is a matrix of rank r, then AtA is a positive definite matrix and the normal equations AtA x = At b has a unique solution x, that is the least square solution.
The transpose of A, At, represents the columns of A as rows. Therefore, if we multiply AtA, we are dot-producting each column of A with every other column of A. As a result, we get a symmetric and positive definite matrix, which can be inverted and multiplied by At to get the least square solution.
Pseudo-inverse and SVD equivalence:
The Singular Value Decomposition (SVD) of a matrix A is a factorization of A into the product of three matrices: A = UΣV^T, where U and V are unitary matrices and Σ is a diagonal matrix with non-negative real numbers on the diagonal, called the singular values of A.
The matrices U and V in the Singular Value Decomposition (SVD) of a matrix A have several properties:
U and V are both unitary matrices, meaning that their inverse is equal to their conjugate transpose. This means that U^TU = I and V^TV = I, where I is the identity matrix.
The columns of U are the left-singular vectors of A and the columns of V are the right-singular vectors of A. These vectors are orthonormal, meaning that they are normalized and mutually orthogonal.
The rank of A is equal to the number of non-zero singular values of A. The rank of A can also be determined from the number of non-zero columns of U or V.
The range of A is equal to the column space of U, and the null space of A is equal to the column space of V.
The matrix UΣV^T is a polar decomposition of A, meaning that it gives the closest possible factorization of A into the product of a unitary matrix and a positive semi-definite matrix.
U and V can be used to diagonalize A-related matrices, such as A^T A and AA^T.
In order show the equivalence between SVD and (A^T A)^-1 A^T, we can start by using the SVD of A: A = UΣV^T.
We can then find A^T A = (UΣV^T)^T (UΣV^T) = VΣ^TU^T UΣV^T = VΣ²V^T, which is a diagonal matrix with Σ² on the diagonal.
Then we can find the inverse of A^T A as (VΣ²V^T)^-1 = VΣ^-2V^T, where Σ^-2 is the diagonal matrix with 1/σ² on the diagonal, for each non-zero σ.
Next, we can multiply this with A^T on the right: (A^T A)^-1 A^T = VΣ^-2V^T A^T = VΣ^-1V^T, where Σ^-1 is the diagonal matrix with 1/σ on the diagonal, for each non-zero σ.
Now, we can see that the result of this multiplication is the same as the result of the Moore-Penrose pseudo inverse of A, which is defined as A^+ = VΣ^-1U^T.
Therefore we can conclude that solving A x = b for x using the method of normal equations (A^T A)^-1 A^T is equivalent to solving the same problem using the SVD of A and the Moore-Penrose pseudo inverse A^+ = VΣ^-1U^T.
In summary, U and V are unitary matrices that contain the information about the singular values and the left and right singular vectors of A. They can be used to understand the properties of A and related matrices, as well as to perform useful computations.
Python code to illustrate the equivalence:
Pseudo inverse calculation:
import scipy as sp
A = np.array([[1, 2], [3, 4], [5, 6]]) # Define the matrix A not square so no inverse, only pseudo-inverse exists
print(A)
A_pinv = np.linalg.pinv(A) # calculate directly the Moore-Penrose pseudo-inverse matrix
print(A_pinv)
At = np.transpose(A)
print (At)
ainv = np.linalg.pinv(np.dot(At,A))
Apsa = np.dot(ainv,At)
print(Apsa)
Matrix A:
[[1 2]
[3 4]
[5 6]]
Inverse of A:
[[-1.33333333 -0.33333333 0.66666667]
[ 1.08333333 0.33333333 -0.41666667]]
Transpose of A:
[[1 3 5]
[2 4 6]]
Pseudo-Inverse (same as inverse as above)
[[-1.33333333 -0.33333333 0.66666667]
[ 1.08333333 0.33333333 -0.41666667]]SVD decomposition:
import numpy as np
from scipy.linalg import svd
# create an example matrix A
A = np.array([[1, 2], [3, 4], [5, 6]])
# Perform SVD decomposition
U, s, VT = svd(A)
# Compute the reconstructed matrix from the decomposition
S = np.zeros((U.shape[0], VT.shape[0]))
S[:VT.shape[0], :VT.shape[0]] = np.diag(s)
A_reconstructed = U @ S @ VT
print("Singular values: ", s)
print("U matrix: \n", U)
print("V^T matrix: \n", VT)
print("Reconstructed matrix: \n", A_reconstructed)
Singular values: [9.52551809 0.51430058]
U matrix:
[[-0.2298477 0.88346102 0.40824829]
[-0.52474482 0.24078249 -0.81649658]
[-0.81964194 -0.40189603 0.40824829]]
V^T matrix:
[[-0.61962948 -0.78489445]
[-0.78489445 0.61962948]]
Reconstructed matrix:
[[1. 2.]
[3. 4.]
[5. 6.]]SVD and pseudo-inverse calculation:
import numpy as np
from scipy.linalg import svd
# create an example matrix A
A = np.array([[1, 2], [3, 4], [5, 6]])
# Perform SVD decomposition
U, s, VT = svd(A)
# Compute the inverse of the diagonal matrix `S`
S_inv = np.zeros((VT.shape[0], U.shape[0]))
S_inv[:s.shape[0], :s.shape[0]] = np.diag(1/s)
# Compute the inverse of A using SVD decomposition
A_inv = VT.T @ S_inv @ U.T
print("Inverse of A matrix: \n", A_inv)
Inverse of A matrix:
[[-1.33333333 -0.33333333 0.66666667]
[ 1.08333333 0.33333333 -0.41666667]]References:
- “Matrix Computations” by Gene H. Golub and Charles F. Van Loan.
- “The Singular Value Decomposition (SVD) and Its Applications” by J. Leskovec, A. Rajaraman, J. Ullman, available online at https://cs.stanford.edu/~ullman/mmds/ch9.pdf
- “A Survey of Pseudo-Inverse Solutions to Linear Systems” by Daniele Moroni, available online at https://arxiv.org/abs/1709.10354