Background

Compact preliminaries the main sections rely on. This is a reference card, not a course: each entry states facts and proves the short ones, so that no section ever has to interrupt its subject to re-teach them. Entries are added when a section first needs them.

The dot product

For $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^d$, the dot product (inner product) is

$$⟨\mathbf{u},\mathbf{v}⟩={\mathbf{u}}^{\top }\mathbf{v}=\sum _{j=1}^d{u}_j{v}_j,$$

and the Euclidean norm is $\Vert \mathbf{u}\Vert =\sqrt{⟨\mathbf{u},\mathbf{u}⟩}$.

Facts (each immediate from the definition):

1. Symmetry: $⟨\mathbf{u},\mathbf{v}⟩=⟨\mathbf{v},\mathbf{u}⟩$.
2. Linearity in each argument: $⟨a\mathbf{u}+\mathbf{w},\mathbf{v}⟩=a⟨\mathbf{u},\mathbf{v}⟩+⟨\mathbf{w},\mathbf{v}⟩$ for any scalar $a$.
3. Positivity: $⟨\mathbf{u},\mathbf{u}⟩={\Vert \mathbf{u}\Vert }^2\ge 0$, with equality iff $\mathbf{u}=0$.
4. Expansion of a sum (used constantly; it is the law of cosines in disguise):

$${\Vert \mathbf{u}+\mathbf{v}\Vert }^2={\Vert \mathbf{u}\Vert }^2+2⟨\mathbf{u},\mathbf{v}⟩+{\Vert \mathbf{v}\Vert }^2.$$

Proof of 4. Expand $⟨\mathbf{u}+\mathbf{v},\mathbf{u}+\mathbf{v}⟩$ using linearity in each argument and symmetry: $⟨\mathbf{u},\mathbf{u}⟩+⟨\mathbf{u},\mathbf{v}⟩+⟨\mathbf{v},\mathbf{u}⟩+⟨\mathbf{v},\mathbf{v}⟩={\Vert \mathbf{u}\Vert }^2+2⟨\mathbf{u},\mathbf{v}⟩+{\Vert \mathbf{v}\Vert }^2$. ∎

Geometrically, $⟨\mathbf{u},\mathbf{v}⟩=\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert \cos \theta$ where $\theta$ is the angle between the vectors — the dot product measures alignment. This reading is justified by the next entry, which shows the ratio $⟨\mathbf{u},\mathbf{v}⟩/(\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert )$ always lies in $[-1,1]$.

The Cauchy-Schwarz inequality

Theorem. For all $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^d$,

$$\left|⟨\mathbf{u},\mathbf{v}⟩\right|\le \Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert ,$$

with equality iff one vector is a scalar multiple of the other.

Proof. If $\mathbf{v}=0$ both sides are zero. Otherwise, for every $t\in \mathbb{R}$, positivity and the expansion identity give

$$0\le {\Vert \mathbf{u}-t\mathbf{v}\Vert }^2={\Vert \mathbf{u}\Vert }^2-2t⟨\mathbf{u},\mathbf{v}⟩+t^2{\Vert \mathbf{v}\Vert }^2.$$

The right-hand side is a quadratic in $t$ that is never negative, so its discriminant is at most zero:

$$4{⟨\mathbf{u},\mathbf{v}⟩}^2-4{\Vert \mathbf{u}\Vert }^2{\Vert \mathbf{v}\Vert }^2\le 0,$$

which is the claim after rearranging and taking square roots. Equality of the discriminant means the quadratic has a real root $t_0$, i.e. $\Vert \mathbf{u}-t_0\mathbf{v}\Vert =0$, i.e. $\mathbf{u}=t_0\mathbf{v}$. ∎

Used in: the perceptron convergence theorem (Step 3 — alignment cannot exceed length).

Calculus

Planned. Partial derivatives, the gradient, the chain rule, and first-order Taylor approximation — added when The logistic-loss gradient and Gradient descent land.

Probability

Planned. Random variables, expectation and variance, independence, the Bernoulli and Gaussian distributions, and Bayes' rule — added when The data-generating process and Maximum likelihood estimation land.

Convexity and Lagrange duality

Planned. Convex sets and functions, Lagrange multipliers, and the duality facts needed by Duality and the kernel SVM — added before that note is written.