Logistic Regression using R - How to handle class bias?

Doing this blog as a revision into some primitive topics in Machine Learning.

Since, almost all my current work is done using R, I will implement logistic regression using this language.

We will be using adult data set. After all is set, now we dive straight into the code. Further explanations shall not be provided as most of the code is self-explanatory in nature.

> idata <- read.csv("adult_csv.csv")

> summary(idata)

      age                   workclass         fnlwgt               education     education.num  
 Min.   :0.000   Private         :33906   Min.   :  12285   HS-grad     :15784   Min.   : 1.00  
 1st Qu.:1.000   Self-emp-not-inc: 3862   1st Qu.: 117551   Some-college:10878   1st Qu.: 9.00  
 Median :2.000   Local-gov       : 3136   Median : 178145   Bachelors   : 8025   Median :10.00  
 Mean   :1.771                   : 2799   Mean   : 189664   Masters     : 2657   Mean   :10.08  
 3rd Qu.:3.000   State-gov       : 1981   3rd Qu.: 237642   Assoc-voc   : 2061   3rd Qu.:12.00  
 Max.   :4.000   Self-emp-inc    : 1695   Max.   :1490400   11th        : 1812   Max.   :16.00  
                 (Other)         : 1463                     (Other)     : 7625                  
               marital.status            occupation            relationship                   race      
 Divorced             : 6633   Prof-specialty : 6172   Husband       :19716   Amer-Indian-Eskimo:  470  
 Married-AF-spouse    :   37   Craft-repair   : 6112   Not-in-family :12583   Asian-Pac-Islander: 1519  
 Married-civ-spouse   :22379   Exec-managerial: 6086   Other-relative: 1506   Black             : 4685  
 Married-spouse-absent:  628   Adm-clerical   : 5611   Own-child     : 7581   Other             :  406  
 Never-married        :16117   Sales          : 5504   Unmarried     : 5125   White             :41762  
 Separated            : 1530   Other-service  : 4923   Wife          : 2331                             
 Widowed              : 1518   (Other)        :14434                                                    
     sex         capitalgain      capitalloss      hoursperweek         native.country    class      
 Female:16192   Min.   :0.0000   Min.   :0.0000   Min.   :0.000   United-States:43832   <=50K:37155  
 Male  :32650   1st Qu.:0.0000   1st Qu.:0.0000   1st Qu.:2.000   Mexico       :  951   >50K :11687  
                Median :0.0000   Median :0.0000   Median :2.000                :  857                
                Mean   :0.2003   Mean   :0.1149   Mean   :1.951   Philippines  :  295                
                3rd Qu.:0.0000   3rd Qu.:0.0000   3rd Qu.:2.000   Germany      :  206                
                Max.   :4.0000   Max.   :4.0000   Max.   :4.000   Puerto-Rico  :  184                
                                                                  (Other)      : 2517  

> head(idata)

  age        workclass fnlwgt education education.num     marital.status        occupation  relationship  race
1   2        State-gov  77516 Bachelors            13      Never-married      Adm-clerical Not-in-family White
2   3 Self-emp-not-inc  83311 Bachelors            13 Married-civ-spouse   Exec-managerial       Husband White
3   2          Private 215646   HS-grad             9           Divorced Handlers-cleaners Not-in-family White
4   3          Private 234721      11th             7 Married-civ-spouse Handlers-cleaners       Husband Black
5   1          Private 338409 Bachelors            13 Married-civ-spouse    Prof-specialty          Wife Black
6   2          Private 284582   Masters            14 Married-civ-spouse   Exec-managerial          Wife White
     sex capitalgain capitalloss hoursperweek native.country class
1   Male           1           0            2  United-States <=50K
2   Male           0           0            0  United-States <=50K
3   Male           0           0            2  United-States <=50K
4   Male           0           0            2  United-States <=50K
5 Female           0           0            2           Cuba <=50K
6 Female           0           0            2  United-States <=50K

Checking class bias now, on column class,

> table(idata$class)

<=50K  >50K 
37155 11687

There is a class bias, a condition observed when the proportion of one event is much smaller than proportion of other event.
Thus, we must sample the observations in approximately equal proportions to get better models.

CREATING TRAINING AND TESTING SAMPLES

#training data
input_ones <- idata[which(idata$class == ">50K"), ]  # all <=50k values
input_zeros <- idata[which(idata$class == "<=50K"), ]  # all <=50k values
set.seed(100)  # for repeatability of samples
input_ones_training_rows <- sample(1:nrow(input_ones), 0.7*nrow(input_ones))  # >50k values for training
input_zeros_training_rows <- sample(1:nrow(input_zeros), 0.7*nrow(input_ones))  # <=50k values training. 
training_ones <- input_ones[input_ones_training_rows, ]  
training_zeros <- input_zeros[input_zeros_training_rows, ]
trainingData <- rbind(training_ones, training_zeros)  # row bind  

# Create Test Data
test_ones <- input_ones[-input_ones_training_rows, ]
test_zeros <- input_zeros[-input_zeros_training_rows, ]
testData <- rbind(test_ones, test_zeros)  # row bind 

One simple optional step is to create Weight of Evidence (WOE) for categorical variables.
This is a very simple, yet useful method - Read more here.

idata_woe <- idata
str(idata_woe)

table(idata_woe$class)

library(car)
library(dplyr)

idata_woe$class <- dplyr::recode(idata_woe$class,"<=50K" = 0,">50K" = 1)
#idata_woe$class <- car::recode(idata_woe$class,"<=50K" = 0,">50K" = 1) - this is not working
idata_woe

i <- 10
q <- quantile(idata_woe$class,
              probs = c(1:(i-1)/i),
              na.rm = TRUE,
              type=3)
cuts <- unique(q)


WOE_Class <- table(findInterval(idata_woe$class,vec = cuts,rightmost.closed = FALSE),idata_woe$class)
WOE_Class <- as.data.frame.matrix(WOE_Class)
WOE_Class$`0`<-rowSums(WOE_Class)
WOE_Class$WOE <- log((WOE_Class$`1`*sum(WOE_Class$`0`))/(WOE_Class$`0`*sum(WOE_Class$`1`)))

> WOE_Class
      0     1      WOE
1 37155     0     -Inf
2 11687 11687 1.430113

Now that we have already calculated WOE, it is only logical that we calculate the Information Value (IV) also,

library(scorecard)

iv(idata_woe, y="class")

> iv(idata_woe, y="class")
          variable info_value
 1:   relationship 1.52771659
 2: marital.status 1.34867700
 3:            age 0.89506214
 4:    capitalgain 0.89314987
 5:     occupation 0.76787908
 6:      education 0.73690518
 7:  education.num 0.73690518
 8:   hoursperweek 0.40824961
 9:         fnlwgt 0.33755308
10:            sex 0.30052143
11:      workclass 0.17056215
12:    capitalloss 0.11592250
13: native.country 0.07509682
14:           race 0.06784214

Now, we have the information value (meaning the strength of relation between “class” and other parameters.
We now start building the logistic regression model,

logitMod <- glm(class ~ relationship + age + capitalgain + occupation + education.num, data=trainingData, family=binomial(link="logit"))
predicted <- plogis(predict(logitMod, testData))  # predicted scores
# or
predicted <- predict(logitMod, testData, type="response")  # predicted scores
summary(logitMod)

Result is as follows,

> summary(logitMod)

Call:
glm(formula = class ~ relationship + age + capitalgain + occupation + 
    education.num, family = binomial(link = "logit"), data = trainingData)

Deviance Residuals: 
    Min       1Q   Median       3Q      Max  
-3.3583  -0.5408   0.0015   0.6281   3.3139  

Coefficients:
                            Estimate Std. Error z value Pr(>|z|)    
(Intercept)                 -4.43416    0.18263 -24.280  < 2e-16 ***
relationshipNot-in-family   -2.26671    0.05846 -38.776  < 2e-16 ***
relationshipOther-relative  -2.52271    0.19614 -12.862  < 2e-16 ***
relationshipOwn-child       -3.43974    0.14067 -24.452  < 2e-16 ***
relationshipUnmarried       -2.66316    0.09625 -27.670  < 2e-16 ***
relationshipWife             0.31766    0.09130   3.479 0.000503 ***
age                          0.34161    0.02041  16.734  < 2e-16 ***
capitalgain                  0.95230    0.03972  23.974  < 2e-16 ***
occupationAdm-clerical       1.08011    0.13682   7.895 2.91e-15 ***
occupationArmed-Forces       2.89421    1.34843   2.146 0.031844 *  
occupationCraft-repair       1.29746    0.13042   9.949  < 2e-16 ***
occupationExec-managerial    2.08246    0.13025  15.988  < 2e-16 ***
occupationFarming-fishing    0.23595    0.17661   1.336 0.181539    
occupationHandlers-cleaners  0.58579    0.18067   3.242 0.001185 ** 
occupationMachine-op-inspct  0.83323    0.14885   5.598 2.17e-08 ***
occupationOther-service      0.16679    0.16294   1.024 0.306012    
occupationPriv-house-serv   -0.02904    0.74544  -0.039 0.968925    
occupationProf-specialty     1.70451    0.13280  12.836  < 2e-16 ***
occupationProtective-serv    1.72939    0.17889   9.667  < 2e-16 ***
occupationSales              1.56500    0.13284  11.781  < 2e-16 ***
occupationTech-support       1.48003    0.16098   9.194  < 2e-16 ***
occupationTransport-moving   1.21363    0.14650   8.284  < 2e-16 ***
education.num                0.29476    0.01128  26.127  < 2e-16 ***
---
Signif. codes:  0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1

(Dispersion parameter for binomial family taken to be 1)

    Null deviance: 22680  on 16359  degrees of freedom
Residual deviance: 13115  on 16337  degrees of freedom
AIC: 13161

Number of Fisher Scoring iterations: 6

Cheers!

Markov Chains - A Mathematical Treatise

Markov Chains

We have a set of stated, $\mathcal{S}$ = {${s_1, s_2, ..., s_m}$}. A Markov process starts in one of these states and moves successively from one state to another. Each move is called a step . If the chain is currently in state $s_i$, then it moves to state $s_j$ at the next step with a probability denoted by $p_{ij}$, and this probability does not depend upon which states the chain was in before the current state.These probabilities $p_{ij}$ are called transition probabilities. The process can remain in the state it is in, and this occurs with probability $p_{ii}$ . Initially a probability is defined by specifying a particular state as the starting state.

Say, we stay in Patna (Capital of the State of Bihar, India), and at my home we usually eat either Roti ($\text{Ro}$), Rice ($\text{Ri}$), Parantha ($\text{Pa}$)) or Bread ($\text{Br}$) for dinner. There are also some days when we eat one particular dinner on two or three or more consecutive days.

Now, we define transition probabilities of using a Transition Matrix which is given as,
$$\text{T}=\begin{array}{c c} & \begin{array}{c c c} \text{Ri} & \text{Ro} & \text{Pa} & \text{Br} \\ \end{array} \\ \begin{array}{c c c} \text{Ri} \\ \text{Ro} \\ \text{Pa} \\ \text{Br}\\ \end{array} & \left[ \begin{array}{c c c} \frac{1}{2} & \frac{1}{4} & \frac{1}{4} & 0 \\ 0 & \frac{1}{4} & \frac{1}{4} & \frac{1}{2} \\ 0 & \frac{1}{2} & \frac{1}{4} & \frac{1}{4} \\ \frac{1}{2} & 0 & \frac{1}{4} & \frac{1}{4} \\ \end{array} \right] \end{array}$$
From the above matrix, it can be seen that $P_{(Rice \implies Rice)}=\frac{1}{2}$ and similarly, $P_{(Roti \implies Parantha)}=\frac{1}{4}$.

In the similar lines of the above concept, a Transition Diagram can also be drawn.

Let us dig further into the concept now. Imagine today we eat Rice at home and two days from today we eat Bread. This is written as $P^{2}_{(Rice \implies Bread)}$. We see that if we ate Rice today then the event of us eating Bread two days from today is a disjoint union of the following,

1. We ate Rice tomorrow and Bread day after.
2. We ate something else tomorrow and Bread day after.
3. We ate Bread tomorrow and Bread day after.

Therefore, we can write $P^{2}_{(Rice \implies Bread)}$ as ,
$$P^{2}_{(Rice \implies Bread)} = [P_{(Rice \implies Rice)}]\cdot[P_{(Rice \implies Bread)}]+[P_{(Rice \implies Roti)}]\cdot[P_{(Roti \implies Bread)}]+ \\ [P_{(Rice \implies Parantha)}]\cdot[P_{(Parantha \implies Bread)}]+[P_{(Rice \implies Bread)}]\cdot[P_{(Bread \implies Bread)}]$$
The has pointed towards a more generalized concept of Dot product of two vectors.

Considering there are $r$ states in the Markov chain,
$$P^{2}_{ij}=\sum_{k=1}^{r}P_{ik}P_{kj}$$
This study was for $n=2$ , meaning we are yet to define this in a more generalized manner. Obviously, looking at the present scenario of high-end computing software packages available, this attempt seems to be a waste of efforts, but then knowing the math is always good fun!

Before doing that, we will again go into the basic definition as defined above and try to make an iterative approach into the problem.

We have assumed that our meal starts at state Rice, so, for us,
$$\text{p}_0=\begin{bmatrix} 1 \\ 0 \\ 0 \\ 0\\ \end{bmatrix}$$
$\text{p}_0$ is the state of our system at $0^{th}$ state or the beginning of the system.

Similarly, if we want to find $\text{p}_1$ we will do it as,
$$\text{p}_1 = \text{T} \cdot \text{p}_0$$
In the similar lines,
$$\boxed{\text{p}_5 = \text{T} \cdot \text{p}_4 = \text{T}^{2} \cdot \text{p}_3 = \text{T}^3 \cdot \text{p}_2 = \text{T}^4 \cdot \text{p}_1 = \text{T}^{5} \cdot \text{p}_0}$$
This means, for generalization’s sake,
$$\text{p}_n = \text{T}^{n}\cdot \text{p}_0$$
Using some very basic Linear Algebra methods to compute $\text{T}^n$,

Recall : $\text{T}=\mathcal{u}\cdot D \cdot\mathcal{u}^{-1}$

Here, $D$ is a Diagonal matrix and $\mathcal{u}$ is a matrix whose columns correspond to the Eigen-vectors of $\text{T}$.

I leave the computation to your own practice.

There for,
$$\text{T}^n = \mathcal{u} \cdot D^n . \mathcal{u}^{-1}$$
Since, $D$ is a diagonal matrix, which is obviously of form,
$$D = \begin{bmatrix} a & 0 & 0 & 0 \\ 0 & b & 0 & 0 \\ 0 & 0 & c & 0 \\ 0 & 0 & 0 & d \end{bmatrix}$$
Therefore, $D^n$ will be,
$$D = \begin{bmatrix} a^n & 0 & 0 & 0 \\ 0 & b^n & 0 & 0 \\ 0 & 0 & c^n & 0 \\ 0 & 0 & 0 & d^n \end{bmatrix}$$
Hence, we can easily compute $T^n$.

The Python implementation of this concept is relatively simple once we understand the math behind it.

All the best with that.

Cheers!

Resources:

1. Matrix Diagonalization

2. Eigen Values and Eigen Vectors

3. Markov Chains

4. Markov Chains

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!

Preparation of exam.

Preparation Notes - Hell lot of Math and Algorithms; very helpful.

Note : These notes are made during my preparation for my exams. They might be crude and may not be in their best form of presentation. Read at your own risk.

---

Subject : IC 021 - Computational Techniques in Control Engineering

Professor : Dr. A Ramakalyan.

Difficulty : Runs to Heavens and goes around it $\infty$ times.

Books:
1. B N Datta’s Numerical Methods for Linear Control Systems. - referenced as [1]
2. Gilbert Strang’s Linear ALgebra and it’s applications. - referenced as [2]
3. S Kumaresen’s Linear Algebra - A Geometric Approach. - referenced as [3]

---

1. Computing $e^\mathcal{A}$[1]

1. There are many ways of doing this, one of the very popular one is the Taylor Series method.
   We simply expand $e^\mathcal{A}$ as per the Taylor series.
   Hence, $e^\mathcal{A}$ can be written as,
   $$\boxed{e^\mathcal{A} = I + \mathcal{A} + \frac{\mathcal{A}^{2}}{2!} + \frac{\mathcal{A^3}}{3!} + ...}$$

   • The drawbacks to this method are that a large number of terms is needed for convergence, and even when convergence occurs, the answer can be totally wrong.

2. Hence, I will now get into the Pade’s Scaling and Squaring algorithm for this task.
   Suppose that, $f(x)$ is a power series presented as,
   $$f(x) = f_0 + f_1 x+ f_2 x^2+...$$
   Then the Pade’s Scaling and Squaring Algorithm, given an approximation of $f(x)$ as ,
   $$\boxed{f(x) \approx \frac{c(x)}{d(x)}= \frac{\sum_{k=0}^p c_{k} x^{k}}{\sum_{k=0}^q d_{k} x^{k}}}$$
   The $c_k$ and $d_k$ are chosen such that the terms containing $x^0, x^1, x^2,...,x^{p+q}$ are cancelled out in $f(x)d(x) - c(x)$. The order of Pade’s approximation is $p+q$. The ratio $(\frac{c(x)}{d(x)})$ is unique and the coefficients $c_0, c_1,...,c_p$ and $d_0, d_1,...,d_q$ always exist.
   
   Similarly, Pade’s approximation for $e^\mathcal{A}$ is given by,
   $$\boxed{R_{pq}(\mathcal{A}) = [D_{pq}(\mathcal{A})]^{-1}N_{pq}(\mathcal{A})}$$
   Where,
   $$\boxed{D_{pq}(\mathcal{A})=\sum_{k=0}^q\frac{(p+q-j)!q!}{(p+q)!j!(q-j)!}(-\mathcal{A})^{j}}$$
   and
   $$\boxed{N_{pq}(\mathcal{A})=\sum_{k=0}^p\frac{(p+q-j)!p!}{(p+q)!j!(p-j)!}(\mathcal{A})^{j}}$$

   • It can be shown (Exercise 5.16) that if p and q are large, or if A is a matrix having all its eigenvalues with negative real parts, then $D_{pq}(\mathcal{A})$ is nonsingular.
   • The difficulty of Round off errors in Pade’s method can be controlled by Scaling and squaring.
   • Since $e^\mathcal{A}$ is same as $(e^\frac{\mathcal{A}}{m})^m$, the idea is it to find out $m$ in terms of powers of $2$ so that $e^\frac{\mathcal{A}}{m}$ can be computed accurately and then find $(e^\frac{\mathcal{A}}{m})^m$ with repetitive squaring.
   • This method has favorable numerical properties when $p=q$.
     
     Let $m = 2^j$ be chosen such that $||A||_{\infty} \leq 2^{j-1}$, then Moler and Van Loan(1978) have shown that there exists an $E$ such that ,
     $$\boxed{[R_{pp}(A/2^j)]^{2^j} = e^{\mathcal{A} + E}},$$
     Where $||E||_{\infty} \leq \epsilon ||\mathcal{A}||_{\infty}$, with
     $$\epsilon = 2^{3-2p} (\frac{(p!)^2}{(2p)!(2p+1)!)}) \\ \boxed{\epsilon = \frac{8}{2^{2p}} (\frac{(p!)^2}{(2p)!(2p+1)!)})}$$
     Given an error tolerance of $\delta$ we should choose $p$ such that $||E||_{\infty} \leq \delta ||\mathcal{A}||_{\infty}$
     
     The Algorithm is as follows:
     Input : $A \in \mathcal{R}^{n \times n}$, $\delta > 0$
     Output : $F = e^{\mathcal{A} + E}$ with $||E||_{\infty} \leq \delta ||\mathcal{A}||_{\infty}$
     
     Step 1: Choose $j$ such that $||\mathcal{A}||_{\infty} \leq 2^{j-1}$, set $\mathcal{A} \equiv \mathcal{A}/2^j$.
     Step 2: Choose $p>0$ and smallest non-negative integer satisfying,
     $$\boxed{(\frac{8}{2^{2p}}) (\frac{(p!)^2}{(2p)!(2p+1)!)}) \leq \delta}.$$
     Step 3: Set $\boxed{D \equiv I, N \equiv I, Y \equiv I, c = 1}$
     Step 4: For $k = 1, 2, ..., p$ do
     $$\boxed{c \equiv c(p - k + 1)/[(2p - k + 1)k] \\ Y \equiv AY,\\ N \equiv N + cY , \\D = D+(-1)^{k}cY.}$$
     Step 5: Solve for $F$ : $\boxed{DF = N}$.
     Step 6: For $k = 1, 2, ..., j$ do,
     $$\boxed{F \equiv F^{2}}$$
   • The algorithm requires about $2(p + j + (1/3)n^3$ flops.
   • The algorithm is numerically stable when A is normal. When A is non-normal, an analysis of the stability property becomes difficult, because, in this case e a may grow before it decays during the squaring process; which is known as “hump” phenomenon.
     Example at Page 143 of [1]

3. We have another effective method called the Matrix decomposition method uses the Real Schur form to do so.
   
   Let $\mathcal{A}$ be transformed to a real Schur matric $R$ using an orthogonal similarity transformation:
   $$\boxed{P^{T}\mathcal{A}P = R}$$
   Then,
   $$\boxed{e^{\mathcal{A}}=Pe^{R}P^{T}}$$
   Note that $R$ is upper-triangular.
   
   The algorithm is:
   Step 1: Transform $\mathcal{A}$ to $R$ using the $QR$ iteration algorithm.
   $$\boxed{P^{T}\mathcal{A}P = R}$$
   Step 2: Compute $e^R = G = g_{ij}$:
   for $i = 1,...,n$ do,
   $$g_{ii} = e^{r_{ii}}$$
   end.
   
   for $k = 1, 2, ..., n-1$ do
   for $i = 1, 2, ..., n-k$ do
   set $j = i+k$
   $$\boxed{g_{ij}=\frac{1}{(r_{ii}-r_{jj})}\Big[r_{ij}(g_{ii}-g_{jj})+\sum_{p=i+1}^{j-1}(g_{ip}r_{pj}-r_{ip}g_{pj})\Big]}$$
   end
   end
   Step 3: Now we have $e^R$ then we compute $e^\mathcal{A}$

---

2.Lyapunov Stability theorem: [1]

Lyapunov Stability theorem,
The system :
$$\boxed{\dot{x}(t)=\mathcal{A}x(t)}$$
is asymptotically stable $iff$, for any symmetric positive definite matrix $M$, there exists a unique symmetric positive definite matrix $X$ satisfying the equation:
$$\boxed{X\mathcal{A}+\mathcal{A}^{T}X=-M}$$

Kronecker Product and Lyapunov:
$$\boxed{\mathcal{A} \bigotimes B = \big[ a_{ij} [B] \big]}$$
For example,
if
$$\mathcal{A} = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix}$$
and,
$$B = \begin{bmatrix} b_{11} &b_{12} &b_{13}\\ b_{21} &b_{22} &b_{23}\\ \end{bmatrix}$$
Then, the Kronecker product will look like,
$$\mathcal{A} \bigotimes B = \begin{bmatrix} a_{11}b_{11} &a_{11}b_{12} &a_{11}b_{13} &a_{12}b_{11} &a_{12}b_{12} &a_{12}b_{13} \\ a_{21}b_{21} &a_{21}b_{22} &a_{21}b_{23}&a_{22}b_{11} &a_{22}b_{12} &a_{22}b_{13} \\ \end{bmatrix}$$
It is evident that,
$$\boxed{\mathcal{A} \bigotimes B \neq B\bigotimes\mathcal{A}}$$
Now, we formulate the $X\mathcal{A}+\mathcal{A}^{T}X=M$ using the Kronecker product. Note that $M$ is negative semi-definite. $X$ is positive definite and symmetric.

Vectorisation of a matrix $\large \triangleq$ Stack all elements of
the matrix into one column.

Going directly to the final answer,
$$\boxed{X\mathcal{A}+\mathcal{A}^{T}X=M = [(A^{T} \bigotimes I )+( I\bigotimes A^{T})]\overrightarrow{X} = \overrightarrow{M}}$$
Verify it once.

If $\mathcal{A}$ is stable then $X$ has unique solution.


Schur method of Lyapunov:
Method proposed by Bartels and Stewart. It is based on the reduction of $A^{T}$ to $RSF$.

Step 1: Reduce the problem.
For,
$$X\mathcal{A}+\mathcal{A}^{T}X = C$$
is reduced to,
$$\boxed{YR^{T}+RY=\hat{C}}$$
Where,
$R = U^{T}A^{T}U$, $\hat{C}=U^{T}CU$ and $Y=U^{T}XU$.

Step 2: Solution of the reduced form.
Let,
$$Y = (y_1, y_2,...,y_n),$$
$$\hat{C}=(c_1,...,c_n)$$
and $$R=(r_{ij})$$
Assume that the columns $y_{k+1}$ through $y_{n}$ have been computed, and consider the following two cases,

Case 1: $r_{kk-1} = 0$. Then $y_k$ is determined by solving the quasi-triangular system,
$$\boxed{(R+r_{kk}I)y_k=c_k-\sum_{j=k+1}^nr_{kj}y_j}$$
If, in particular, R is upper triangular, that is there are no “Schur bumps” on the diagonal, then each $y_i$, $i=n, n - 1 ..... 2, 1$ can be obtained
by solving an $n \times n$ upper triangular system as follows:
$$\boxed{(R+r_{nn}I)y_n=c_n} \\ \boxed{(R+r_{n-1,n-1}I)y_{n-1}=c_{n-1}-r_{n-1,n}y_n}$$

Case 2: $r_{kk-1} \neq 0$ this shows a Schur Bump.
$$\boxed{R(y_{k-1}, y_k)+(y_{k-1}, y_k) \begin{bmatrix} r_{k-1,k-1} &r_{k,k-1}\\ r_{k-1,k} &r_{k,k}\\ \end{bmatrix}\\ =(c_{k-1},c_k)-\sum_{j=k+1}^n(r_{k-1,j}y_j, r_{kj}y_j)=(d_{k-1},d_k)}$$
Example at Page 274


If $\mathcal{A}$ doesn’t have Eigen Values in the Limit circle , we modify $\mathcal{A}$ as,
$$A_{1} = (I-A)^{-1}(I+A) \text{ and } Q_{1} = (I+A^{T}_{1})(I+A_{1})\\ \text { solve for A } \implies (I-A)A_{1}=(I+A)\\ \implies A_{1}-AA_{1}=I+A\\ \implies A_{1} - I = AA_{1}+A\\ \implies A(A_{1}+I) = A_{1}-I\\ \implies A=(A_{1}-I)(A_{1}+I)^{-1}$$
Use this $A$ in the Discrete Lyapunov which is given by,
$$\mathcal{L}_{D} : A^{T}PA-P=Q$$
The resulting equation is,
$$A^{T}_1P+PA_{1}=Q_{1} \text{ assume, } Q = -2I$$
You will get a similar equation to that of the normal Lyapunov equation.

---

3. Modified QR algorithms:[4]

1. Modified Gram-Schmidt method:
   for
   $$k = 1:n\\ q^{T}_k = a^{T}_k$$
   end
   
   for
   $$k = 1:n\\ r_{kk} = (q^{T}_{k}q_k)^{1/2}\\ q^{T}_k= \frac{q^{T}_k}{r_{kk}}$$
   -for
   $$j = k+1:n\\ r_{kj}=a^{T}_{j}q_{k}\\ q^{T}_{j}=q^{T}_{j}-r_{kj}q^{T}_{k}$$
   -end
   end
   It requires $\boxed{O(\frac{8}{3}n^{3})}$ operations.
   Practice example from the above link

2. Original algorithm of QR decomposition:
   Aim is to write matrix $\mathcal{A}$ in terms of $\boxed{Q\times R}$.
   Here, $Q$ is an orthogonal matrix with orthonormal columns; and $R$ is an upper-triangular matrix.
   
   Now, we take an example,
   $$\mathcal{A}=\begin{bmatrix} 1 & 2 & 3\\ -1 & 1 & 1\\ 1 & 1 & 1\\ 1 & 1 & 1 \end{bmatrix}$$
   We will first find $q_1$, $q_2$ and $q_3$ as the three orthonormal vectors using the GS-strategy.
   Now, we will define $a$, $b$ and $c$ as,
   $$a = \begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}, b=\begin{bmatrix} 2\\ 1\\ 1\\ 1 \end{bmatrix} \text{and}, c = \begin{bmatrix} 3\\ 1\\ 1\\ 1 \end{bmatrix}$$
   We define a partial basis as $\mathcal{X}$ which will be updated at each step.
   
   For the first step,
   we find $v_1$ as,
   $$\boxed{v_1 = \frac{a}{1} = \begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}} \text{now the partial basis is,} \mathcal{X} = \big[\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix} \big]$$
   similarly, we find $v_2$ as follows,
   $$v_2 = b - proj_{\mathcal{X}}\begin{bmatrix} 2\\ 1\\ 1\\ 1 \end{bmatrix}\\ = \begin{bmatrix} 2\\ 1\\ 1\\ 1 \end{bmatrix}-\frac{\begin{bmatrix} 2\\ 1\\ 1\\ 1 \end{bmatrix}.\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}}{\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}.\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}}\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix} = \begin{bmatrix} 2\\ 1\\ 1\\ 1 \end{bmatrix}-\frac{3}{4}\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}\\ \text{Now,} \boxed{4v_2=\begin{bmatrix} 8\\ 4\\ 4\\ 4 \end{bmatrix}-\begin{bmatrix} 3\\ -3\\ 3\\ 3 \end{bmatrix}\\ =\begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix}}$$
   Now, we update $\mathcal{X}$,
   $$\mathcal{X} = \Big[\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}, \begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix} \Big]$$
   Now, we find $v_3$ as follows,
   $$v_3 = \begin{bmatrix} 3\\ 1\\ 1\\ 1 \end{bmatrix} - proj_{\mathcal{X}}\begin{bmatrix} 3\\ 1\\ 1\\ 1 \end{bmatrix}\\ v_3 = \begin{bmatrix} 3\\ 1\\ 1\\ 1 \end{bmatrix}-\frac{\begin{bmatrix} 3\\ 1\\ 1\\ 1 \end{bmatrix}.\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}}{\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}.\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}}\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}-\frac{\begin{bmatrix} 3\\ 1\\ 1\\ 1 \end{bmatrix}.\begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix}}{\begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix}.\begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix}}\begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix}\\ v_3 = \begin{bmatrix} 3\\ 1\\ 1\\ 1 \end{bmatrix}-\frac{4}{4}\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}-\frac{24}{76}\begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix}\\ \text{now},\\ \boxed{19v_3 = \begin{bmatrix} 8\\ -4\\ -6\\ -6 \end{bmatrix}}$$
   Hence, the partial basis is,
   $$\boxed{\mathcal{X} = \Big[\begin{bmatrix} 1\\ -1\\ 1\\ 1 \end{bmatrix}, \begin{bmatrix} 5\\ 7\\ 1\\ 1 \end{bmatrix}, \begin{bmatrix} 8\\ -4\\ -6\\ -6 \end{bmatrix}\Big]}$$

$$proj_{\overrightarrow{a}}{\overrightarrow{b}} = \frac{{\overrightarrow{a}}\cdot {\overrightarrow{b}}}{{\overrightarrow{a}}^2}{\overrightarrow{a}}$$

This partial basis is the orthogonal set, hence we now make it orthonoamal,
$$Q_{orthogonal} = \begin{bmatrix} 1 & 5 & 8\\ -1 & 7 & -2\\ 1 & 1 & -3\\ 1 & 1 & -3\\ \end{bmatrix}$$
Hence,
norm of first column, $$||n_1|| = \sqrt{1^2+(-1)^2+1^2+1^2} = 2$$
Similarly,
$$||n_2|| = \sqrt{76}$$
and
$$||n_2|| = \sqrt{38}$$
Hence, the orthonormal $Q$ is,
$$Q_{orthonormal}=\begin{bmatrix} 1/2 & 5/\sqrt{76} & 8/\sqrt{38} \\ -1/2 & 7/\sqrt{76} & -2/\sqrt{38}\\ 1/2 & 1/\sqrt{76} & -3/\sqrt{38}\\ 1/2 & 1/\sqrt{76} & -3/\sqrt{38}\\ \end{bmatrix}$$
Now, we have, $\mathcal{A}$ and $Q$; we now find $R$; which by theory has to be upper-triangular,
$$\mathcal{A}= Q \cdot R \\ Q^{T} \cdot \mathcal{A} = Q^{T} \cdot Q \cdot R\\ \text{NOTE:}\text{because } Q \text{ is orthonormal } \boxed{Q^{T} \cdot Q = I}.\\ \therefore \boxed{R = Q^{T} \cdot \mathcal{A}}$$
Make up the algorithm from the above steps.

---

4. Condition Number:[5]

As a rule of thumb, if the condition number $\kappa (A)=10^{k}$, then you may lose up to $k$ digits of accuracy on top of what would be lost to the numerical method due to loss of precision from arithmetic methods.

A problem with a low condition number is said to be well-conditioned, while a problem with a high condition number is said to be ill-conditioned. The condition number is a property of the problem.

Condition number is mathematically defined as,
$$\kappa(A) = ||A||_{1}||A^{-1}||_{1}$$
We define the $1$-norm as follows,
For a matrix $M$
$$M = \begin{bmatrix} 2 & 3\\ 1 & -1 \end{bmatrix}$$
The $1$-norm is,
$$\text{Maximum of }(2+1,3+1) = 4.\\ \text{Hence, }||M||_{1} = 4.$$

So, for a given matrix,
$$P = \begin{bmatrix} 1 & 10^{4}\\ -1 & 2 \end{bmatrix}$$
We get,
$$P^{-1} = \frac{1}{2+10^{4}}\begin{bmatrix} 2 & -10^{4}\\ 1 & 1 \end{bmatrix}$$
Hence,
$$||P||_{1} = \text{maximum of }(1+1, 2+10^{2}) = 2+10^{4}$$
and,
$$||P^{-1}||_{1} = \frac{1}{2+10^{4}}\text{maximum of }(2+1, 10^{4}+1) = \\ \frac{1}{2+10^{4}}(1+10^{4})$$
Therefore,
$$\text{Condition number},\\ \kappa(P) = ||P||_{1}||P^{-1}||_{1} = 1+10^{4}$$
Thus, the matrix (or system) is ill-conditioned.

---

The question paper that came for this exam was pretty sadistic.
Give it a try, if you can and tell me how awesome it feels. I will score around 30/50.