Pseudo-inverse and projection matrices

Pseudo-inverse and projection matrices are also often used in recommendation systems, so I’ll make a note of them.

github

  • The file in jupyter notebook format is here.

google colaboratory

  • If you want to run it in google colaboratory here

Author’s environment

The author’s OS is macOS, and the options are different from Linux and Unix commands.

!sw_vers
ProductName: Mac OS X
ProductVersion: 10.14.6
BuildVersion: 18G103
Python -V
Python 3.8.5

Import the basic libraries and keras and check their versions.

%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

Compute the pseudo-inverse matrix

An ordinary matrix does not always have an inverse. In that case, the simultaneous equation, .

$$ Ax=b $$

is not possible.

So we define a pseudo-inverse matrix.

$$ A^{+}=\left(A^{T} A\right)^{-1} A^{T} $$

If we multiply this $A^{+}$ by the left and proceed with the calculation, we get

$$ A^{+}A=\left(A^{T} A\right)^{-1} A^{T}A=I $$

and $x$ can be calculated.

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]])

Compute the rank of this matrix.

np.linalg.matrix_rank(A)
2

2, so we can’t compute the inverse matrix.

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

You will get an error and exit.

The pseudo-inverse can be computed with 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]])

The result can be calculated as follows.

Projection matrix

The projection matrix is defined as follows.

$$ P^{2}=P $$

It means that once a point in vector space has been linearly transformed (rotated or moved) by $P$, it cannot be moved any further.

$$ P^{N}=P $$

This is because.

Spectral decomposition

Let $A$ be a Hermitian matrix and perform eigenvalue decomposition. Let $u_i$ be an eigenvector and $\lambda_i$ be 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 $$

which can be decomposed as

$U$ is a unitary matrix.

$$ U^TU=I $$

is valid. Here, $U_i U_i^T$ is a

$$ (u_i u_i^T)^2 = u_i u_i^Tu_i u_i^T = u_i u_i^T $$

and is a projection matrix into eigenspaces. Therefore

$$ A = \sum_{i} \lambda_i u_i u_i^T $$

can be decomposed into a matrix called $A$ that is a projection matrix onto the eigenspace, summed with the eigenvalues as weights. This is called spectral decomposition, and it is a form of decomposition that comes up in various situations in recommendation systems.

Summary

This is a summary of the pseudo-inverse and projection matrices. There are still many things that I do not understand, so I will add more information as needed.