Prerequisites for CS467

Linear Algebra

Vector

• A vector is a list of numbers
• $x=\left[\begin{array}{c}{x}_1\\ x_2\\ ⋮\\ x_n\end{array}\right]\in {\mathbb{R}}^n$
• $x^{\mathrm{\top }}=\left[\begin{array}{cccc}{x}_1& x_2& \cdots & x_n\end{array}\right]$

Inner product

• given two vectors:
  $x,y\in {\mathbb{R}}^n$
• notations:
  $⟨x,y⟩$ or
  $x^{\mathrm{\top }}y$
• $x^{\mathrm{\top }}y=y^{\mathrm{\top }}x=\sum _{i=1}^n{x}_i{y}_i$ (a scalar)

Euclidean norm (2-norm)

• the length of the vector
• given a vectors:
  $x\in {\mathbb{R}}^n$
• $\Vert x\Vert =\sqrt{\sum _{i=1}^n{x}_i^2}$
• $\Vert x{\Vert }^2=x^{\mathrm{\top }}x$
• unit vector:
  $\frac{x}{\Vert x\Vert }$

Orthogonal and orthonormal

• given three vectors:
  $x,y,z\in {\mathbb{R}}^n$
• if
  $⟨x,y⟩=0$, then
  $x$ and
  $y$ is orthogonal (perpendicular) to each other
• the set of vectors
  $\{x,y,z\}$ is said to be orthonormal if
  $x,y,z$ are mutually orthogonal, and
  $\Vert x\Vert =\Vert y\Vert =\Vert z\Vert =1$

Linear independence

• given a set of
  $m$ vectors
  $\{v_1,v_2,...,v_m\}$
• the set is linearly dependent if a vector in the set can be represented
  as a linear combination of the remaining vectors
  • $v_m=\sum _{i=1}^{m-1}{\alpha }_i{v}_i,{\alpha }_i\in \mathbb{R}$
• otherwise, the set is linearly independent

Span

• the span of
  $\{v_1,...,v_m\}$ is the set of all vectors that can be expressed as a linear combination of
  $\{v_1,...,v_m\}$
  • span
    $(\{v_1,...,v_m\})$ =
    $\{u:u=\sum _{i=1}^m{\alpha }_i{v}_i\}$
• if
  $\{v_1,...,v_m\}$ is linearly independent, where
  $v_i\in {\mathbb{R}}^m$, then any vector
  $u\in {\mathbb{R}}^m$ can be written as a linear combination of
  $v_1$ through
  $v_m$
  • in other words, span
    $(\{v_1,...,v_m\})={\mathbb{R}}^m$
  • e.g.
    $v_1=\left[\begin{array}{c}1\\ 0\end{array}\right]v_2=\left[\begin{array}{c}0\\ 1\end{array}\right],$ span
    $(\{\left[\begin{array}{c}1\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 1\end{array}\right]\})={\mathbb{R}}^2$
  • we call
    $\{v_1,...,v_m\}$ a basis of
    ${\mathbb{R}}^m$

Matrix

• A matrix
  $A\in {\mathbb{R}}^{m\times n}$ is a 2d array of numbers with
  $m$ rows and
  $n$ columns
  • if
    $m=n$, we call
    $A$ a square matrix
• Matrix multiplication
  • given two matrices
    $A\in {\mathbb{R}}^{m\times n}$ and
    $B\in {\mathbb{R}}^{n\times p}$
  • $C=AB\in {\mathbb{R}}^{m\times p}$, where
    $C_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}$
  • not commutative:
    $AB\ne BA$
• Matrix-vector multiplication
  • can be viewed as a linear combination of the columns of a matrix

Transpose

$A^{\mathrm{\top }}$

• The transpose of a matrix results from flipping the rows and columns
  • $(A^{\mathrm{\top }}{)}_{ij}=A_{ji}$
• Some properties:
  • $(AB{)}^{\mathrm{\top }}=B^{\mathrm{\top }}{A}^{\mathrm{\top }}$
  • $(A+B{)}^{\mathrm{\top }}=A^{\mathrm{\top }}+B^{\mathrm{\top }}$
• If
  $A^{\mathrm{\top }}=A$, we call
  $A$ a symmetric matrix

Trace

$\text{tr}(A)$

• The trace of a square matrix is the sum of its diagonal
  • $\text{tr}(A)=\sum _{i=1}^n{A}_{ii}$
• If
  $A,B$ are square matrix, then
  $\text{tr}(AB)=\text{tr}(BA)$
  • $\sum _{i=1}^n(AB{)}_{ii}=\sum _{i=1}^n\sum _{k=1}^n{A}_{ik}{B}_{ki}=\sum _{k=1}^n\sum _{i=1}^n{B}_{ki}{A}_{ik}=\sum _{k=1}^n(BA{)}_{kk}$

Inverse

$A^{-1}$

• The inverse of a square matrix
  $A$ is the unique matrix such that
  • $A^{-1}A=I=A{A}^{-1}$
• Let
  $A$ be a
  $n\times n$ matrix.
  $A$ is invertible iff
  • the column vectors of
    $A$ is linearly independent (spans
    ${\mathbb{R}}^n$)
  • $\text{det}(A)\ne 0$
• Assume that both
  $A,B$ are invertible. Some properties:
  • $(AB{)}^{-1}=B^{-1}{A}^{-1}$
  • $(A^{-1}{)}^{\mathrm{\top }}=(A^{\mathrm{\top }}{)}^{-1}$

Orthogonal matrix

• a square matrix is orthogonal if all its columns are orthonormal
• $U$ is a orthogonal matrix iff
  • $U^{\mathrm{\top }}U=I=U{U}^{\mathrm{\top }}$
  • $U^{-1}=U^{\mathrm{\top }}$
• Note: if
  $U$ is not square but has orthonormal columns, we still have
  $U^{\mathrm{\top }}U=I$ but not
  $U{U}^{\mathrm{\top }}=I$

Calculus

Chain rule

• $\frac{dy}{dx}=\frac{dy}{du}\frac{du}{dx}$ (single-variable)
• e.g.,
  $y=(x^2+1{)}^3,\frac{dy}{dx}=?$
  • let
    $u=x^2+1$, then
    $y=u^3$
  • $\frac{dy}{dx}=3(x^2+1{)}^2(2x)$

Critical points

• $f^{\prime }>0$ =>
  $f$ is increasing
• $f^{\prime }<0$ =>
  $f$ is decreasing
• $f^{″}>0$ =>
  $f^{\prime }$ is increasing =>
  $f$ is concave up
• $f^{″}<0$ =>
  $f^{\prime }$ is decreasing =>
  $f$ is concave down
• We call
  $x=a$ a critical point of a continous function
  $f(x)$ if either
  $f^{\prime }(a)=0$ or
  $f^{\prime }(a)$ is undefined

Taylor series

• $f(x)=\sum _{n=0}^{\mathrm{\infty }}\frac{f^{(n)}(a)}{n!}(x-a{)}^n$ (single-variable)
• second order approximation:
  • $f(x)\approx f(a)+f^{\prime }(a)(x-a)+\frac{1}{2}{f}^{″}(a)(x-a{)}^2$ (single-variable)
    • for
      $x$ close enough to
      $a$
  • $f(w)\approx f(u)+\mathrm{\nabla }f(u{)}^{\mathrm{\top }}(w-u)+\frac{1}{2}(w-u{)}^{\mathrm{\top }}{H}_f(u)(w-u)$ (multivariate)
    • $w,u\in {\mathbb{R}}^d$, for
      $w$ close enough to
      $u$
    • ${{\mathrm{\nabla }}_{w}f}^{\mathrm{\top }}=[\frac{\partial f}{\partial w_0},\cdots ,\frac{\partial f}{\partial w_d}]$
    • $H_f$ is the Hessian matrix, where
      $(H_f{)}_{ij}=\frac{{\partial }^{2}f}{\partial w_i\partial w_j}$

Probability

Conditional probability

• $P(A|B)$: the conditional probability of event
  $A$ happening given that event
  $B$ has occurred
  • $P(A|B)=\frac{P(A,B)}{P(B)}$
• $P(A|B)=\frac{P(B|A)P(A)}{P(B)}$ (Bayes rule)
• $\{A_i{\}}_{i=1}^n$ is a partition of the sample space. We have
  $P(B)=\sum _{i=1}^{n}P(B,A_i)=\sum _{i=1}^{n}P(B|A_i)P(A_i)$

Independece and conditional independence

• random variable
  $X$ is independent with
  $Y$ iff
  • $P(X|Y)=P(X)$
  • $P(X,Y)=P(X)P(Y)$
• random variable
  $X$ is conditionally independent with
  $Y$ given
  $Z$ iff
  • $P(X|Y,Z)=P(X|Z)$
  • $P(X,Y|Z)=P(X|Z)P(Y|Z)$

Expectation

• $\mathcal{X}$: the sample space. The set of all possible outcomes of an experiment.
  • e.g., the face of a dice,
    $\mathcal{X}=\{1,2,3,4,5,6\}$
• $p(x)$: probability mass function (discrete) or probability density function (continuous)
• $\mathbb{E}[X]=\sum _{x\in \mathcal{X}}xp(x)$ (discrete)
• $\mathbb{E}[X]={\int }_{\mathcal{X}}xp(x)dx$ (continuous)
  • more generally,
    $\mathbb{E}[g(X)]={\int }_{\mathcal{X}}g(x)p(x)dx$
• Linearity of expectation
  • $\mathbb{E}[aX+b]=a\mathbb{E}[X]+b$
  • $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$
• If
  $X$ and
  $Y$ are independent,
  $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$
  • why? plug in
    $P(X,Y)=P(X)P(Y)$ into the definintion of expectation
  • the converse is not true

Variance and covariance

• $\text{Var}[X]=\mathbb{E}[(X-\mu {)}^2]$, where
  $\mu =\mathbb{E}[X]$
  • $=\mathbb{E}\left[X^2\right]-{\mu }^2$
• $\text{Var}[aX+b]=a^2\text{Var}[X]$
• $\text{Cov}[X,Y]=\mathbb{E}[(X-{\mu }_X)(Y-{\mu }_Y)]$
• If
  $X$ and
  $Y$ are independent, then
  $\text{Cov}[X,Y]=0$
  • the converse is not true

Covariance matrix

• Consider
  $d$ random variables
  $X_1,...,X_d$
• $\text{Cov}[X_i,X_j]=\mathbb{E}[(X_i-{\mu }_{X_i})(X_j-{\mu }_{X_j})]$
• We can write a
  $d\times d$ matrix
  $\mathrm{\Sigma }$, where
  ${\mathrm{\Sigma }}_{ij}=\text{Cov}[X_i,X_j]$
  • when
    $i=j$ (diagonal),
    $\mathbb{E}[(X_i-{\mu }_{X_i})(X_i-{\mu }_{X_i})]=\text{Var}[X_i]$