Pseudo-Inverse and Projection Matrix
Pseudo-inverse and projection matrices are often used in recommendation systems, so let’s make a note of them.
GitHub
- You can find the files in Jupyter notebook format here .
Google Colaboratory
- If you want to execute on Google Colaboratory, click here .
Author’s Environment
The author’s OS is macOS. The options differ from Linux and Unix commands.
!sw_vers
ProductName: Mac OS X
ProductVersion: 10.14.6
BuildVersion: 18G103
!python -V
Python 3.8.5
Let’s import the basic libraries and check their versions, including Keras.
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
import matplotlib
import matplotlib.pyplot as plt
import scipy
import numpy as np
import pandas as pd
print('matplotlib version :', matplotlib.__version__)
print('scipy version :', scipy.__version__)
print('numpy version :', np.__version__)
matplotlib version : 3.3.2
scipy version : 1.3.1
numpy version : 1.19.2
Calculating Pseudo-Inverse
Not all matrices have an inverse. In such cases, we can’t solve systems of equations like $Ax=b$.
Hence, we define the pseudo-inverse.
$$ A^{+}=\left(A^{T} A\right)^{-1} A^{T} $$
By multiplying $A^{+}$ from the left, we get:
$$ A^{+}A=\left(A^{T} A\right)^{-1} A^{T}A=I $$
And then, it becomes possible to calculate $x$.
A = np.arange(25).reshape((5,5))
A
array([[ 0, 1, 2, 3, 4],
[ 5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]])
Let’s calculate the rank of this matrix.
np.linalg.matrix_rank(A)
2
Since it’s 2, we can’t calculate the inverse.
np.linalg.inv(A)
---------------------------------------------------------------------------
LinAlgError Traceback (most recent call last)
<ipython-input-6-ae645f97e1f8> in <module>
----> 1 np.linalg.inv(A)
<__array_function__ internals> in inv(*args, **kwargs)
~/anaconda3/lib/python3.8/site-packages/numpy/linalg/linalg.py in inv(a)
544 signature = 'D->D' if isComplexType(t) else 'd->d'
545 extobj = get_linalg_error_extobj(_raise_linalgerror_singular)
--> 546 ainv = _umath_linalg.inv(a, signature=signature, extobj=extobj)
547 return wrap(ainv.astype(result_t, copy=False))
548
~/anaconda3/lib/python3.8/site-packages/numpy/linalg/linalg.py in _raise_linalgerror_singular(err, flag)
86
87 def _raise_linalgerror_singular(err, flag):
---> 88 raise LinAlgError("Singular matrix")
89
90 def _raise_linalgerror_nonposdef(err, flag):
LinAlgError: Singular matrix
An error occurs and it terminates.
We can compute the pseudo-inverse using numpy’s pinv.
np.linalg.pinv(A).round(3)
array([[-0.144, -0.092, -0.04 , 0.012, 0.064],
[-0.076, -0.048, -0.02 , 0.008, 0.036],
[-0.008, -0.004, -0. , 0.004, 0.008],
[ 0.06 , 0.04 , 0.02 , 0. , -0.02 ],
[ 0.128, 0.084, 0.04 , -0.004, -0.048]])
Now, we can calculate it.
Projection Matrix
A projection matrix is defined as follows.
$$ P^{2}=P $$
Once points on a vector space are transformed (rotated or moved) by $P$, they cannot be further moved.
$$ P^{N}=P $$
This is because it holds true for $N$ times.
Spectral Decomposition
Let $A$ be a Hermitian matrix, and let’s perform eigenvalue decomposition. $u_i$ is an eigenvector, and $\lambda_i$ is an eigenvalue.
$$ A=U \Lambda U^{T} \equiv\left[u_{1}, \ldots, u_{n}\right] \operatorname{diag}\left(\lambda_{1}, \ldots, \lambda{n} \right)\left[\begin{array}{c} u_{1}^{T} \\ \vdots \\ u_{n}^{T} \end{array}\right] $$
Thus,
$$ A = \sum_{i} \lambda_i u_i u_i^T $$
We can decompose $A$ into a sum of projection matrices onto eigenspaces weighted by eigenvalues. This is called spectral decomposition, and it represents a form of decomposition that frequently arises in recommendation systems.
Summary
We’ve summarized pseudo-inverse and projection matrices. Since there are still many things I don’t understand, I’ll add more as needed.