1. Linear Algebra and Calculus
We refresh some of the material in linear algebra and calculus needed for this course.
1.1 Linear Algebra Refresher
Recap 1.1 (Vector toolbox): Let $\vb{a},\vb{b} \in \mathbb{R}^n$ be two vectors, then we recall the following definitions and properties:
- inner product: $\langle\vb{a},\vb{b}\rangle = \vb{a}^{\top} \vb{b} = \vb{b}^{\top} \vb{a} = \sum_{i=1}^n a_i b_i$
- lenght: $\norm{\vb{a}}^2 = \langle\vb{a},\vb{a}\rangle = \sum_{i=1}^n a_i^2$
- Cauchy-Schwarz: $\abs{\langle\vb{a},\vb{b}\rangle}^2 \leq \langle\vb{a},\vb{a}\rangle \cdot \langle\vb{b},\vb{b}\rangle$
- orthogonality: $\vb{a} \perp \vb{b} \iff \langle\vb{a},\vb{b}\rangle = 0$
Recap 1.2 (Orthonormal basis): Let $\vb{y} = \sum_{i} b_i \vb{e}_i$ where the $\vb{e}_i$ form an orthonormal basis, i.e. $\langle\vb{e}_i,\vb{e}_j\rangle = \delta_{i,j}$. Then the coordinates can be calculated as $b_i = \langle\vb{y},\vb{e}_i\rangle$.
Recap 1.3 (Matrix transpose and inverse): Let $\vb{A} \in \mathbb{R}^{n\times p}$ and $\vb{B} \in \mathbb{R}^{p \times n}$ be two invertible matrices, then the following properties hold:
- $(\vb{A} \vb{B})^{\top} = \vb{B}^{\top} \vb{A}^{\top}$
- $\vb{A}^{-1} \vb{A} = \vb{I}$
- $(\vb{A} \vb{B})^{-1} = \vb{B}^{-1} \vb{A}^{-1}$
- $\qty(\vb{A}^{-1})^{\top} = \qty(\vb{A}^{\top})^{-1} = \vb{A}^{-\top}$
Note that if $\vb{X}$ is a matrix, then $\vb{X}^{\top} \vb{X}$ and $\qty(\vb{X}^{\top} \vb{X})^{-1}$ (if it exists) are symmetric.
Recap 1.4 (Orthogonal projection): Let $\vb{y} \in \mathbb{R}^n$ be a vector and $S$ be a $p$-dimensional subspace spanned by linearly independent vectors $\vb{x}_1, \ldots \vb{x}_p$. If we define $\vb{X} = \qty[ \vb{x}_1 \cdots \vb{x}_p ] \in \mathbb{R}^{n\times p}$, then the orthogonal projection matrix is $\vb{P}_S = \vb{X} \qty(\vb{X}^{\top} \vb{X})^{-1} \vb{X}^{\top}\in \mathbb{R}^{n \times n}$.
The orthogonal projection of $\vb{y}$ onto $S$ in the basis of $\mathbb{R}^n$ is $\vb{y}_{\perp} = \vb{P}_S \vb{y}$ and we note the following properties:
- $\vb{P}_S$ is symmetric, i.e $\vb{P}_S^{\top} = \vb{P}_S$
- $\vb{P}_S$ is idempotent, i.e $\vb{P}_S^{n} = \vb{P}$
- $\trace{\vb{P}_S} = p$
- $\rank{\vb{P}_S} = p$
- $\vb{y}_{\perp} = \mathop{\arg \min}\limits_{\vb{s} \in S} \norm{\vb{y} - \vb{s}}$
- $\vb{1} - \vb{P}_S$ is also a projection
We also note that $\vb{P}_S(\vb{1} - \vb{P}_S) = \vb{0}$ and that the eigenvalues of $\vb{P}_S$ are in $\qty{0,1}$ with the geometric multiplicity of the eigenvalue $1$ being $p$.
Recap 1.5 (Quadratic form, positive definite matrix): Let $\vb{A} \in \mathbb{R}^{n \times n}$ be a matrix.
- $\vb{A}$ is called positive definite or p.d. if $\forall \vb{x} \in \mathbb{R}^n \setminus \qty{\vb{0}} : \vb{x}^{\top} \vb{A} \vb{x} \gt 0$
- $\vb{A}$ is called positive semi-definite or p.s.d. if $\forall \vb{x} \in \mathbb{R}^n : \vb{x}^{\top} \vb{A} \vb{x} \geq 0$
- if $\vb{A}$ is p.d., then $\lambda_i \gt 0$, $\trace{\vb{A}} \gt 0$, $\det{\vb{A}} \gt 0$