Moore-Penrose Pseudoinverse

Generalization of the inverse of a matrix.

I believe, we pay too much attention to implementation, and too less
attention in the study of the concept that is implemented. I have been
on then teams of many Data Science and Machine Learning projects, and
I would always reiterate on one simple idea; that is, “If you do not
know the math, you don’t know it at all.”

This is a piece of philosophy I deeply believe in. With the advent of packages like numpy, matplotlib, scikit-learn etc., implementing a machine learning model with a moderately difficult data set and problem is fairly simple.
The magic then stays in being able to tweak the algorithm and getting something new (or weird) out of the model. And, for you to be capable of doing so, you will have to know the mechanism behind it.
The Moore-Penrose pseudoinverse in the soul of PCA (Principal Component Analysis), one of the most popularly used Dimensionality reduction techniques.

---

How do we define the inverse of a matrix?
Provided that the matrix is a square matrix and non-singular, we simple divide the adjoint of the matrix with its determinant.
Mathematically, for $A_{m \times m}$ and $|A| \neq 0$, the inverse of $A$ is defined as,
$$A^{-1} = \frac{ \text{adj.} A}{|A|} \tag*{(1)}$$

---

Of course, the above method is computationally very expensive. Hence, we can get the inverse of the matrix recursively using the Fadeev-LeVerrier equation ( Read about that in this blog of mine).

---

Now, how do we deal with matrices that are non-square? How do you find the inverse of a matrix that looks like this,
$$B = \begin{bmatrix} x_{11} & x_{13} \\ x_{21} & x_{23}\\ x_{d1} & x_{d3} \end{bmatrix}_{3\times 2}$$
This is where the Generalization of inverse of a matrix happens, named the Moore-Penrose Pseudoinverse.

---

For every $A_{m \times n}$, there exists a pseudoinverse $A^{\dagger}_{n \times m}$. ( $A^\dagger$ is read as “A dagger”).
$A^{\dagger}$ is mathematically defined as,
$$A^{\dagger}=(A^{T}A)^{-1}A^{T} \tag*{(2)}$$
This is dimensionally consistent. Please check and verify.

---

Now, say we have,
$$Q = \begin{bmatrix} 1 \\ 2 \end{bmatrix}$$
It is impossible to find $Q^{-1}$ by the conventional method $(1)$. So, we use the Generalized Inverse at $(2)$.
So,
$$Q^{T} = \begin{bmatrix} 1 && 2 \end{bmatrix}$$
So, $Q^{T}Q$ comes out to be $[5]_{1 \times 1}$. So, $(Q^{T}Q)^{-1}$ comes out to be $\frac{1}{5}$.
Hence,
$$Q^{\dagger}=(Q^{T}Q)^{-1}Q^{T} =\frac{1}{5} \begin{bmatrix} 1 && 2 \end{bmatrix} = \begin{bmatrix} \frac{1}{5} && \frac{2}{5} \end{bmatrix}$$ which is the pseudoinverse or the generalized inverse.

---

For a square matrix (i.e., $m \times m$),
$$A^{\dagger}=A^{-1}$$
In detail,
$$(A^{T}A)^{-1}A^{T}=\frac{\text{adj. A}}{|A|}$$

---

Some properties of the generalized inverse are,
1. $AA^{\dagger}A=A$
2. $A^{\dagger}AA^{\dagger}=A^{\dagger}$
3. $(AA^{\dagger})=AA^{\dagger}$
One important point to remember is, $A^{\dagger}$ always exists and is unique.

---

Cheers!

Multiplication Algorithms.

I am presently enrolled in a course named Computational Techniques in Control Engineering. The Syllabus is Math extensive and we are expected to be pretty fluent in programming too; which is a great combination.
The course is handled by Professor A Ramakalyan.
The syllabus is as follows,

More details about it can be found at the website of National Institute of Technology, Trichy | Academic Curriculum | Instrumentation and Control Engineering.
So, there was one class in which he concluded the class with a detailed derivation of Gram-Schmidt Orthogonalization process.
And then he asks us what is the product of $a + ib$ and $c + id$, so with the basic grade school polynomial multiplication skill that we all have, we can easily look into the following,
$(a+ib) \times (c+id)$
$= a(c+id) + ib(c+id)$
$=ac + iad + ibc + i^{2}bd$
$=(ac-bd) + i(ad + bc)$

Note : $i^{2} = -1$

It was simple and straight forward, which was highly unlikely to happen in a course taken by that particular teacher.
He asked us to find out the number of multiplications that we involved in finding the above product.
It is clear that, there are 4 multiplications. He then asked us to do find the same product using 3 multiplications!
This is where the level of awesomeness hits so high that it almost looks CRAZY!
As soon as I got back to the room, I started Googling and looked at some random research papers and stuff.
Hence this blog post.
In this blog post, we will briefly study the essence of Multiplication Algorithms; we will study the Karatsuba Algorithm in detail. We will also see the answer to the mind blowing question by Ramakalyan Sir.

---

Karatsuba Algorithm.

The usual grade school style of multiplication takes around $\Theta(n^{2})$ time. Karatsuba is his paper “A. Karatsuba and Yu. Ofman (1962). “Multiplication of Many-Digital Numbers by Automatic Computers”. Proceedings of the USSR Academy of Sciences. 145: 293–294. Translation in the academic journal Physics-Doklady, 7 (1963), pp. 595–596”, presented that this multiplication can be done faster; in $\Theta( n^{log_{2}3}) \approx \Theta(n^{1.584963})$.
This number might seem pretty insignificant, but in cases where we tackle very very large multiplication problems, this works wonders.
I was looking into stack-overflow for a proper explanation while I found this answer. Let us look briefly into it,
$(a+ib) \times (c+id) = (ac-bd) + i(ad + bc)$
Let, $m = ac-bd$ and $n = ad+bc$
We are concerned with two numbers basically, $(ac-bd)$ and $(ad+bd)$.
Now, we compute three multiplications, $x = ac$, $y = bd$, and $z= (a+b)(c+d)$.
Now,
$m = x -y$
and, $n = z - x - y$.
This is how the Karatsuba Algorithm works.
To keep stuff in perspective, let us consider an example, where two $1024$-digit numbers are multiplied. [$n = 1024 = 2^{10}$].
As per the classical multiplication algorithm, it will required, $n^{2}$ single multiplications, that means, $2^{20}$ multiplications; however by the Karatsuba Algorithm, this number can be reduced to $2^{10log_{2}3} = 2^{log_{2}3^{10}} = 3^{10}$ single multiplications. And, if you look into the values of $3^{10}$ and $2^{20}$, you will see that the latter is much much greater than the former.
Karatsuba algorithm was the first algorithm to be faster or better than the traditional multiplication algorithm that took a quadratic time.

---

Side note:

We must also consider the Gauss Complex Multiplication algorithm. It precise speaks of the $(a+ib) \times (c+id)$ problem.
This also works by decreasing the number of multiplications and increasing the number of additions and subtractions.
For the $(a+ib) \times (c+id)$,
we find,
$x = c.(a+b)$
$y = a.(d-c)$
$z = b.(c+d)$
Finally the real part,
$Re((a+ib) \times (c+id)) = x-z$
$Im((a+ib) \times (c+id)) = x + y$
if we look at the traditional method, we will see that we use $1$ subtraction, and $2$ addition. However, in this method, we use $3$ additions and $2$ subtractions.

---

Cheers!