Chapter 99: Mathematical Background Appendix

This note is a high-fidelity Markdown migration of the Mathematical Background appendix from the LaTeX source.

Parent map: index Related chapters: probability-and-mathstats, linear-regression, maximum-likelihood-and-machine-learning

Concept map

flowchart TD
  A[Proof Techniques] --> B[Set Theory]
  B --> C[Analysis and Topology]
  C --> D[Measure and Integration]
  D --> E[Probability Theory]
  C --> F[Linear Algebra]
  F --> G[Function Spaces]
  G --> H[Calculus and Optimisation]

Mathematical Background

Proof Techniques

1. Direct Proof / modus ponens: If $R$ is a true statement and $R⟹S$ is a true conditional statement, then $S$ is a true statement. Direct proofs typically involve backwards-forwards reasoning - take all statements that follow from $R$ that might relate to $S$, list them in $\mathcal{R}$. Then, take all statements that follow from $S$, list them in $\mathcal{S}$. Then, look for statements $r,s\in \mathcal{R}\times \mathcal{S}$ that have a straightforward proof, and write proof of the form $R⟹r⟹s⟹S$.

2. Contrapositive: Since every conditional statement is equivalent to its contrapositive, proving $\neg Q⟹\neg P$ is equivalent to proving $P⟹Q$.

3. Proof by contradiction: Assume $P$ is true, and assume $Q$ is false [i.e. $\neg Q$ is true], and show that $\neg Q⟹S$ (using $P$ and other possible intermediate results) where $S$ is known to be false. Conclude that $\neg Q$ must be false, so $Q$ must be true, and we have proved that $P⟹Q$.

4. Induction [only applies to statements pertaining to well ordered sets] $\mathcal{N}$

   • Assume a base case - $P(0)$ is a true statement

   • Prove whenever $P(k)$ is true, $P(k+1)$ is true

   • Therefore $P(n)$ is true for every $n\in \mathcal{N}$

Set Theory

A set is a collection of objects. E.g. $\mathbb{R},\mathbb{Q},\mathbb{Z},\mathbb{N}$.

Set operations:

• Intersection : $A\cap B$

• Union : $A\cup B$

• Difference: $A\setminus B:=\{x:x\in A\wedge x\notin B\}$

• cartesian product: $A\times B:=\{(a,b):a\in A\wedge b\in B\}$

Definition. Set of all subsets of S is itself a set. Denoted as $\mathfrak{P}(S)$

$\left|\mathbb{C}\right|>\left|\mathbb{R}\right|>\left|\mathbb{Q}\right|>\left|\mathbb{Z}\right|>\left|\mathbb{N}\right|$

Relations

Given two sets $X$ and $Y$, any subset of their Cartesian product $X\times Y$ is called a binary relation. For any pair of elements $(x,y)\in R\subseteq RX\times Y⟹xRy$.

Properties of binary relations:

• reflexive $xRx\forall x\in X$

• transitive if $xRy\wedge yRz⟹xRz$

• symmetric If $xRy⟹yRx$

• antisymmetric If $xRy\wedge yRx⟹x=y$

• asymmetric if $xRy⟹\neg (yRx)$

• complete if either $xRy$ or $yRx$ or both $\forall x,y,z\in X$

Definition. An equivalence relation $R$ on a set $X$ is a relation that is reflexive, transitive, and symmetric. Given an equivalence relation $\sim$, the set of elements that are related to a given element $a$ :

$\sim (a):=\{x\in X:x\sim a\}$

is called the equivalence class of $a$. e.g. Indifference $\sim$ preference relation is an equivalence relation, but the preference relation $⪰$ is not because it isn’t symmetric.

Definition. A relation that is reflexive and transitive but not symmetric is called an order relation: $x⪰y$. This is also called a weak order. $\succ$ is not an order relation because it is not reflexive (and is called a strong order). Every order relation also induces an equivalence relation: $x\sim y⟺x⪰y\wedge y⪰x$

An ordered set $(X,⪰)$ consists of a set $X$ together with an order relation $⪰$ defined on X.

Intervals and Contour Sets

Given an ordered set and two elements $a,b\in X\text{ s.t. }b⪰a$, we can define

• The open interval $(a,b)$ : set of all elements strictly between $a$ and $b$.

• The closed interval $[a,b]$ : set of all elements between $a$ and $b$ $\text{ s.t. }[a,b]=\{x\in X:a\preccurlyeq x\preccurlyeq b\}$

Analogously, for arbitrary ordered sets, $(X,⪰)$ we can define

• Upper contour set $⪰(a):=\{x\in X:x⪰a\}$ : set of all elements that follow or dominate a

• Lower contour set $\preccurlyeq (a):=\{x\in X:x\preccurlyeq a\}$ : set of all elements that precede $a$ in the order $⪰$

A partial order is a relation that is reflexive, transitive, and antisymmetric.

Definition. The join of a partially ordered set $\mathcal{S}$ is the supremum and is denoted $\bigvee \mathcal{S}$. $\max (a,b)$ is sometimes written $a\vee b$.

The meet of a poset is the infimum and is denoted $\bigwedge \mathcal{S}$. $\min (a,b)$ is sometimes written $a\wedge b$.

Algebra

Definition. A set $\mathcal{G}$ and an operation $\otimes :\mathcal{G}\times \mathcal{G}\to G$ defined on $\mathcal{G}$. Then $G:=(\mathcal{G},\otimes )$ is called a group if the following conditions hold:

1. Closure of $\mathcal{G}$ under $\otimes$: $\forall x,y\in \mathcal{G},x\otimes y\in \mathcal{G}$

2. Associativity: $\forall x,y,z\in \mathcal{G},(x\otimes y)\otimes z=x\otimes (y\otimes z)$

3. Neutral element: $\exists e\in \mathcal{G}\forall x\in G\text{ s.t. }x\otimes e=e\otimes x=x$

4. Inverse element: $\forall x\in \mathcal{G},\exists y\in \mathcal{G}:x\otimes y=e\wedge y\otimes x=e$.

5. if additionally $\forall x,y\in \mathcal{G}:x\otimes y=y\otimes x$, then $G$ is an Abelian/Commutative group

$(\mathbb{Z},+),({\mathbb{R}}^{m\times n},+)(\mathbb{R}\backslash \{0\},.)$ are all groups

Definition. A real valued vector space $V=(\mathcal{V},+,\cdot )$ is a vector space with two operations

$$\begin{array}{rl}+& :\mathcal{V}\times \mathcal{V}\to \mathcal{V}\\ \cdot & :\mathbb{R}\times \mathcal{V}\to \mathcal{V}\end{array}$$

Where

1. $(\mathcal{V},+)$ is an Abelian Group

2. Distributivity

   • $\forall \lambda \in \mathbb{R},\mathbf{x},\mathbf{y}\in \mathcal{V}:\lambda \cdot (\mathbf{x}+\mathbf{y})=\lambda \cdot \mathbf{x}+\lambda \cdot \mathbf{y}$

   • $\forall \lambda ,\psi \in \mathbb{R},\mathbf{x}\in \mathcal{V}:(\lambda +\psi )\cdot \mathbf{x}=\lambda \cdot \mathbf{x}+\psi \cdot \mathbf{x}$

3. Associativity : $\forall \lambda ,\psi \in \mathbb{R},\mathbf{x}\in \mathcal{V}:\lambda \cdot (\psi \cdot \mathbf{x})=(\lambda \psi )\cdot \mathbf{x}$

4. Neutral Item wrt outer operation: $\forall \mathbf{x}\in \mathcal{V}:1\cdot \mathbf{x}=\mathbf{x}$

Analysis and Topology

Preliminaries:

Vectors : $x:=(x_1,\cdots ,x_k)$, where $x_i\in \mathbb{R}$

Metric Spaces

Definition.

$$d_2(x,y):={\Vert x-y\Vert }_2:={\left(\sum _{i=1}^k(x_i-y_i{)}^2\right)}^{1/2}$$

Requirements for a metric(e.g. $d_2:{\mathbb{R}}^2\times \mathbb{R}\to \mathbb{R}\forall x,y,v\in {\mathbb{R}}^k$):

• $d_2(x,y)=0⟺x=y$ : a point is at zero distance from itself

• $d_2(x,y)=d_2(y,x)$ : distance is symmetric

• $d_2(x,y)\le d_2(x,v)+d_2(v,y)$ : triangle inequality

We can generalise this definition to arbitrary nonempty sets $S$.

Definition. A metric space is a nonempty set $S$ and a metric of distance $\rho :S\times S\to \mathbb{R}\forall x,y,v\in S\text{ s.t. }$

• $\rho (x,y)=0⟺x=y$

• $\rho (x,y)=\rho (y,x)$

• $\rho (x,y)\le \rho (x,v)+\rho (v,y)$

For example, $({\mathbb{R}}^k,d_2)$ is a metric space. Many additional metric spaces in ${\mathbb{R}}^k$ are generated by a norm.

Definition. A norm on $X\subseteq {\mathbb{R}}^k$ is a mapping $X\ni x\mapsto \Vert x\Vert \in \mathbb{R}\text{ s.t. }\forall x,y\in {\mathbb{R}}^k\text{ and }\gamma \in \mathbb{R}$ satisfying

• Nonnegativity: $\Vert x\Vert \ge 0\forall xinX$

• Non degeneracy: $\Vert x\Vert =0⟺x=0$

• Homogeneity: $\Vert \gamma x\Vert =\left|\gamma \right|\Vert x\Vert$

• Triangle Inequality: $\Vert x+y\Vert \le \Vert x\Vert +\Vert y\Vert$

Each norm $\Vert .\Vert$ on ${\mathbb{R}}^k$ generates a metric $\rho$ on ${\mathbb{R}}^k$ via $\rho (x,y):=\Vert x-y\Vert$.

E.g. ${\Vert x\Vert }_2:=({\sum }_{i=1}^k{x}_i^2{)}^{1/2}$ generates Euclidean distance $d_2$.

The pair $\left(X,\Vert \cdot \Vert \right)$ consisting of a vector space $X$ together with a norm $\Vert \cdot \Vert$ is called a normed linear space.

Definition. A Banach space $(X,\Vert \cdot \Vert )$ is a normed linear space that is a complete (in the Cauchy-convergence sense) metric space with respect to the metric derived from its norm.

Definition. Also known as Minkowski Norm

A class of norms that includes ${\Vert .\Vert }_2$ as a special case is the ${\Vert \cdot \Vert }_p$ norm defined by

$${\Vert x\Vert }_p:={\left(\sum _{i=1}^k{\left|x_i\right|}^p\right)}^{1/p},x\in {\mathbb{R}}^k$$

${\Vert \cdot \Vert }_p$ norms give rise to a class of metric spaces $({\mathbb{R}}^k,d_p)$ where $d_p(x,y):={\Vert x-y\Vert }_p\forall x,y\in {\mathbb{R}}^k$.

Examples:

• 1: Taxicab

• 2: Euclidian

• $\infty$: Chebychev

Definition. Frobinius Norm of a matrix $\mathbf{A}$ is

$${\Vert \mathbf{A}\Vert }_F=\sqrt{\sum _{i=1}^M\sum _{j=1}^N{a}_{ij}^2}=\sqrt{\mathrm{tr}({\mathbf{A}}^{\prime }\mathbf{A})}$$

Definition. $a,b\in \mathbb{R}$, $[a,b]$ denotes the set of real numbers satisfying $a\le x\le b$. $($ or $)$ denotes a strict inequality (i.e. closed from above or below).

If $\mathcal{S}\subset \mathbb{R}$ is bounded from above, $\exists y\text{ s.t. }x\le y\forall x\in \mathcal{S}$.. Then $y$ is the least upper bound or supremum of $\sup \left\{x:x\in \mathcal{S}\right\}$. If $\mathcal{S}$ is not bounded from above, we write ${\sup }_{x\in \mathcal{S}}=\infty$.

Similarly, the greatest lower bound of a set or infimum is denoted ${\inf }_{x\in \mathcal{S}}(x)\vee \inf \left\{x:x\in \mathcal{S}\right\}$

Definition. A sequence $x_1,x_2,\dots x_n$ is denoted by ${\left\{x_i\right\}}_{i=1}^{\infty }$ or $\left\{x_i\right\}$ when the range of the indices is clear.

Let $\left\{x_i\right\}$ be an infinite sequence of real numbers and $\exists S\text{ s.t. }(1)\forall \epsilon >0,\exists N\text{ s.t. }\forall n>N,x_n<S+\epsilon$ and $(2)\forall \epsilon >0\text{ and }M>0,\exists n>M\text{ s.t. }{x}_n>S-\epsilon$. Then, $S$ is the $\mathrm{limsup}\left\{x_n\right\}$.

If $\left\{x_n\right\}$ is not Bounded from above, $\mathrm{limsup}{x}_n=\infty$.

Definition. A sequence $(x_n)$ in a metric space $(S,\rho )$ is said to be a Cauchy sequence if, $\forall ϵ>0,\exists N\in \mathbb{N}\text{ s.t. }\rho (x_j,x_k)<ϵ$ whenever $j,k\ge N$ (intuitively, points in a Cauchy sequence get tighter together).

Let $(x_n)$ be a sequence of vectors in ${\mathbb{R}}^k$. Suppose for any $ϵ>0,\exists n\in \mathbb{N}\text{ s.t. }\forall p,q>n,\rho (x^p,x^q)<ϵ$. Then, $(x_n)$ has a limit.

More basic definition: $\{a_n{\}}_{n=1}^{\infty }\to A$ if $\forall ϵ>0,\exists N\text{ s.t. }\forall n\ge N,\left|a_n-A\right|<ϵ$

• $\{a_n{b}_n\}\to AB$

• $\{a_n+b_n\}\to A+B$

Sequences

Let $S=(S,\rho )$ be a metric space. A sequence $(x_n)\subset S$ is said to converge to $x\in S$ if $\forall ϵ>0,\exists N\in \mathbb{N}\text{ s.t. }n\ge N⟹\rho (x_n,x)<ϵ$.

Theorem. A sequence in $(S,\rho )$ can have at most one limit

Definition. centered on $x\in S$ with radius $ϵ>0$ is the set

$B(ϵ,x):=\{z\in S:\rho (z,x)<ϵ\}$

Set Definitions

Definition. A subset $E$ of $S$ is called bounded if $E\subset B(n,x)$ for some $x\in S$ and some suitably large $n\in \mathbb{N}$ (intuition - some arbitrarily large $ϵ$ ball can fit $E$ inside it).

A sequence $(x_n)$ in $S$ is called bounded if its range $\{x_n:n\in \mathbb{N}\}$ is a bounded set.

Definition. A set $F\subset S$ is closed IFF for every convergent sequence contained in $F$, the limit of the sequence is also in $F$.

A closed set contains all its limit points. That is , if $(x_k)$ is a convergent sequence of points in $S$, then ${\lim }_{k\to \infty }{x}_k$ is in S as well.

Definition. A subset of an arbitrary metric space $S$ is open iff its complement is closed, and closed iff its complement is open.

A set $S\in {\mathbb{R}}^k$ is called open if, $\forall x \in S \exists \epsilon

0 \suchthat y \in B(\epsilon, x), \rho(x,y) < \epsilon$ is in S.

If $F$ is a closed, bounded subset of $(\mathbb{R},\Vert .\Vert )$, then $\sup F\in F$.

• A set $S\subset {\mathbb{R}}^k$ is open iff its complement is closed.

• the union of any number of open sets is open

• the intersection of a finite number of open sets is open.

• the intersection of any number of closed sets is closed

• the union of a finite number of closed sets is closed.

Definition. A point $x\in S$ is called an interior point of $S$ if the set $\{y:\rho (y,x)<ϵ\}$ is contained in $S$ for all $ϵ>0$ sufficiently small. A point is called a boundary point if $\{y:\rho (y,x)<ϵ\}\cap S^c$ is non-empty for all $ϵ>0$ sufficiently small. The set of all boundary points in $\mathcal{A}$ is denoted by $\partial \mathcal{A}$.

The closure of a set $S$ is the set $S$ combined with all points that are the limits of sequence of points in $S$.

Definition. A subset $A\subset S$ is said to be complete iff every cauchy sequence in A converges to some point in $A$.

Definition. The set $K\subset S$ is called compact if every sequence contained in $K$ has a subsequence that converges to a point in $K$.

Definition. A set $S\subset {\mathbb{R}}^k$ is called convex if, $\forall \lambda \in [0,1]$ and $a,a^{\prime }\in S$, we have $\lambda a+(1-\lambda )a^{\prime }\in S$. (i.e. all convex combinations of two points in a set are also in the set).

Theorem. Every bounded sequence in Euclidean space $({\mathbb{R}}^k,d_2)$ has at least one convergent subsequence.

Theorem. A subset of $({\mathbb{R}}^k,d_2)$ is precompact in that same space iff it is bounded and compact.

IOW : Compact $⟺$ Closed $\wedge$ Bounded

Theorem. All metrics on ${\mathbb{R}}^k$ induced by a norm are equivalent.

Functions

A function $f$ from set $A$ to $B$, written as $A\ni x\mapsto f(x)\in B$ or $f:A\to B$ is a rule associating every element in A to one and only one element in $B$. The point $b$ is also written as $f(a)$, and is called the image of $a$ under $f$. For $D\subset B$, the set $f^{-1}(D)$ is the set of all points in A that map into D under F, and is called the preimage of D under F. $f^{-1}(D):=\{a\in A:f(a)\in D\}$

a function $f:A\to B$ is called

• injective / one-to-one if distinct elements of $A$ are always mapped into distinct elements of $B$

• surjective / onto if every element of B is the image under $f$ of at least one point in $A$

• bijective if a function is both injective and surjective

Definition. A real valued function $f$ on ${\mathbb{R}}^k$ is continuous at point $a$ if $\forall ϵ>0,\exists \delta >0\text{ s.t. }\rho (x,a)<\delta ⟹\left|f(x)-f(a)\right|<ϵ$.

Equivalently, ${\lim }_{x\to a}f(x)=f(a)$

A function is said to be continuous on the set $S\subset {\mathbb{R}}^k$ if, $\forall a\in S\wedge \forall ϵ>0,\exists \delta >0\text{ s.t. }\forall \{x:\rho (x,a)<\delta \},\left|f(x)-f(a)\right|<ϵ$. Equivalently, in ${\lim }_{x\to a}f(x)$, we require the sequence of points that converge to $a$ to be entirely in $S$.

• The sum of two continuous functions is continuous

• The product of two continuous functions is continuous

• The quotient of two continuous functions is continuous at any point where the denominator is nonzero

Definition.

$$\underset{x\to c}{\lim }f(x)=L⟺\forall \epsilon >0,\exists \delta >0,\text{ s.t. }0<|x-c|<\delta \Rightarrow |f(x)-L|<\epsilon$$

Definition. Given two metric spaces $(\mathcal{X},{\rho }_X)$, $(\mathcal{Y},{\rho }_Y)$, a function $f:\mathcal{X}\to \mathcal{Y}$ is called Lipschitz continuous if $\exists K\in \mathbb{R}\text{ s.t. }\forall x_1,x_2\in \mathcal{X}$, ${\rho }_Y(f(x_1),f(x_2))\le K{\rho }_X(x_1,x_2)$

such a $K$ is referred to as a Lipschitz constant for the function $f$.

A Real valued function $f:\mathbb{R}\to \mathbb{R}$ is Lipschitz if $\exists K>0$ such that $\left|f(x_1)-f(x_2)\right|\le K|x_1-x_2|$

This limits how fast a function can change. Every function that has bounded first derivatives is Lipschitz continuous. A differentiable function is Lipschitz if and only if it has a bounded derivative.

Definition. A function defined on $\mathcal{X}$ is said to be Holder of order $\alpha >0$ if $\exists M\ge 0$ such that ${\rho }_Y(f(x),f(y))\le M{\rho }_X(x,y{)}^{\alpha }\forall x,y\in \mathcal{X}$

this is also called Uniform Lipschitz.

Theorem. A function f $S\to Y$ is continuous iff the preimage $f^{-1}(G)$ of every open set $G\subset Y$ is open in $S$.

Definition. $f$ is continuous if $\forall ϵ>0$, $\exists \delta >0$ $\text{ s.t. }\left|x-x_0\right|<\delta \forall x⟹\left|f(x)-f(x_0)\right|<ϵ$.

Theorem. Let function f $S\to Y$, where $S,Y$ are metric spaces and $f$ is continuous. If $K\subset S$ is compact, then so is $f(K)$, the image of $K$ under $f$.

Result.

$$\Gamma (\alpha ):={\int }_0^{\infty }{t}^{\alpha -1}{e}^{-t}dt={\int }_0^1{\left(\log (1/t)\right)}^{\alpha -1}dt$$

Beta function : $B(\alpha ,\beta )=\Gamma (\alpha )\cdot \Gamma (\beta )/\Gamma (\alpha +\beta )$

Theorem. Let $f:k\to \mathbb{R}$, where $K\subset (S,\rho )$ (an arbitrary metric space). If $f$ is continuous and $K$ is compact, then $f$ attains its supremum and infimum on $K$.

In case of continuous functions on compact domains, optima always exist.

Definition. The function $f:\mathbb{R}\to \mathbb{R}$ is differentiable at $x_0$ if $\exists \lim R(x)=\frac{(f(x)-f(x_0))}{(x-x_0)}=f^{\prime }(x_0)$, i.e. $(f(x)-f(x_0))/(x-x_0)$ has a limit as $x\to x_0$.

The derivative of $f$ at $x_0$ is this limit and is denoted $f^{\prime }(x_0)$ or $\frac{\partial f}{\partial x}{|}_{x=x_0}$

Theorem. Differentiability $\subset$ Continuity $\subset$ $\exists$ Limit i.e. not all functions with limits are continuous, not all continuous functions are differentiable.

More generally,

Continuously Differentiable $\subset$ Lipschitz Continuous $\subset$ $\alpha -$ Holder Continuous $\subset$ Uniformly Continuous $\subset$ Continuous

Theorem.

• Linearity: $f,g:X\to Y$ are differentiable at $\mathbf{x}$, then $f+g$ and $\alpha f$ are differentiable at $x$ with $\nabla (f+g)(x)=\nabla f(x)+\nabla g(x)$ and $\nabla (\alpha f)(x)=\alpha \nabla f(x)$.

• Chain Rule: If $f$ and $g$ are differentiable, then $g\circ f$ is differentiable and $\nabla (g\circ f)(x)=\nabla g(f(x))\nabla f(x)$.

Theorem. Let $f:[a,b]\to \mathbb{R}$, $f$ is continuous and differentiable. $f(a)=f(b)⟹\exists c\in [a,b]\text{ s.t. }{f}^{\prime }(c)=0$.

Theorem. $f:[a,b]\to \mathbb{R}$, $f$ is continuous and differentiable. Then,

$f^{\prime }(c)=\frac{f(b)-f(a)}{b-a}$

Definition. The epigraph of a function $f$ is $\text{epi}f:=\left\{(x,t):\right\}f(x)\le t$ (i.e. area above the function).

Definition. Let $f:[a,b]\to \mathbb{R},x,y\in [a,b];t\in (0,1)$. Then,

• F is convex if $f((1-t)x+ty)\le (1-t)f(x)+tf(x)$. $f^{\prime \prime }\ge 0$: i.e. the epigraph of $f$ is a convex set.

• F is concave if $f((1-t)x+ty)\ge (1-t)f(x)+tf(x)$. $f^{\prime \prime }\le 0$

Fixed Points

Definition. Let $T:S\to S$, where $S$ is any set. An $x^{\ast }\in S$ is called a fixed point of $T$ on S if $T{x}^{\ast }=x^{\ast }$.

If $S\subset \mathbb{R}$, then fixed points of $T$ are those points in $S$ where $T$ meets the 45 degree line.

Theorem. Consider the space $({\mathbb{R}}^k,d)$, where $d$ is the metric induced by any norm. Let $S\subset {\mathbb{R}}^k$, and let $T:S\to S$. If $T$ is continuous and $S$ is both compact and convex, then $T$ has at least one fixed point in S.

Definition. Let $(S,\rho )$ be a metric space. $T:S\to S$ is a map. it is called

• nonexpansive if $\rho (Tx,Ty)\le \rho (x,y)\forall x,y\in S$

• contracting if $\rho (Tx,Ty)<\rho (x,y)\forall x,y\in S,x\ne y$

• uniformly contracting with modulus $\lambda \in [0,1)$ if $\rho (Tx,Ty)<\lambda \rho (x,y)\forall x,y\in S,x\ne y$

Theorem. Let $T:S\to S$, where $(S,\rho )$ is a complete metric space. If $T$ is a uniform contraction on $S$ with modulus $\lambda$, then $T$ has a unique fixed point $x^{\ast }\in S$. Moreover for every $x\in S$ and $n\in \mathbb{N}$, we have $\rho (T^{n}x,x^{\ast })\le {\lambda }^n\rho (x,x^{\ast })⟹T^{n}x\to x^{\ast }\text{ as }n\to \infty$

Measure

Definition. A $\sigma$-algebra (also $\sigma$-field) is a collection $\mathcal{F}$ of subsets of $\Omega$ that

• $\Omega \in \mathcal{F}\wedge \varnothing \in \mathcal{F}$: includes $\Omega$ itself and the null set

• $A\in \mathcal{F}⟹\Omega -A=:A^C\in \mathcal{F}$: is closed under complement

• $A_1,A_2,\cdots \in \mathcal{F}⟹{\bigcup }_{i=1}^{\infty }{A}_i\in \mathcal{F}$ : is closed under countable unions.

This is effectively the definition of the event space $\mathcal{S}$ for a sample space $\Omega$.

Definition. A measure $\mu$ on a set $\mathcal{X}$ assigns a nonnegative value $\mu (A)$ to many subsets of $\mathcal{X}$. For a collection $\mathcal{F}$ subsets of $\Omega$, a measure is a map

$\mu :\mathcal{F}\to [0,\infty ]$

Given $A\in \mathcal{F},\mu (A)$ is a measure of the ‘size’ of set $A$.

A function $\mu$ on a $\sigma -$ field $\mathcal{A}$ of $\mathcal{X}$ is a measure of

• Null empty-set: $\mu (\varnothing )=0$

• Non-Negativity: $\forall A\in \mathcal{A},0\le \mu (A)\le \infty ⟹\mu :\mathcal{A}\to [0,\infty ]$

• Countable Additivity: If $A_1,A_2,\dots$ are disjoint elements of $\mathcal{A}$ (i.e. $A_i\cap A_j=\varnothing \forall i\ne j$), $\mu \left({\bigcup }_{i=1}^{\infty }{A}_i\right)={\sum }_{i=1}^{\infty }\mu (A_i)$

Existence ensured by Caratheodory’s Extension Theorem.

Examples of measures $\mu$:

• If $\mathcal{X}$ is countable, let $\mu (A)=\#A=$ number of points in A. This counting measure can be defined for any subset $A\subset \mathcal{X}$, then the $\sigma -$ field $\mathcal{A}$ is the collection of all subsets of $\mathcal{X}=:\mathfrak{X}=2^{\mathcal{X}}$, the power set of $\mathcal{X}$.

• If $\mathcal{X}={\mathbb{R}}^k$, define $\mu (A)=\int {\dots }_A\int d{x}_1\dots d{x}_k$

Definition. Given a topology on $\Omega$, a Borel $\sigma$-field is a $\sigma$ field generated by the family of open subsets of $\Omega$, i.e. the smallest $\sigma$ field that contains all the open sets.

The Lebesgue measure of a set $A$ can be defined implicitly for any set B in a $\sigma -$ field $\mathcal{B}$ called the Borel sets of ${\mathbb{R}}^n$. $\mathcal{B}$ is the smallest $\sigma -$ field that contains all ‘rectangles’

$$(a_1,b_1)\times \cdots \times (a_n,b_n):=\{x\in {\mathbb{R}}^n:a_i<x_i<b_i,i=1,\dots ,n\}$$

Result. Suppose $\Omega =\mathbb{R}$. We say that $I\subset \mathbb{R}$ is a bounded interval if $\exists a,b,a<b\text{ s.t. }I\in \left\{[a,b],(a,b),(a,b],[a,b)\right\}$. Define ${\mathcal{C}}^1:=\left\{I\subset \mathbb{R},I\text{ is a bounded interval}\right\}$, the smallest $\sigma -$ algebra that contains ${\mathcal{C}}^1$ is denoted by ${\mathcal{B}}^1$ and is called the Borelian $\sigma -$algebra

Thus, a countable union of open intervals belongs to the Borelean $\sigma$-algebra. Since every open subset of $\mathbb{R}$ can be written as a countable union of open intervals, it is therefore also a Borelean set. The closed subsets are Borelean since a closed set is the complement of an open set.

Definition. Basic problem: how to assign each subset of ${\mathbb{R}}^k$, i.e. each element of $\mathfrak{P}({\mathbb{R}}^k)$ a real number that will represent its ‘size’.

With ${\mathbb{R}}^n,n=1,2,3$, $\mu (A)$ is the length, area, or volume of $A$, respectively. $\mu$ is a Lebesgue measure on ${\mathbb{R}}^k$.

Definition. If $\mathcal{A}$ is a $\sigma -$field of subsets of $\mathcal{X}$, the pair $(\mathcal{X},\mathcal{A})$ is called a measurable space, and if $\mu$ is a measure on $\mathcal{A}$, the triple $(\mathcal{X},\mathcal{A},\mu )$ is called a measure space.

Definition. A measure $\mu$ is called a probability measure if $\mu (\mathcal{X})=1$, and then the triple $(\mathcal{X},\mathcal{A},\mu )$ is called a probability space.

Definition. If $(\mathcal{X},\mathcal{A})$ is a measurable space and $f$ is a real-valued function on $\mathcal{X}$, $f$ if measureable if

$f^{-1}(B):=\{x\in \mathcal{X}:f(x)\in B\}\in \mathcal{A}$

for every Borel set $B$.

Integration

An integral is a map assigning a number to a function, where the number is viewed as the area/volume ‘under’ the function. Given a measure space $(\Omega ,\mathcal{F},\mu )$ and a measureable function $f:\Omega \to \mathbb{R}$, an integral $\int fd\mu$ is a map from $f$ to number such that the following three properties hold

• If $f\ge 0$, then $\int fd\mu \ge 0$

• $\forall a\in \mathbb{R},\int a\varphi d\mu =a\int \varphi d\mu$

• $\int (f+g)d\mu =\int fd\mu +\int gd\mu$

Definition. Suppose $f$ is a bounded function defined on $[a,b]$. An increasing sequence $P:=\left\{a=x_0<x_1<x_2<\cdots <x_n=b\right\}$ defines a partition of the interval. The mesh size of the partition is defined to be

$\left|P\right|=\max \left\{\left|x_i-x_{i-1}\right|:i=1,\dots ,N\right\}$

To each partition we associate two approximations of the area under the graph of $f$, by the rules

$U(f,P):={\sum }_{j=1}^N{\sup }_{x\in [x_{j-1},x_j]}f(x)(x_j-x_{j-1})$

$L(f,P):={\sum }_{j=1}^N{\inf }_{x\in [x_{j-1},x_j]}f(x)(x_j-x_{j-1})$

these are called the upper and lower Riemann Sums For any partition, $U(f,P)\ge L(f,P)$.

Definition. A bounded function $f$ defined on an interval $[a,b]$ is said to be Riemann integrable if

${\inf }_{P}U(f,P)={\sup }_{P}L(f,P);{\int }_a^{b}f(x)dx=:\text{Riemann Integral}$

Suppose $f$ is piecewise continuous, defined on $[a,b]$. Then, $f$ is Riemann integrable and

$${\int }_a^{b}f(x)dx=\underset{N\to \infty }{\lim }\sum _{j=1}^{N}f\left(a+\frac{j}{N}(b-a)\right)\frac{b-a}{N}$$

Theorem. If $f$ is continuous on $[a,b]$ then $F(x):={\int }_a^{x}f(t)dt$ is differentiable on the open interval $(a,b)$ and $F^{\prime }(x)=f(x)\forall x\in (a,b)$. $F$ is called the anti-derivative.

${\int }_a^{b}f(t)dt=F(b)-F(a)$

Definition. Given a measurable space $(\Omega ,\mathcal{F})$ and a set $E\in \mathcal{F}$, we define an indicator function $f_e:\Omega \to \mathbb{R}$ defined by

$f_E(\omega )=1_{\omega \in E}$

This function is measurable.

Definition. Any function $f$ of the form $f(\omega ){\sum }_{i=1}^n{a}_i{1}_{\omega \in E_i}\forall a_i\in \mathbb{R}\wedge E_1,\dots ,E_n\in \mathcal{F}$, where ${\left\{E_i\right\}}_{i=1}^n$ is a finite partition of $\Omega$. A countable sum of measurable functions is measurable, which implies that $f$ is measurable. Then we define

$\int fd\mu :={\sum }_{i=1}^n{a}_i\mu (E_i)$

Definition. For any measurable function $f$, define $f^{+}:=\max \left\{f,0\right\}$ and $f^{-}:=\max \left\{-f,0\right\}$, which are also measurable. We also have $f=f^{+}-f^{-}$ and $\left|f\right|=f^{+}+f^{-}$. When at least one of $\int f^{+}d\mu$ or $\int f^{-}d\mu$ is finite, we define the integral

$\int fd\mu :=\int f^{+}d\mu -\int f^{-}d\mu$ When both $\int f^{+}d\mu$ and $\int f^{-}d\mu$ are finite, we say $f$ is integrable w.r.t. $\mu$. Lebesgue integrals intuitively slice the function horizontally, while Riemann integrals slice vertically.

Probability Theory

Definition. The triple $(\Omega ,\mathcal{S},P)$ is a probability space if it satisfies the following

• Unitarity: $\mathbf{Pr}\left(\Omega \right)=1$

• Non Negativity: $\forall s\in S,\mathbf{Pr}\left(a\right)\ge 0\mathbf{Pr}\left(a\right)\in \mathbb{R}\wedge \mathbf{Pr}\left(a\right)<\infty$

• Countable Additivity: If $A_1,A_2,\dots ,\in S$ are pairwise disjoint[i.e. $\forall i\ne j,A_i\cap A_j=\varnothing$], Then $\text{P}\left({\bigcup }_{i=1}^{\infty }{A}_i\right)={\sum }_{i=1}^{\infty }\text{P}(A_i)$

Other properties for any event $A,B$

• $A\subset B⟹\mathbf{Pr}\left(A\right)\le \mathbf{Pr}\left(B\right)$

• $\mathbf{Pr}\left(A\right)\le 1$

• $\mathbf{Pr}\left(A\right)=1-\mathbf{Pr}\left(A^c\right)$

• $\mathbf{Pr}\left(\varnothing \right)=0$

Stated differently:

Definition. Let $P$ be a probability measure on a measurable space $(\mathcal{E},\mathcal{B})$, so $(\mathcal{E},\mathcal{B},P)$ is a probability space. Sets $B\in \mathcal{B}$ are called events, points $e\in \mathcal{E}$ are called outcomes, and $P(B)$ is called the probability of B.

Let $(\mathcal{E},\mathcal{B})$ be a measurable space. Let $\mathbb{P}:\mathcal{B}\to [0,1]$ be a ‘set’ function mapping the $\sigma -$ algebra of subsets of $\mathcal{E}$ into the real line. We say $\mathbb{P}$ is a probability measure if, for events $A,B\in \mathcal{E}$,

1. $0\le \mathbf{Pr}\left(A\right)\le 1$: Events range from never happening to always happening

2. $\mathbf{Pr}\left(\mathcal{E}\right)=1$: Something must happen

3. $\mathbf{Pr}\left(\varnothing \right)=0$: Nothing never happens

4. $\mathbf{Pr}\left(A\right)+\mathbf{Pr}\left(A^c\right)=1$: A must either happen or not happen

5. $\mathbf{Pr}\left({\cup }_{n=1}^{\infty }{A}_n\right)={\sum }_{n=1}^{\infty }\mathbf{Pr}\left(A_n\right)$: $\sigma -$ additivity for countable disjoint events

   • Boole’s Inequality $\mathbf{Pr}\left({\cup }_{n=1}^{\infty }{A}_n\right)\le {\sum }_{n=1}^{\infty }$ for any sequence of events

6. Monotonicity: for events $A,B;A\subseteq B⟹\mathbf{Pr}\left(A\right)\le \mathbf{Pr}\left(B\right)$

Definition. A measurable function $X:\Omega \to \mathbb{R}\text{ s.t. }\forall r\in \mathbb{R},\left\{\omega \in \Omega :X(\omega )\le r\right\}\in \mathcal{E}$ (event space) is called a random variable. In other words, a random variable is a function from the sample space to the real line $\mathbb{R}$, and the probability of its value being in a given interval is well defined.

Definition. The probability measure $P_X$ living on $(\mathbb{R},\mathcal{B}(\mathbb{R}))$ such that for any $A\in \mathcal{B}(\mathbb{R})$,

$P_X(A)=P(\{e\in \mathcal{E}:X(e)\in A\})=:P(X\in A)$

for Borel sets $A$ is called the distribution of $X$. The notation $X\sim Q$ is used to indicate that $X$ has distribution $Q⟹P_X=Q$.

Definition. Map $\mathbb{F}:\mathbb{R}\to [0,1]$ such that

$$F_X(x)=P(X\le x)=:P_X((-\infty ,x])$$

for $x\in \mathbb{R}$

Properties of CDF $\mathbb{F}\left(u\right)$

• Boundary property: ${\lim }_{u\to -\infty }\mathbb{F}\left(u\right)=0,{\lim }_{u\to \infty }\mathbb{F}\left(u\right)=1$

• Nondecreasing: $\mathbb{F}\left(x\right)\le \mathbb{F}\left(y\right)$ if $x\le y$

• Right continuous: ${\lim }_{u\downarrow x}\mathbb{F}\left(u\right)=\mathbb{F}\left(x\right)$

Densities

Theorem. If a finite measure $P$ is absolutely continuous wrt a $\sigma -$ finite measure $\mu$, then $\exists$ a nonnegative measurable function $f$ s.t.

$P(A)={\int }_{A}fd\mu =:\int f{1}_{A}d\mu$

The function $f$ in this theorem is called the Radon-Nikodym derivative of $P$ with respect to $\mu$, or the density of $P$ with respect to $\mu$, denoted

$f=\frac{dP}{d\mu }$

Definition. If a random variable has density $p$ wrt Lebesgue measure on $\mathbb{R}$, then $X$ or its distribution $P_X$ is called absolutely continuous with density $p$. Then, from R-N ,

$F_X(x)=P(X\le x)=P_X((-\infty ,x])={\int }_{-\infty }^{x}p(u)du$

Using the fundamental theorem of calculus, $p$ can be found from the CDF $F_X$ by differentiation, $p(x)=F_X^{\prime }(x)$.

Definition. Let ${\mathcal{X}}_0$ be a countable subset of $\mathbb{R}$. The measure $\mu :=\mu (B)=\#(\mathcal{X}\cap B)$ for borel sets $B$ is also called counting measure on ${\mathcal{X}}_0$. Then,

$\int fd\mu ={\sum }_{x\in {\mathcal{X}}_0}f(x)$

Suppose $X$ is a random variable s.t. $P(X\in {\mathcal{X}}_0)=P_X({\mathcal{X}}_0=1)$. Then, $X$ is called a discrete random variable.

The density $p$ of $P_X$ w.r.t. $\mu$ satisfies

$$P(X\in A)=P_X(A)={\int }_{A}pd\mu =\sum _{x\in {\mathcal{X}}_0}p(x)1_A(x)$$

In particular, if $A=\{y\}\text{ s.t. }y\in {\mathcal{X}}_0$, then $X\in A⟺X=y$, and so

$$P(X=y)=\sum _{x\in {\mathcal{X}}_0}p(x)1_{\{y\}}(x)=p(y)$$

The density $p$ is called the mass function for X.

Moments

Definition. If $X$ is a random variable on a probability space $(\mathcal{E},\mathcal{B},P)$, then the expectation of $X\sim P_X$ (i.e. density $p$), is defined as

$\mathbb{E}\left[X\right]:=\int XdP=\int xd{P}_X(x)=\int xp(x)d(x)$

For discrete RV $X$ with $P(X\in {\mathcal{X}}_0)=1$ for a countable set ${\mathcal{X}}_0$, if $\mu$ is counting measure on ${\mathcal{X}}_0$, and $p$ is the mass function given by $p(x)=P(X=x)$,

$$\mathbb{E}\left[X\right]:=\int xd{P}_X(x)=\int xp(x)d\mu (x)=\sum _{x\in {\mathcal{X}}_0}xp(x)$$

Definition. The variance of a random variable $X$ with finite expectation is defined as

$\mathbb{V}\left[X\right]=\mathbb{E}{\left[X-\mathbb{E}\left[X\right]\right]}^2$

If $X$ is absolutely continuous with density $p$,

$\mathbb{V}\left[X\right]=\int (x-\mathbb{E}\left[X\right]{)}^{2}p(x)dx$

If $X$ is discrete with mass function $p$,

$\mathbb{V}\left[X\right]={\sum }_{x\in {\mathcal{X}}_0}(x-\mathbb{E}\left[X\right]{)}^{2}p(x)$

Random vectors

If $X_1,\dots ,X_n$ are random variables, then the function $X:\mathcal{E}\to {\mathbb{R}}^n$ defined by

$$X(e)=\left(\begin{array}{c}{X}_1(e)\\ ⋮\\ X_n(e)\end{array}\right),e\in \mathcal{E}$$

is called a random vector. The definitions above extend naturally to random vectors, e.g. the distribution $P_X$ of $X$ is

$P_X(B)=P(X\in B):=P(\{e\in \mathcal{E}:X(e)\in B\})$

for Borel sets $B\in {\mathbb{R}}^n$. The expectation of a random vector $X$ is the vector of expectations

$$\mathbb{E}[X]=\left[\begin{array}{c}\mathbb{E}[X_1]\\ ⋮\\ \mathbb{E}[X_n]\end{array}\right]$$

A random vector is said to be absolutely continuous if the CDF can be written as

$$\mathbb{F}\left(x_1,x_2,\dots ,x_n\right)={\int }_{-\infty }^{x_1}{\int }_{-\infty }^{x_2}\cdots {\int }_{-\infty }^{x_n}f(z_1,\dots ,z_n)d{z}_1\dots d{z}_n$$

Definition. A matrix $W$ is called a random matrix if the entries $W_{ij}$ are random variables.

Definition. The covariance of a random vector $X$ is the matrix of covariances of the variables in $X$

$[\mathrm{Cov}\left((\right)X){]}_{ij}=\mathrm{Cov}\left((\right)X_i,X_j)$

If $\mu =\mathbb{E}\left[X\right]$ and $(X-\mu {)}^{\prime }$ is the transpose of the mean deviation, then

$$\mathrm{Cov}(X_i,X_j):=\mathbb{E}\left[(X_i-{\mu }_i)(X_j-{\mu }_j)\right]={\left[\mathbb{E}\left[(X-\mu )(X-\mu {)}^{\prime }\right]\right]}_{ij}$$

so

$$\mathrm{Cov}(X)=\mathbb{E}\left[(X-\mu )(X-\mu {)}^{\prime }\right]=\mathbb{E}[X{X}^{\prime }]-\mu {\mu }^{\prime }$$

Product Measures and Independence

Let $(\mathcal{X},\mathcal{A},\mu )$ and $(\mathcal{Y},\mathcal{B},\nu )$ be measure spaces. Then $\exists$ a unique product measure $\mu \times \nu$ on $(\mathcal{X}\times \mathcal{Y},\mathcal{A}\vee \mathcal{B})$ such that $(\mu \times \nu )(A\times B)=\mu (A)\nu (B)\forall A\in \mathcal{A},B\in \mathcal{B}$. The $\sigma$-field $\mathcal{A}\vee \mathcal{B}$ is defined formally as the smallest $\sigma -$ field containing all sets $A\times B$ with $A\in \mathcal{A}$ , $B\in \mathcal{B}$.

Theorem. Integration against the product measure $\mu \times \nu$ can be accomplished by iterated integration against $\mu$ and $\nu$, in either order

$$\int f(x,y)d(\mu \times \nu )=\int \left[\int f(x,y)d\nu (y)\right]d\mu (x)=\int \left[\int f(x,y)d\mu (x)\right]d\nu (y)$$

Definition. Suppose $X_i:\Omega \to \mathbb{R},1\le i\le m$ are random variables.

$X_1,X_2,\dots ,X_m$ are indepepndent for all $B_1,B_2,\dots ,B_m$ Borel subsets of $\mathbb{R}$, it is true that

$$\mathbf{Pr}\left(X_i\in B_i,\forall i1\le i\le m\right)=\mathbf{Pr}\left(X_1\in B_1\right)\dots \mathbf{Pr}\left(X_m\in B_m\right)$$

Conditional Expectations

Definition. Given two r.v.s $X,Y$ with finite second moments, $\mathbb{E}\left[Y|X\right]$ is defined as a $\sigma (X)-$ measurable function $m(X)$ such that

$m(.){\mathrm{argmin}}_h{\mathbb{E}}_{\mathbb{P}}{\left[Y-m(X)\right]}^2$

For continuous $X,Y\in {\mathbb{R}}^2$ with pdf $f(x,y)$, For any $y^{\ast }\in \mathbb{R}$, the conditional probability of the event $\left\{Y\le y^{\ast }\right\}:={\mathbb{P}}_{Y|X}(Y\le y^{\ast }|x)$ is defined as a function satisfying

$${\int }_{-\infty }^{x^{\ast }}{\mathbb{P}}_{Y|X}(Y\le y^{\ast }\mid x)f_X(dx)={\mathbb{P}}_{XY}(X\le x^{\ast },Y\le y^{\ast }),\forall x^{\ast }\in \mathbb{R}$$

The conditional CDF is

$${\mathbb{F}}_{Y|X}(y^{\ast })={\mathbb{P}}_{Y|X}(Y\le y^{\ast }\mid x)={\int }_{-\infty }^{y^{\ast }}\frac{f(x,y)}{f_X(x)}dy$$

where the conditional density is $f(y\mid x)=f(x,y)/f_X(x)$.

Definition. Let $X\sim F_X;Y\sim F_Y$. Define the class of ‘Bounded Lipschitz functions’ with Lipschitz constant 1 as

$$BL(1):=\left\{h:\mathbb{R}\to \mathbb{R}\text{ s.t. }\left|h(x)-h(y)\right|\le \left|x-y\right|\wedge \underset{x\in \mathbb{R}}{\sup }\left|h(x)\right|\le 1\right\}$$

Then the Bounded Lipschitz Distance is

$$d_{BL}(F_X,F_Y):=\underset{h\in BL(1)}{\sup }\left|{\mathbb{E}}_{F_X}\left[h(X)\right]-{\mathbb{E}}_{F_Y}\left[h(Y)\right]\right|$$

$F_X$ and $F_Y$ are said to be ‘close’ if $d_{BL}(F_X,F_Y)$ is small.

Order Statistics

Theorem. Suppose $X_1,X_2,\dots ,X_n$ are r.v.s with distribution ${\mathbb{F}}_x\left(\right)$. To each $\omega \in \Omega$ define $\max (X_1,\dots ,X_n)(\omega )=\max (X_1(\omega ),\dots ,X_n(\omega ))$. We want the distribution of $\max (X_1,\dots ,X_n)$.

$$G(r)=\mathbf{Pr}\left(\left\{\omega \in \Omega :\max (X_1,\dots ,X_n)\le r\right\}\right)=\mathbf{Pr}\left({\cap }_{i=1}^n[X_i\le r]\right)=\prod _{i=1}^n\mathbf{Pr}\left(X_i\le r\right)=\prod _{i=1}^{n}F(r)={\mathbb{F}}^n(r)$$

If $F$ has a density, $G$ has a density too

$g(r)=G^{\prime }(r)=n{\mathbb{F}}^{n-1}(r)\mathsf{f}\left(r\right)$

More generally, the distribution function of $X_{(m)}$ is given by ${\mathbb{F}}_{(m)}$

$${\mathbb{F}}_{(m)}(t)=\sum _{i=m}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)\mathbb{F}(t{)}^i(1-\mathbb{F}(t){)}^{n-i},-\infty <t<\infty$$

Reference: Severini (2005), Chapter 7.

Result. has a distribution with density $g(r)=n{r}^{n-1}$

Result. (Useful for Vickrey auctions)

$$\begin{array}{rl}{\mathbb{F}}_{Y^2}\left(r\right)& ={\mathbb{F}}^m(r)+m(1-\mathbb{F}(r)){\mathbb{F}}^{m-1}(r)\\ {\mathsf{f}}_{Y^2}\left(r\right)& =m(m-1)(1-\mathbb{F}(r)){\mathbb{F}}^{m-2}(r)\mathsf{f}(r)\end{array}$$

Linear Functions and Linear Algebra

Linear Functions

Definition. A function $f:X\to Y$ between two linear spaces $X,Y$ is linear if it preserves the linearity of sets $X$ and $Y$ through the following properties ($\forall {\mathbf{x}}_1,{\mathbf{x}}_2\in X$)

• Additivity $f({\mathbf{x}}_1+{\mathbf{x}}_2)=f({\mathbf{x}}_1)+f({\mathbf{x}}_2)$

• Homogeneity $f(\alpha {\mathbf{x}}_1)=\alpha f({\mathbf{x}}_1)$

• $f:V\to W$ linear and bijective is called an isomorphism

• A linear function that maps onto $\mathbb{R}$ is called a linear functional.

• A linear function that maps onto itself is called a linear operator / automorphism.

Every linear function mapping from a finite-dimensional domain $X$ can be represented by a matrix.

Theorem. Linear Functions $f(\alpha {\mathbf{x}}_1+(1-\alpha ){\mathbf{x}}_2)=\alpha f({\mathbf{x}}_1+(1-\alpha )f({\mathbf{x}}_2)$ Imply

• Additivity : $f({\mathbf{x}}_1+{\mathbf{x}}_2=f({\mathbf{x}}_1)+f({\mathbf{x}}_2)$ generalises to

  • Convex Functions $f(\alpha {\mathbf{x}}_1+(1-\alpha ){\mathbf{x}}_2)\le \alpha f({\mathbf{x}}_1)+(1-\alpha )f({\mathbf{x}}_2)$ generalises to

  • Quasiconvex functions $f(\alpha {\mathbf{x}}_1+(1-\alpha ){\mathbf{x}}_2)\le \min (f({\mathbf{x}}_1,{\mathbf{x}}_2)$

• Homogeneity: $f(\alpha \mathbf{x})=\alpha f(\mathbf{x})$ generalises to

  • Homogeneous functions $f(\alpha \mathbf{x})={\alpha }^{k}f(\mathbf{x}),\alpha >0$ generalises to

  • Homothetic functions $f({\mathbf{x}}_1)=f({\mathbf{x}}_2)⟹f(\alpha {\mathbf{x}}_1)=f(\alpha {\mathbf{x}}_2)\alpha >0$

Definition. An inner product on a vector space $V$ is a mapping $⟨\cdot ,\cdot ⟩:V\times V\to \mathbb{R}$ that satisfies, $\forall x,y,z\in V\wedge ain\mathbb{R}$

• $⟨x,x⟩\ge 0\text{ and }⟨x,x⟩=0⟺x=0$

• $⟨x,y+z⟩=⟨x,y⟩+⟨x,z⟩$

• $⟨x,ay⟩=a⟨x,y⟩$

• $⟨x,y⟩=⟨y,x⟩$

${\mathbf{x}}^{\prime }\mathbf{y}=⟨\mathbf{x},\mathbf{y}⟩:={\sum }_{i=1}^n{x}_i{y}_i$

This generalises to an inner product of two functionals $u,v:\mathbb{R}\to \mathbb{R}$ where

$⟨u,v⟩={\int }_a^{b}u(x)v(x)dx$

An inner product defines a norm $\Vert v\Vert =\sqrt{⟨v,v⟩}$. This gives us a restatement of the Cauchy-Schwartz inequality $\left|⟨x,y⟩\right|\le \Vert x\Vert \Vert y\Vert$

Definition.

1. $⟨x,y⟩=0⟹x\perp y$ (Orthogonality). Furthermore, if $\Vert \mathbf{x}\Vert =1=\Vert \mathbf{y}\Vert$, then they are said to be orthonormal.

2. $⟨x,y⟩=\pm 1⟹$ x parallel to y

Definition. $\mathbf{A}\in {\mathbb{R}}^{n\times n}$ is symmetric, positive definite if $\forall \mathbf{x}\in V:{\mathbf{x}}^{\prime }\mathbf{A}\mathbf{x}$ > 0.

Definition. For conformable matrices $\mathbf{A}$ and $\mathbf{B}$ with identical dimensions, the element-wise product

$$c_{ij}=a_{ij}\times b_{ij}\forall i,j\in \text{dim}(A)\equiv \mathbf{A}\odot \mathbf{B}$$

is called the Hadamard product.

Definition. Euclidian norm of a vector $\mathbf{x}\in {\mathbb{R}}^N$ is defined as $\Vert \mathbf{x}\Vert :=\sqrt{⟨\mathbf{x},\mathbf{x}⟩}$

Theorem. Angle between $\mathbf{u}$ and $\mathbf{v}$ is given by

$\cos \theta =\frac{⟨\mathbf{u},\mathbf{v}⟩}{\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert }$

Theorem. $\Vert ⟨x,y⟩\Vert \le \Vert x\Vert \Vert y\Vert$

Definition. $\text{Trace}(A)={\sum }_{n=1}^N{a}_{nn}$

For conformable matrices $A,B;\mathrm{tr}(AB)=\mathrm{tr}(BA)$

Definition. For a square matrix $A$, scalar $\lambda$ and vector $x$ that satisfies $Ax=\lambda x$ constitute an eigenvalue and eigenvector respectively.

Definition. A square matrix $\mathbf{A}\in {\mathbb{R}}^{n\times n}$ is orthogonal iff its columns are orthonormal so that

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

Definition. For $\mathbf{\Phi }:V\to W$, we define the kernel/null space as

$$\ker (\mathbf{\Phi }):={\mathbf{\Phi }}^{-1}(0_W)=\left\{\mathbf{v}\in V:\mathbf{\Phi }(\mathbf{v})=0_W\right\}$$

and the image/range

$$\text{Im}(\mathbf{\Phi }):=\mathbf{\Phi }(V)=\left\{\mathbf{w}\in W\mid \exists \mathbf{v}\in V:\mathbf{\Phi }(\mathbf{v})=\mathbf{w}\right\}$$

The dimension of the image is called the rank of $\mathbf{\Phi }$. The dimension of the kernel is called the nullity of $\mathbf{\Phi }$. If $\mathbf{X}$ is finite dimensional,

$\text{rank }\mathbf{\Phi }+\text{nullity }\mathbf{\Phi }=\text{dim}\mathbf{X}$

This is the rank-nullity result

A linear function $\Phi$ has full rank if $\mathrm{rank}\Phi (X)=\text{min}\{\mathrm{rank}X,\mathrm{rank}Y\}$.

Definition. Nonsingular Matrices

A matrix $\mathbf{A}\in {\mathbb{R}}_{n\times n}$ with columns ${\mathbf{a}}_1,\dots {\mathbf{a}}_n$ is non-singular or one-to-one if

$$\mathbf{A}\text{ is one-to-one}⟺\left\{{\mathbf{a}}_1,\dots ,{\mathbf{a}}_n\right\}\text{ is a basis}⟺\ker (\mathbf{A})=\left\{0\right\}$$

Projection

Definition. Let $V$ be a vector space and $U\subseteq V$ is a subspace of $V$. A linear mapping $\pi :V\to U$ is called a projection if ${\pi }^2=\pi \circ \pi =\pi$. Since homeomorphisms can be expressed by a transformation matrix, projections can be represented as a projection matrix ${\mathbf{P}}_{\pi }$ with the property ${\mathbf{P}}_{\pi }^2=\mathbf{P}$. Projection matrices are always symmetric.

Result. We look at orthogonal projections of vectors $\mathbf{y}\in {\mathbb{R}}^n$ onto lower dimensional subspaces $X\subseteq {\mathbb{R}}^n$ with $\dim (X)=m\ge 1$. Assume $({\mathbf{x}}_1,\dots ,{\mathbf{x}}_m)$ is an ordered basis of $X$. Therefore, any projection ${\pi }_U(\mathbf{x})={\sum }_{i=1}^m{\lambda }_i{x}_i=\mathbf{X}\mathbf{\lambda }$. The problem, then, is to find ${\lambda }_1,\dots ,{\lambda }_m$ coordinates of the projection (with respect to basis $X$) where ${\pi }_U(\mathbf{x})=\mathbf{B}\mathbf{\lambda }$ given $\mathbf{X}=\left[{\mathbf{x}}_1,\dots ,{\mathbf{x}}_m\right]\in {\mathbb{R}}^{n\times m}$ and $\mathbf{\lambda }={\left[{\lambda }_1,\dots ,{\lambda }_m\right]}^T\in {\mathbb{R}}^m$. The solution is the familiar OLS coef vector

$\mathbf{\lambda }=({\mathbf{X}}^{\prime }\mathbf{X}{)}^{-1}{\mathbf{X}}^{\prime }\mathbf{y}$

where ${\left({\mathbf{X}}^{\prime }\mathbf{X}\right)}^{-1}{\mathbf{X}}^{\prime }$ is also called the pseudo-inverse of $\mathbf{B}$, which can be computed as long as ${\left({\mathbf{X}}^{\prime }\mathbf{X}\right)}^{-1}$ is full rank.

The projection matrix is therefore

${\mathbf{P}}_{\pi }=\mathbf{X}{\left({\mathbf{X}}^{\prime }\mathbf{X}\right)}^{-1}{\mathbf{X}}^{\prime }$

Definition. Any basis $({\mathbf{b}}_1,\dots ,{\mathbf{b}}_n)$ of an $n-$ dimensional vector space $V$ can be transformed into an orthogonal/orthonormal basis $({\mathbf{u}}_1,\dots ,{\mathbf{u}}_n)$ where $\mathrm{span}[{\mathbf{b}}_1,\dots ,{\mathbf{b}}_n]=\mathrm{span}[{\mathbf{u}}_1,\dots ,{\mathbf{u}}_n]$ as follows

$${\mathbf{u}}_1:={\mathbf{b}}_1,{\mathbf{u}}_k:={\mathbf{b}}_k-{\pi }_{\mathrm{span}[{\mathbf{u}}_1,\dots ,{\mathbf{u}}_{k-1}]}({\mathbf{b}}_k),k=2,\dots ,n$$

where the $k$th basis vector ${\mathbf{b}}_k$ is projected onto the subspace spanned by the first $k-1$ constructed orthogonal vectors ${\mathbf{u}}_1,\dots ,{\mathbf{u}}_{k-1}$.

This is the same as FWL Theorem, but older.

Matrix Decompositions

Definition. A square matrix $\mathbf{A}$ admits to an eigen-decomposition if it can be factorised as $\mathbf{A}=\mathbf{Q}\mathbf{\Lambda }{\mathbf{Q}}^{-1}$ where

• $\mathbf{Q}$ is a $n\times n$ matrix whose $i$th column is the eigenvector ${\mathbf{q}}_i$ of $A$ (orthogonal matrix)

• $\mathbf{\Lambda }$ is a diagonal matrix with corresponding eigenvalues ${\Lambda }_{ii}={\lambda }_i$

Theorem. If $\mathbf{Q},\mathbf{N}$ are $N\times N$ orthogonal matrices

• ${\mathbf{Q}}^T={\mathbf{Q}}^{-1}$ is also orthogonal

• $\mathbf{QN}$ is orthogonal

• $det(\mathbf{Q})\in \{-1,1\}$

Definition. If $\mathbf{A}$ is positive definite, then it admits to

• $\mathbf{A}={\mathbf{R}}^T\mathbf{R}$ where $\mathbf{R}$ is non-singular upper triangular

• $\mathbf{A}=\mathbf{L}{\mathbf{L}}^T$ where $\mathbf{L}$ is non-singular lower triangular

Definition. If $\mathbf{A}$ is a $N\times K$ matrix with full column rank, $\exists$ a factorisation $\mathbf{A}=\mathbf{QR}$ where

• $\mathbf{Q}$ is an orthogonal matrix

• $\mathbf{R}$ is $K\times K$ upper triangular and nonsingular (invertible)

Result. $\hat{\mathbf{\beta }}={\left({\mathbf{X}}^{\prime }\mathbf{X}\right)}^{-1}{\mathbf{X}}^{\prime }\mathbf{y}$ is often numerically unstable, so we can define $\mathbf{X}=\mathbf{QR}$. The, the OLS estimate can be written as $\hat{\mathbf{\beta }}={\left(\mathbf{R}\right)}^{-1}{\mathbf{Q}}^{\prime }\mathbf{y}$. The homoscedastic variance is $\mathbb{V}\left[\hat{\mathbf{\beta }}\right]={\sigma }^2{\left({\mathbf{X}}^{\prime }\mathbf{X}\right)}^{-1}={\left({\mathbf{R}}^{\prime }\mathbf{R}\right)}^{-1}{\sigma }^2$.

Using the same decomposition, $\hat{\mathbf{y}}=\mathbf{X}\hat{\mathbf{\beta }}=\mathbf{Q}{\mathbf{Q}}^{\prime }\mathbf{y}$.

Definition. Any $n\times p$ matrix $\mathbf{Z}$ may be written as

$\mathbf{Z}=\mathbf{U\Sigma }{\mathbf{V}}^{\prime }$

where $\mathbf{U}$ is a $n\times n$ orthogonal matrix, $\mathbf{V}$ is a $p\times p$ orthogonal matrix, and $\mathbf{\Sigma }$ is a $n\times p$ diagonal matrix with non-negative elements.

Result. For a square covariance matrix ${\mathbf{X}}^{\prime }\mathbf{X}$, if $\mathbf{X}=\mathbf{US}{\mathbf{V}}^{\prime }$, then

$${\mathbf{X}}^{\prime }\mathbf{X}=\mathbf{V}{\mathbf{S}}^T{\mathbf{U}}^T\mathbf{US}{\mathbf{V}}^T=\mathbf{VD}{\mathbf{V}}^{\prime }$$

where $\mathbf{D}={\mathbf{S}}^2$ contains the square singular values. In other words,

$$\mathbf{U}=\text{evec}(\mathbf{X}{\mathbf{X}}^{\prime }),\mathbf{V}=\text{evec}({\mathbf{X}}^{\prime }\mathbf{X}),{\mathbf{S}}^2=\text{eval}({\mathbf{X}}^{\prime }\mathbf{X})=\text{eval}(\mathbf{X}{\mathbf{X}}^{\prime })$$

Matrix Identities

For conformable matrices $\mathbf{A},\mathbf{B},\mathbf{C}$,

$$\mathbf{A}(\mathbf{B}+\mathbf{C})=\mathbf{AB}+\mathbf{AC}$$ $$\mathbf{A}+{\mathbf{B}}^{\top }={\mathbf{A}}^{\top }+{\mathbf{B}}^{\top }$$ $$\mathbf{A}{\mathbf{B}}^{\top }={\mathbf{B}}^{\top }{\mathbf{A}}^{\top }$$ $${\left(\mathbf{AB}\right)}^{-1}={\left(\mathbf{B}\right)}^{-1}{\left(\mathbf{A}\right)}^{-1}$$ $$\mathrm{tr}(\mathbf{ABC})=\mathrm{tr}(\mathbf{CBA})=\mathrm{tr}(\mathbf{BCA})$$

Partitioned Matrices

Definition. It can be useful to partition a matrix as follows

$$X=\left[\begin{array}{cc}{X}_{11}& X_{12}\\ X_{21}& X_{22}\end{array}\right]$$

Multiplying a partitioned matrix with a stacked vector $\mathbf{c}$

$$\mathbf{Xc}=\left[\begin{array}{cc}{X}_{11}& X_{12}\\ X_{21}& X_{22}\end{array}\right]\left[\begin{array}{c}{c}_1\\ c_2\end{array}\right]=\left[\begin{array}{c}{X}_{11}{c}_1+X_{12}{c}_2\\ X_{21}{c}_1+X_{22}{c}_2\end{array}\right]$$

Theorem.

$${\left[\begin{array}{cc}{X}_{11}& X_{12}\\ X_{21}& X_{22}\end{array}\right]}^{-1}=\left[\begin{array}{cc}{X}_{11}^{-1}+X_{11}^{-1}{X}_{12}{F}_2{X}_{21}{\left(X_{11}\right)}^{-1}& -{\left(X_{11}\right)}^{-1}{X}_{12}{F}_2\\ -F_2{X}_{21}{\left(X_{11}\right)}^{-1}& F_2\end{array}\right]$$

where $F_2={\left(X_{22}-X_{21}{\left(X_{11}\right)}^{-1}{X}_{12}\right)}^{-1}$

Function Spaces

Almost all of this section is based on Larry Wasserman’s notes: functionspaces.pdf, and Racine (2013).

Definition. Let $U$ be any set, let $bU$ be the collection of all bounded functions s.t. $f:U\to \mathbb{R}$ (i.e. ${\sup }_{x\in U}\left|f(x)\right|<\infty$ and let

$$d_{\infty }(f,g):={\Vert f-g\Vert }_{\infty }:=\underset{x\in U}{\sup }\left|f(x)-g(x)\right|$$

Spaces of functions can be treated as linear vector spaces

Definition. $⟨f,g⟩=\int f(x)g(x)dx$

which leads to a norm for functions

${\Vert f\Vert }_2^2=\int f^2(x)dx$

Definition. An operator $\mathcal{O}$ is a higher-order function that maps from one function to another. A derivative and integral are both operators.

Operators can have eigenvalues and eigenfunctions such that

$\mathcal{O}f=\lambda f$

$\exp ax$ is an eigenfunction for both differentiation and integration.

Definition. is a complete ($:=$ every Cauchy sequence in the space converges to a point in it), inner product space. Equivalently, it is a vector space endowed with an inner product and an associated norm and metric such that every Cauchy sequence has a limit in $\mathcal{H}$.

Intuitively, it means it doesn’t have any ‘holes’ in it ($\mathbb{Q}$ is not a complete space because $\sqrt{2}$ is missing from it).

Every Hilbert space is a Banach space but the reverse is not true in general. In a hilbert space, $\Vert f_n-f\Vert \to 0\text{ as }n\to \infty$.

If $V$ is a hilbert space and $L$ is a closed subspace then $\forall v,\exists y\in L$ called a projection of $v$ onto $L$ that minimises $\Vert v-z\Vert$ over $z\in L$. The set of elements orthogonal every $z\in L$ is denoted $L^{\perp }$. Every $v\in L$ can be written as $v=w+z$ where $z$ is the projection of $v$ onto $L$ and $w\in L^{\perp }$.

Result. , the set of random variables defined on a common probability space $\left\{\Sigma ,\mathcal{F},\mu \right\}$ is a Hilbert space with inner product $⟨X,Y⟩=\mathbb{E}\left[XY\right]$, associated norm $\Vert X\Vert =\sqrt{\mathbb{E}\left[X^2\right]}$ and metric $\Vert X-Y\Vert$.

Result. the space of Borel-measurable real functions $f$ on $\mathbb{R}$ given density $w(x)$ satisfying ${\int }_{-\infty }^{\infty }f(x{)}^{2}w(x)\mathsf{d}x<\infty$ and associated norm $\Vert f\Vert =\sqrt{⟨f,f⟩}$ and metric $\Vert f-g\Vert$ is a hilbert space.

Definition. If $L$ and $M$ are spaces such that every $\ell \in L$ is orthogonal to every $m\in M$, then we define the orthogonal sum as

$L\oplus M=\left\{l+m:l\in L,m\in M\right\}$

A set of vectors $\left\{e_t,t\in T\right\}$ is orthonormal if $⟨e_s,e_t⟩=0$ when $s\ne t$ and $\Vert e_t\Vert =1\forall T$. This is also called an orthonormal basis. Every hilbert space has an orthonormal basis. A Hilbert space is said to be separable if there exists a countable orthonormal basis.

$L_p$ spaces

Let $\mathcal{F}$ be a collection of functions $[a,b]\mapsto \mathbb{R}$. The $L_p$ norm on $\mathcal{F}$ is defined by

${\Vert f\Vert }_p={\left({\int }_a^b{\left|f(x)\right|}^{p}dx\right)}^{1/p}$

For $p=\infty$, we define the sup norm ${\Vert f\Vert }_{\infty }={\sup }_x\left|f(x)\right|$.

The space $L_p(a,b)$ is defined as

$L_p(a,b):=\left\{f:[a,b]\to \mathbb{R}:{\Vert f\Vert }_p<\infty \right\}$

Every $L_p$ space is a Banach Space.

• Cauchy Schwartz: ${\left(\int f(x)g(x)dx\right)}^2\le \int f^2(x)dx\int g^2(x)dx$

• Minkowski : ${\Vert f+g\Vert }_p\le {\Vert f\Vert }_p+{\Vert g\Vert }_p$ where $p>1$

• Holder: ${\Vert fg\Vert }_1\le {\Vert f\Vert }_p{\Vert g\Vert }_q$ where $(1/p)+(1/q)=1$

Result. Functions where ${\Vert f\Vert }_2^2<\infty$ are said to be square-integrable, and the space of square-integrable functions is called $L_2$. Many familiar results from vector spaces carries over into $L_2$.

$L_2(a,b)$ is a Hilbertspace. The inner product between two functions $f,g\in L_2(a,b)$ is ${\int }_a^{b}f(x)g(x)dx$ and the norm of $f$ is ${\Vert f\Vert }^2={\int }_a^b{f}^2(x)dx$. With this inner product, $L_2(a,b)$ is a separable Hilbert space; that is, we can find a countable orthonormal basis ${\varphi }_1,{\varphi }_2,\dots ;$ , that is $\Vert {\varphi }_j\Vert =1\forall j$, and ${\int }_a^b{\varphi }_i(x){\varphi }_j(x)=0\forall i\ne j$. It follows that if $f\in L_2(a,b)$,

$f(x)={\sum }_{j=1}^{\infty }{\theta }_j{\varphi }_j(x)\text{ where }{\theta }_j={\int }_a^{b}f(x){\varphi }_j(x)dx$

are the coefficients. Parseval’s identity ${\int }_a^b{f}^2(x)dx={\sum }_{j=1}^{\infty }{\theta }_j^2$.

The span of $L_2$ is

$$\left\{\sum _{j=1}^{\infty }{a}_j{\varphi }_j(x):(a_j{)}_{j\ge 1}\in {\mathbb{R}}^{\infty }\right\}$$

The projection of $f={\sum }_{j=1}^{\infty }{\theta }_j{\varphi }_j(x)$ onto the span $\left\{{\varphi }_1,\dots ,{\varphi }_n\right\}$ is $f_n={\sum }_{j=1}^n{\theta }_j{\varphi }_j(x)$, which we call the n-term linear approximation of $f$.

Definition. A sequence of functions ${\psi }_1,\dots$ can be considered a basis. An orthonormal basis is one that admits to

$f={\sum }_{j=1}^{\infty }⟨f,{\psi }_j⟩{\psi }_j$

Mononomials $1,x,x^2,\dots$ are a basis for $L_2$ on $[0,1]$ and $\mathbb{R}$, but they aren’t orthogonal.

Result. A popular basis for $L_2$ on $[0,1]$ are the sines and cosines, which may be written as ${\varphi }_1=1$, ${\varphi }_{2k}=\sin 2k\pi x$ , ${\varphi }_{2k+1}=\cos 2k\pi x$. Coefficients in this expansion are referred to as the Fourier transform of the original function.

A cosine basis on $[0,1]$ is

$${\varphi }_0(x)=1,{\varphi }_j(x)=\sqrt{2}\cos (2\pi jx),j=1,2,\dots$$

Legendre basis on $(-1,1)$ is

$$P_0(x)=1,P_1(x)=x,P_2(x)=\frac{1}{2}(3x^2-1),P_3(x)=\frac{1}{2}(5x^3-3x),\dots$$

The Haar basis on [0,1] consists of functions $\left\{\varphi (x),{\psi }_{jk}(x):j=0,1,\dots ,k=0,1,\dots ,2^j-1\right\}$ where $\varphi (x)=\{\begin{array}{ll}1& \text{ if }0\le x<1\\ 0& \text{ otherwise }\end{array}$ ${\psi }_{jk}(x)=2^{j/2}\psi \left(2^{j}x-k\right)$ and $\psi (x)=\{\begin{array}{rl}-1& \text{ if }0\le x\le \frac{1}{2}\\ 1& \text{ if }\frac{1}{2}<x\le 1\end{array}$

This is a doubly indexed set of functions so when $f$ is expanded in this basis we write $f(x)=\alpha \varphi (x)+{\sum }_{j=1}^{\infty }{\sum }_{k=1}^{2^j-1}{\beta }_{jk}{\psi }_{jk}(x)$ where $\alpha ={\int }_0^{1}f(x)\varphi (x)dx$ and ${\beta }_{jk}={\int }_0^{1}f(x){\psi }_{jk}(x)dx.$ The Haar basis is an example of a wavelet basis.

Definition. Let $\beta$ be a positive integer. Let $T\subset \mathbb{R}.$ The Holder space $H(\beta ,L)$ is the set of functions $g:T\to \mathbb{R}$ such that

$$\left|g^{(\beta -1)}(y)-g^{(\beta -1)}(x)\right|\le L|x-y|,\text{for all }x,y\in T$$

The special case $\beta =1$ is sometimes called the Lipschitz space. If $\beta =2$ then we have

$$\left|g^{\prime }(x)-g^{\prime }(y)\right|\le L|x-y|,\text{for all }x,y\in T$$

Roughly speaking, this means that the functions have bounded second derivatives.

Multivariate version

There is also a multivariate version of Holder spaces. Let $T\subset {\mathbb{R}}^d$. Given a vector $s=$ $\left(s_1,\dots ,s_d\right),$ define $|s|=s_1+\cdots +s_d,s!=s_1!\cdots s_d!,x^s=x_1^{s_1}\cdots x_d^{s_d}$ and

$$D^s=\frac{{\partial }^{s_1+\cdots +s_d}}{\partial x_1^{s_1}\cdots \partial x_d^{s_d}}$$

The Hölder class $H(\beta ,L)$ is the set of functions $g:T\to \mathbb{R}$ such that

$$\left|D^{s}g(x)-D^{s}g(y)\right|\le L\Vert x-y{\Vert }^{\beta -|s|}$$

for all $x,y$ and all $s$ such that $|s|=\beta -1$.

Definition. A Sobolev space is a space of functions possessing sufficiently many derivatives for some application domain. Formally,

Let $f$ be integrable on every bounded interval. Then $f$ is weakly differentiable if there exists a function $f^{\prime }$ that is integrable on every bounded interval, such that ${\int }_x^y{f}^{\prime }(s)ds=f(y)-f(x)$ whenever $x\le y.$ We call $f^{\prime }$ the weak derivative of $f.$ Let $D^{j}f$ denote the $j^{\text{th }}$ weak derivative of $f$

The Sobolev space of order $m$ is defined by $W_{m,p}=\left\{f\in L_p(0,1):\Vert D^{m}f\Vert \in L_p(0,1)\right\}$ The Sobolev ball of order $m$ and radius $c$ is defined by $W_{m,p}(c)=\left\{f:f\in W_{m,p},{\Vert D^{m}f\Vert }_p\le c\right\}$

Definition. A Mercer kernel is a continuous function $K:[a,b]\times [a,b]\to \mathbb{R}$ such that $K(x,y)=K(y,x),$ and such that $K$ is positive semidefinite, meaning that

$$\sum _{i=1}^n\sum _{j=1}^{n}K\left(x_i,x_j\right)c_i{c}_j\ge 0$$

for all finite sets of points $x_1,\dots ,x_n\in [a,b]$ and all real numbers $c_1,\dots ,c_n.$ The function

$K(x,y)={\sum }_{k=1}^{m-1}\frac{1}{k!}{x}^k{y}^k+{\int }_0^{x\wedge y}\frac{(x-u{)}^{m-1}(y-u{)}^{m-1}}{(m-1){!}^2}du$

is an example of a Mercer kernel. The most commonly used kernel is the Gaussian kernel

$K(x,y)=e^{-\frac{\Vert x-y{\Vert }^2}{{\sigma }^2}}$

Definition.

Given a kernel $K,$ let $K_x(\cdot )$ be the function obtained by fixing the first coordinate. That is, $K_x(y)=K(x,y).$ For the Gaussian kernel, $K_x$ is a Normal, centered at $x.$ We can create functions by taking liner combinations of the kernel:

$f(x)={\sum }_{j=1}^k{\alpha }_j{K}_{x_j}(x)$ Let ${\mathcal{H}}_0$ denote all such functions: ${\mathcal{H}}_0=\left\{f:{\sum }_{j=1}^k{\alpha }_j{K}_{x_j}(x)\right\}$ Given two such functions $f(x)={\sum }_{j=1}^k{\alpha }_j{K}_{x_j}(x)$ and $g(x)={\sum }_{j=1}^m{\beta }_j{K}_{y_j}(x)$ we define an inner product $⟨f,g⟩=⟨f,g{⟩}_K={\sum }_i{\sum }_j{\alpha }_i{\beta }_{j}K\left(x_i,y_j\right)$ In general, $f($ and $g)$ might be representable in more than one way. You can check that $⟨f,g{⟩}_K$ is independent of how $f($ or $g)$ is represented. The inner product defines a norm: $\Vert f{\Vert }_K=\sqrt{⟨f,f,⟩}=\sqrt{{\sum }_j{\sum }_k{\alpha }_j{\alpha }_{k}K\left(x_j,x_k\right)}=\sqrt{{\alpha }^T\mathbb{K}\alpha }$ where $\alpha ={\left({\alpha }_1,\dots ,{\alpha }_k\right)}^T$ and $\mathbb{K}$ is the $k\times k$ matrix with ${\mathbb{K}}_{jk}=K\left(x_j,x_k\right)$

The Reproducing Property

.

Let $f(x)={\sum }_i{\alpha }_i{K}_{x_i}(x).$ Note the following crucial property: $⟨f,K_x⟩={\sum }_i{\alpha }_{i}K\left(x_i,x\right)=f(x)$ This follows from the definition of $⟨f,g⟩$ where we take $g=K_x.$ This implies that $⟨K_x,K_x⟩=K(x,x)$ This is called the reproducing property. It also implies that $K_x$ is the representer of the evaluation functional.

The completion of ${\mathcal{H}}_0$ with respect to $\Vert \cdot {\Vert }_K$ is denoted by ${\mathcal{H}}_K$ and is called the RKHS generated by $K$.

Evaluation Functionals. A key property of RKHS’s is the behavior of the evaluation functional. The evaluation functional ${\delta }_x$ assigns a real number to each function. It is defined by ${\delta }_{x}f=f(x).$ In general, the evaluation functional is not continuous. This means we can have $f_n\to f$ but ${\delta }_x{f}_n$ does not converge to ${\delta }_{x}f.$ For example, let $f(x)=0$ and $f_n(x)=\sqrt{n}I\left(x<1/n^2\right).$ Then $\Vert f_n-f\Vert =1/\sqrt{n}\to 0.$ But ${\delta }_0{f}_n=\sqrt{n}$ which does not converge to ${\delta }_{0}f=0.$ Intuitively, this is because Hilbert spaces can contain very unsmooth functions.

But in an $\mathrm{RKHS}$, the evaluation functional is continuous. Intuitively, this means that the functions in the space are well-behaved. To see this, suppose that $f_n\to f.$ Then

$${\delta }_x{f}_n=⟨f_n,K_x⟩\to ⟨f,K_x⟩=f(x)={\delta }_{x}f$$

so the evaluation functional is continuous.

A Hilbert space is a RKHS if and only if the evaluation functionals are continuous.

Theorem. Let $\ell$ be a loss function depending on $\left(X_1,Y_1\right),\dots ,\left(X_n,Y_n\right)$ and on $f\left(X_1\right),\dots ,f\left(X_n\right).$ Let $\hat{f}$ minimize $\ell +g\left(\Vert f{\Vert }_K^2\right)$ where $g$ is any monotone increasing function. Then $\hat{f}$ has the form $\hat{f}(x)={\sum }_{i=1}^n{\alpha }_{i}K\left(x_i,x\right)$ for some ${\alpha }_1,\dots ,{\alpha }_n$

Calculus and Optimisation

Calculus

Definition. The derivative of a function $f$ at point $x$, when defined, is the tangent to the function at $x$.

$\frac{\partial f}{\partial x}={\lim }_{h\to 0}\frac{f(x+h)-f(x)}{h}$

Definition. For function $f:{\mathbb{R}}^m\to \mathbb{R}$, we define the

$${\nabla }_{\mathbf{x}}f=\left[\begin{array}{c}\frac{\partial f}{\partial x_1}\\ \frac{\partial f}{\partial x_2}\\ ⋮\\ \frac{\partial f}{\partial x_n}\end{array}\right]$$

which collects the partial derivatives in a column vector.

The matrix of partial derivatives of $f$ is called the Hessian, denoted by ${\nabla }^2(\mathbf{x})$

$${\nabla }^2(\mathbf{x})=\left[\begin{array}{ccc}\frac{\partial }{\partial x_1}\frac{\partial f}{\partial x_1}& \cdots & \frac{\partial }{\partial x_n}\frac{\partial f}{\partial x_1}\\ ⋮& \ddots & ⋮\\ \frac{\partial }{\partial x_1}\frac{\partial f}{\partial x_n}& \cdots & \frac{\partial }{\partial x_n}\frac{\partial f}{\partial x_n}\end{array}\right]$$

For a vector-valued function $\mathbf{f}:{\mathbb{R}}^n\to {\mathbb{R}}^m$, we can construct the Jacobian, which collects all $m\times n$ partial derivatives.

$$\frac{\partial \mathbf{f}}{\partial \mathbf{x}}=\left[\begin{array}{c}\nabla f_1(\mathbf{x})\\ \nabla f_2(\mathbf{x})\\ ⋮\\ \nabla f_m(\mathbf{x})\end{array}\right]=\left[\begin{array}{cccc}\frac{\partial f_1(\mathbf{x})}{\partial x_1}& \frac{\partial f_1(\mathbf{x})}{\partial x_2}& \dots & \frac{\partial f_1(\mathbf{x})}{\partial x_n}\\ \frac{\partial f_2(\mathbf{x})}{\partial x_1}& \frac{\partial f_2(\mathbf{x})}{\partial x_2}& \dots & \frac{\partial f_2(\mathbf{x})}{\partial x_n}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial f_m(\mathbf{x})}{\partial x_1}& \frac{\partial f_m(\mathbf{x})}{\partial x_2}& \dots & \frac{\partial f_m(\mathbf{x})}{\partial x_n}\end{array}\right]$$

Theorem. $f:\mathbb{R}\to \mathbb{R}$ admits to Taylor expansion around $a$ such that

$$f(x)=f(a)+\frac{f^{\prime }(a)}{1!}(x-a)+\frac{f^{\prime \prime }(a)}{2!}(x-a{)}^2+\cdots =\sum _{n=0}^{\infty }\frac{f^{(n)}(a)}{n!}(x-a{)}^n$$

For a function with multiple arguments $f:{\mathbb{R}}^k\to \mathbb{R}$, the second-order Taylor expansion around the point ${\mathbf{x}}_0$ is

$$f(\mathbf{x})\approx f({\mathbf{x}}_0)+(\mathbf{x}-{\mathbf{x}}_0)\cdot \nabla f({\mathbf{x}}_0)+\frac{1}{2}(\mathbf{x}-{\mathbf{x}}_0){\nabla }^2(\mathbf{x})(\mathbf{x}-{\mathbf{x}}_0)$$

Theorem. Let $f(\mathbf{x})$ have continuous first and second order partial derivatives in the $\epsilon -$ neighbourhood of the optimum ${\mathbf{x}}_0$.

If $\nabla f({\mathbf{x}}_0)=0$ and ${\nabla }^2({\mathbf{x}}_0)$ is positive definite, then ${\mathbf{x}}_0$ is a local minimum. If $\nabla f({\mathbf{x}}_0)=0$ and ${\nabla }^2({\mathbf{x}}_0)$ is negative definite, then ${\mathbf{x}}_0$ is a local maximum.

Theorem. Let ${\lambda }_1,\dots ,{\lambda }_m$ be nonnegative real numbers, and suppose ${\mathbf{x}}_0$ maximises the Lagrangian $M(\mathbf{x},\mathbf{\lambda })$

$M(\mathbf{x},\mathbf{\lambda })=f(\mathbf{x})-{\sum }_{j=1}^m{\lambda }_j{g}_j(\mathbf{x})$

Then, ${\mathbf{x}}_0$ maximises $f(\mathbf{x})$ subject to constraints ($x\in \mathcal{S}$)

$g_j(\mathbf{x})\le g_j({\mathbf{x}}_0),j=1,\dots m$

Theorem. If $\phi :U\to {\mathbb{R}}^d$ is differentiable at $a$ and $D_{{\phi }_a}$ is invertible, then $\exists U^{\prime },V^{\prime }$ such that $a\in U^{\prime }\subseteq U,\phi (a)\in V^{\prime }\wedge \phi :U^{\prime }\to V^{\prime }$ is bijective. Further, the inverse function $\psi :V^{\prime }\to U^{\prime }$ is differentiable.

Theorem. Let $U\subseteq {\mathbb{R}}^{d+1}$ be a domain and $f:U\to \mathbb{R}$ be a differentiable function. If $x\in {\mathbb{R}}^d\wedge y\in \mathbb{R}$, we’ll concatenate the two vectors and write $(x,y)\in {\mathbb{R}}^{d+1}$.

Suppose $c=f(a,b)$, and ${\partial }_{y}f(a,b)\ne 0$. Then, $\exists U^{\prime }\ni a\wedge$ differentiable function $g:U^{\prime }\to \mathbb{R}\text{ s.t. }g(a)=b\wedge f(x,g(x))=c\forall x\in U^{\prime }$.

Further, $\exists V^{\prime }\ni b\text{ s.t. }\left\{(x,y)|x\in U^{\prime },y\in V^{\prime },f(x,y)=c\right\}=\left\{(g,g(x))|x\in U^{\prime }\right\}$. IoW, $\forall x\in U^{\prime },f(x,y)=c$ has a unique solution $y=g(x)\in V^{\prime }$.

Theorem. Let $f:{\mathbb{R}}^2\to \mathbb{R}$ be differentiable and consider the implicitly defined curve

$$\Gamma :=\left\{(x,y)\in {\mathbb{R}}^2\mid f(x,y)=c\right\}$$

(i.e. a level set of $f$). Pick $(a,b)\in \Gamma$, suppose ${\partial }_{y}f(a,b)\ne 0$. By IFT, we know the $y$-coordinate of this curve can locally be expressed as a differentiable function of $x$. Directly differentiating $f(x,y)=c\text{ w.r.t. }x$ gives

$${\partial }_{x}f+{\partial }_{y}f\frac{dy}{dx}=0⟺\frac{dy}{dx}=-\frac{{\partial }_{x}f(a,b)}{{\partial }_{y}f(a,b)}$$

Differentiation Rules

Rule	$f(x)$	$f^{\prime }(x)$
Power rule	$x^a$	$a{x}^{a-1}$
Exponential rule	$e^x$	$e^x$
Log rule	$\log x$	$\frac{1}{x}$
Linear rule	$(af+bg)$	$a\frac{\partial f}{\partial x}+b\frac{\partial g}{\partial x}$
Product rule	$(f\cdot g)$	$f^{\prime }(x)g(x)+f(x)g^{\prime }(x)$
Quotient rule	$\frac{f}{g}$	$\frac{f^{\prime }(x)g(x)-f(x)g^{\prime }(x)}{(g(x){)}^2}$
Chain rule	$f(g(x))$	$\frac{\partial f}{\partial g}\frac{\partial g}{\partial x}$

Matrix Derivatives

Let $\mathbf{a},\mathbf{x}\in {\mathbb{R}}^n$, and $\mathbf{A}$ be a conformable matrix

• $\frac{\partial {\mathbf{a}}^{\prime }\mathbf{x}}{\partial \mathbf{x}}=\mathbf{a}$

• $\frac{\partial {\mathbf{a}}^{\prime }\mathbf{x}}{\partial {\mathbf{x}}^{\prime }}={\mathbf{a}}^{\prime }$

---

• $\frac{\partial }{\partial {\mathbf{x}}^{\prime }}\mathbf{A}\mathbf{x}=\mathbf{A}$

• $\frac{\partial }{\partial \mathbf{x}}\mathbf{A}\mathbf{x}={\mathbf{A}}^{\prime }$

• $\frac{\partial }{\partial \mathbf{x}}{\mathbf{x}}^{\prime }\mathbf{A}\mathbf{x}=(\mathbf{A}+{\mathbf{A}}^{\prime })\mathbf{x}$

• $\frac{\partial }{\partial \mathbf{A}}{\mathbf{x}}^{\prime }\mathbf{A}\mathbf{x}=\mathbf{x}{\mathbf{x}}^{\prime }$

• $\frac{\partial }{\partial \mathbf{A}}\log \left|\mathbf{A}\right|={\left({\mathbf{A}}^{\prime }\right)}^{-1}$

General Results from Optimisation Theory

References: Luenberger (1997), Rustagi (2014).

• Projection Theorem - In ${\mathbb{R}}^k$, the shortest line from a point to the plane is furnished by the perpendicular from the point to the plane. Core idea carries through to higher dimensions and infinite-dimensional Hilbert Space

• Hahn-Banach Theorem: given a sphere and a point not in the sphere, there exists a hyperplane separating the point and the sphere.

• Duality: The shortest distance from a point to a convex set is equal to the maximum of the distances from the point to a hyperplane separating the point from the convex set.

• Differentials: Set derivative of the objective function to zero.

Linear Programming

Maximise

$$\underset{\mathbf{x}}{\max }Z={\mathbf{c}}^{\top }\mathbf{x}$$

subject to

$$\begin{array}{rl}\mathbf{Ax}& \le \mathbf{b}\\ \mathbf{x}& \ge 0\end{array}$$

where $\mathbf{x}\in {\mathbb{R}}^n$ is the choice vector, $\mathbf{c}\in {\mathbb{R}}^n$ is a given vector, $\mathbf{A}\in {\mathbb{R}}^{m\times n}$ is a known matrix of constants, and $\mathbf{b}\in {\mathbb{R}}^m$ is a vector of constants.

Definition. By introducing $m$ slack variables $y_1,\dots ,y_m$, $\mathbf{y}=(y_1,\dots ,y_m{)}^{\top }$ for every inequality with $\mathbf{y}\ge 0$, we can convert every linear programming into its standard form

$$\begin{array}{rl}\underset{\mathbf{x}}{\min }Z& =({\mathbf{c}}^{\top }{\mathbf{x}}^{\top }+0^{\top }\mathbf{y})\text{subject to}\\ \mathbf{Ax}+\mathbf{Iy}& =\mathbf{b}\\ \mathbf{x}& \ge 0,\mathbf{y}\ge 0\end{array}$$

Definition. Primal

$$\begin{array}{rl}\underset{x}{\min }& {\mathbf{c}}^{\top }\mathbf{x}\text{ s.t. }\\ \mathbf{Ax}& \ge b\\ \mathbf{x}& \ge 0\end{array}$$

Dual

$$\begin{array}{rl}\underset{y}{\max }& {\mathbf{b}}^{\top }\mathbf{y}\text{ s.t. }\\ {\mathbf{A}}^{\top }\mathbf{y}& \le c\\ \mathbf{y}& \ge 0,\mathbf{y}\in {\mathbb{R}}^{n+m}\end{array}$$

Theorem. A feasible solution ${\mathbf{x}}_0$ to the primal is optimal IFF there exists a feasible solution ${\mathbf{y}}_0$ to the dual problem such that

${\mathbf{c}}^{\top }{\mathbf{x}}_0={\mathbf{b}}^{\top }{\mathbf{y}}_0$

Dantzig’s Simplex method, Karmarkar’s Algorithm.

Nonlinear Optimisation

$$\begin{array}{rl}\text{minimise}[\text{maximise}]& f(\mathbf{x})\text{ s.t. }\\ g_i(\mathbf{x})& \le a_{i}i=1,\dots ,k\\ \mathbf{x}& \ge 0\end{array}$$

Saddle Point

Suppose we have $\mathbf{x},\mathbf{y}\in {\mathbb{R}}^n$ and $\varphi (\cdot )$ is a real valued function. Then, $({\mathbf{x}}_0,{\mathbf{y}}_0),{\mathbf{x}}_0\ge 0,{\mathbf{y}}_0\ge 0$ is a saddle-point of $\varphi (\mathbf{x},\mathbf{y})$ if

$\varphi ({\mathbf{x}}_0,\mathbf{y})\le \varphi ({\mathbf{x}}_0,{\mathbf{y}}_0)\le \varphi (\mathbf{x},{\mathbf{y}}_0)$

$\forall \mathbf{x},\mathbf{y}\ge 0$.

$$\begin{array}{rl}\varphi ({\mathbf{x}}_0,{\mathbf{y}}_0)& =\underset{\mathbf{x}}{\min }\underset{\mathbf{y}}{\max }\varphi (\mathbf{x},\mathbf{y})\\ \varphi ({\mathbf{x}}_0,{\mathbf{y}}_0)& =\underset{\mathbf{y}}{\max }\underset{\mathbf{x}}{\min }\varphi (\mathbf{x},\mathbf{y})\end{array}$$

Definition.

$$\begin{array}{rl}Q& ={\mathbf{a}}^{\top }\mathbf{x}-\frac{1}{2}{\mathbf{x}}^{\top }\mathbf{Bx}\text{ s.t. }\\ {\mathbf{C}}^{\top }\mathbf{x}& \le \mathbf{d}\\ \mathbf{x}& \ge 0\end{array}$$

where $\mathbf{a}\in {\mathbb{R}}^n$, $\mathbf{B}\in {\mathbb{R}}^{n\times n}$ is symmetric, positive definite, $\mathbf{C}\in {\mathbb{R}}^{n\times k}$ is a matrix of constraints, and $\mathbf{d}\in {\mathbb{R}}^k$.

Constrained Maximisation

Theorem. We want to maximise $f(x)\text{ s.t. }g(x)=c$ (implicitly defined by $S:=\left\{g=c\right\}$). Suppose $\nabla g\ne 0\forall x\in S$. If $f$ attains a constrained local maximum (or minimum) at $a$ on the surface $S$, $\exists \lambda \in \mathbb{R}\text{ s.t. }\nabla f(a)=\lambda \nabla g(a)$.

Generic problem of the form

Definition. ${\max }_{x_1,x_2\in {\mathbb{R}}^n}f(x_1,x_2)\text{ s.t. }g(x_1,x_2)=b$

First, write $\mathcal{L}(x_1,x_2,\lambda )=f(x_1,x_2)+\lambda \left[g(x_1,x_2)-b\right]$

differentiating wrt $x_1,x_2,\lambda$ yields FOCs

$$\begin{array}{rl}[x_1]& :\frac{\partial \mathcal{L}}{\partial x_1}=f_1(x_1,x_2)+\lambda g_1(x_1,x_2)=0\\ [x_2]& :\frac{\partial \mathcal{L}}{\partial x_2}=f_2(x_1,x_2)+\lambda g_2(x_1,x_2)=0\\ [\lambda ]& :\frac{\partial \mathcal{L}}{\partial \lambda }=g(x_1,x_2)-b=0\end{array}$$

which gives us three (potentially nonlinear) equations with three unknowns $(x_1,x_2,\lambda )$, that can be solved simultaneously.

To check sufficiency, the second-order condition analogue is the determinant of the bordered hessian matrix

$$\text{BH}(x_1,x_2,\lambda )=\left[\begin{array}{ccc}0& -g_1(x_1,x_2)& -g_2(x_1,x_2)\\ -g_1(x_1,x_2)& f_{11}(x_1,x_2)& f_{12}(x_1,x_2)\\ -g_2(x_1,x_2)& f_{21}(x_1,x_2)& f_{22}(x_1,x_2)\end{array}\right]$$

If $\det \text{BH}>0$, then it is negative definite, which implies that the $(x_1^{\ast },x_2^{\ast })$ that solves the system is indeed a local maximum.

Definition. The Hessian for of a $C^2$ [twice differentiable] function $f:{\mathbb{R}}^{n}d\to \mathbb{R}$ is defined by the matrix

$$\text{H}f=\left[\begin{array}{cccc}{\partial }_1{\partial }_{1}f& {\partial }_2{\partial }_{1}f& \dots & {\partial }_d{\partial }_{1}f\\ {\partial }_1{\partial }_{2}f& {\partial }_2{\partial }_{2}f& \dots & {\partial }_d{\partial }_{2}f\\ ⋮& ⋮& \dots & ⋮\\ {\partial }_1{\partial }_{d}f& {\partial }_2{\partial }_{d}f& \dots & {\partial }_d{\partial }_{d}f\end{array}\right]$$

• If $(\mathbf{A}\mathbf{v})\cdot \mathbf{v}\le 0\forall v\in {\mathbb{R}}^d$, $\mathbf{A}$ is said to be negative semi-definite.

• If $(\mathbf{A}\mathbf{v})\cdot \mathbf{v}<0\forall v\in {\mathbb{R}}^d$, $\mathbf{A}$ is said to be negative definite.

• If $(\mathbf{A}\mathbf{v})\cdot \mathbf{v}\ge 0\forall v\in {\mathbb{R}}^d$, $\mathbf{A}$ is said to be positive semi-definite.

• If $(\mathbf{A}\mathbf{v})\cdot \mathbf{v}>0\forall v\in {\mathbb{R}}^d$, $\mathbf{A}$ is said to be positive definite.

Numerical Optimisation

Root-finding

We want to evaluate the roots of the equation

$y=f(x)=0,x\in \mathbb{R}$

Assume the inverse of $f$, denoted $f^{-1}$ exists.

$x=f^{-1}(y)=g(y)$

Finding the root of $f(x)=0$ is equivalent to evaluating $g(0)=x$.

Canonical newton-raphson is

$x_{i+1}=x_i-\frac{f\left(x_i\right)}{f^{\prime }\left(x_i\right)}$

Quasi-Newton

General version of update rule:

$${\mathbf{\theta }}_{k+1}={\mathbf{\theta }}_k-{\lambda }_k\cdot {\mathbf{A}}_k\frac{\partial \ell }{\partial \mathbf{\theta }}({\mathbf{\theta }}_k)$$

Step length $\lambda =1$ for both N-R and BHHH.

Definition. set ${\mathbf{A}}_k={\left({\nabla }^2(\theta )\right)}^{-1}$

Update rule:

$$x_{i+1}=x_i-\frac{f^{\prime }(x_i)}{f^{\prime \prime }(x_i)}$$

For Log-likelihood,

$${\mathbf{\theta }}_{k+1}={\mathbf{\theta }}_k-{\left(\frac{{\partial }^2\ell }{\partial \mathbf{\theta }\partial {\mathbf{\theta }}^{\prime }}({\mathbf{\theta }}_k)\right)}^{-1}\frac{\partial \ell }{\partial \mathbf{\theta }}({\mathbf{\theta }}_k)\equiv {\mathbf{\theta }}_k-{\left(\mathsf{H}({\mathbf{\theta }}_k)\right)}^{-1}\mathsf{s}({\mathbf{\theta }}_k)$$

Definition. Uses Information-matrix equality. Set $A_k=\frac{1}{N}(\mathcal{S}({\theta }_k)\mathcal{S}({\theta }_k{)}^{\prime })$ to be outer product of scores

$$A_k:={\left(\frac{1}{N}\sum _{i=1}^N\frac{\partial \ell }{\partial \theta }({\theta }_k)\frac{\partial \ell }{\partial {\theta }^{\prime }}({\theta }_k)\right)}^{-1}$$