Basics of Math and Graph

Linear Algebra

• Scalar

• Vector

  $$\mathbf x=\begin{bmatrix} x_1\\x_2\\ \vdots\\x_n \end{bmatrix}$$

• The $L_p$ norm of a vector

$$\Vert\mathbf x\Vert_p=(\sum_{i=1}^{n}\lvert x_i\rvert^p)^\frac{1}{p}$$

• The $L_1$ norm of a vector

$$\Vert\mathbf x\Vert_1=\sum_{i=1}^{n}\lvert x_i\rvert$$

• The $L_2$ norm of a vector

$$\Vert\mathbf x\Vert_2=\sqrt{\sum_{i=1}^{n}x_i^2}$$

• The $L_\infty$ norm of a vector

$$\Vert \mathbf x\Vert_\infty=\mathop{max}\limits_{i}\lvert x_i\rvert$$

• The distance of two vectors $\mathbf x_1,\mathbf x_2$

$$\mathbf D_p(\mathbf x_1,\mathbf x_2)=\Vert\mathbf x_1-\mathbf x_2\Vert_p$$

• A set of vectors $\mathbf x_1,\mathbf x_2,\cdots,\mathbf x_m$ are linearly independent

not exist a set of scalars $\lambda_1,\lambda_2,\cdots,\lambda_m,$ which are not all 0

$$\lambda_1\mathbf x_1+\lambda_2\mathbf x_2+\cdots+\lambda_m\mathbf x_m=0$$

• Matrix

  $$\mathbf A=\begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{bmatrix}$$

• Matrix product

  $$\mathbf A\in\mathbb R^{m\times n}$$ $$\mathbf B\in\mathbb R^{n\times p}$$ $$\mathbf C_{ij}=\sum_{k=1}^{n}\mathbf A_{ik}\mathbf B_{kj}$$ $$\mathbf C\in\mathbb R^{m\times p}$$

• determinant

  $$det(\mathbf A)=\sum_{k_1k_2\cdots k_n}(-1)^{\tau(k_1k_2\cdots k_n)} a_{1k_1}a_{2k_2}\cdots a_{nk_n}$$ $$k_1k_2\cdots k_n\ is\ a\ permutation\ of\ 1,2,\cdots,n$$ $$\tau(k_1k_2\cdots k_n)\ is\ the\ inversion\ number\ of\ the\ permutationk_1k_2\cdots k_n$$

• The inverse matrix

  $$\mathbf A^{-1}\mathbf A=\mathbf I$$

• The transpose of matrix

  $$\mathbf A_{ij}^{T}=\mathbf A_{ji}$$

• The Hadamard product

  $$\mathbf A\in\mathbb R^{m\times n}$$ $$\mathbf B\in\mathbb R^{m\times n}$$ $$\mathbf C_{ij}=\mathbf A_{ij}\mathbf B_{ij}$$ $$\mathbf C\in\mathbb R^{m\times n}$$

• Tensor: An array with arbitrary dimension

Probability theory

• joint probability

  $$P(X=x_1,Y=y_1)$$

• conditional probability

  $$P(X=x_1|Y=y_1)$$

• The sum rule

  $$P(X=x)=\sum_yP(X=x,Y=y)$$

• The product rule

  $$P(X=x,Y=y)=P(Y=y|X=x)P(X=x)$$

• Bayes formula

  $$P(Y=y|X=x)=\frac{P(X=x,Y=y)}{P(X=x)}=\frac{P(X=x|Y=y)P(Y=y)}{P(X=x)}$$ $$P(X_i=x_i|Y=y)=\frac{P(Y=y|X_i=x_i)P(X_i=x_i)}{\sum_{j=1}^nP(Y=y|X_j=x_j)}$$

• The chain rule

  $$P(X_1=x_1,\cdots,X_n=x_n)\\ =P(X_1=x_1)\prod_{i=2}^{n}P(X_i=x_i|X_1=x_1,\cdots,X_{i-1}=x_{i-1})$$

• The expectation of f(x)

  $$\mathbb E[f(x)]=\sum_xP(x)f(x)$$

• The variance of f(x)

  $$\begin{aligned} Var(f(x)&=\mathbb E[(f(x)-\mathbb E[f(x)])^2]\\ &=\mathbb E[f(x)^2]-\mathbb E[f(x)]^2 \end{aligned}$$

• The standard deviation

  $$\sqrt{Var(f(x)}$$

• Covariance

  $$Cov(f(x),g(y))=\mathbb E[(f(x)-\mathbb E[f(x)])(g(y)-\mathbb E[g(y)])]$$

• Gaussian distribution

  $$N(x|\mu,\sigma^2)=\sqrt{\frac{1}{2\pi\sigma^2}}exp(-\frac{1}{2\sigma^2}(x-\mu)^2)$$ $$\mu\ is\ the\ mean\ of\ variable\ x$$ $$\sigma^2\ is\ the\ variance$$

• Bernoulli distribution

  $$P(X=x)=p^x(1-p)^{(1-x)},x \in \left\{0,1\right\}$$

• Binomial distribution

  $$P(Y=k)=\begin{pmatrix}N\\k\end{pmatrix}p^k(1-p)^{(N-k)}$$

• Laplace distribution

  $$P(x|\mu,b)=\frac{1}{2b}exp(-\frac{\lvert x -\mu\rvert}{b})$$

Graph theory

$$G=(V,E)$$ $$V\ is\ the\ set\ of\ vertices$$ $$E\ is\ the\ set\ of\ edges$$

• Adjacency matrix

  $$A_{ij}=\left\{ \begin{aligned} &1\ if\left\{v_i,\ v_j\right\}\in E\ and\ i\ \neq\ j,\\ &0\ otherwise. \end{aligned} \right.$$

• Degree matrix

  $$D_{ii}=d(v_i)$$

• Laplacian matrix

  $$L=D-A$$ $$L_{ij}=\left\{ \begin{aligned} &d(v_i)\ if\ i=j,\\ &-1\ if\left\{v_i,v_j\right\}\in E\ and\ i\ \neq\ j,\\ &0\ otherwise. \end{aligned} \right.$$

• Symmetric normalized Laplacian

  $$\begin{aligned} L^{sym}&=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}\\ &=I-D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \end{aligned}$$

$$L_{ij}^{sym}=\left\{ \begin{aligned} &1\ if\ i=j\ and\ d(v_i)\neq\ 0,\\ &-\frac{1}{\sqrt{d(v_i)d(v_j)}}if\left\{v_i,v_j\right\}\in E\ and\ i\ \neq\ j,\\ &0\ otherwise. \end{aligned} \right.$$

• Random walk normalized Laplacian $$L^{rw}=D^{-1}L=I-D^{-1}A$$ $$L_{ij}^{rw}= \left\{ \begin{aligned} &1\ if\ i=j\ and\ d(v_i)\ \neq\ 0,\\ &-\frac{1}{d(v_i)}\ if\left\{v_i,v_j\right\}\in E\ and\ i\ \neq\ j,\\ &0\ otherwise. \end{aligned} \right.$$
• Incidence matrix

For a directed graph

$$M_{ij}= \left\{ \begin{aligned} &1\ if\ \exists\ k\ s.t\ e_j=\left\{v_i,v_k\right\},\\ &-1\ if\ \exists\ k\ s.t\ e_j=\left\{v_k,v_i\right\},\\ &0\ otherwise. \end{aligned} \right.$$

For a undirected graph

$$M_{ij}= \left\{ \begin{aligned} &1\ if\ \exists\ k\ s.t\ e_j=\left\{v_i,v_k\right\},\\ &0\ otherwise. \end{aligned} \right.$$