Vector Geometry, Rank, and Projection

Definition On $\mathbb{R}^n$ this page uses the ordinary dot product $\mathbf{u}^{\top}\mathbf{v} = \sum_i u_i v_i$. The Euclidean norm of a vector $\mathbf{v}$ is

and the Euclidean distance between $\mathbf{u}$ and $\mathbf{v}$ is $\lVert \mathbf{u} - \mathbf{v} \rVert_2$. The norm is zero only for the zero vector. Two vectors are orthogonal when $\mathbf{u}^{\top}\mathbf{v} = 0$. For nonzero vectors this means they meet at a right angle, and the zero vector is orthogonal to every vector. Orthogonal vectors satisfy the Pythagorean identity

Definition The span of vectors $\mathbf{a}_1, \dots, \mathbf{a}_k$ in $\mathbb{R}^n$ is the set of all their linear combinations $c_1\mathbf{a}_1 + \dots + c_k\mathbf{a}_k$ with real numbers $c_j$. The column space of an $n \times p$ matrix $X$ is the span of its columns,

It is a subspace of $\mathbb{R}^n$, so it contains $\mathbf{0}$ and is closed under addition and scalar multiplication. The span of one nonzero vector is a line through the origin, and the span of the zero vector is $\{ \mathbf{0} \}$. For a linear model without an intercept, $\operatorname{Col} X$ is exactly the set of prediction vectors the model can produce. With an intercept, the same holds for the augmented matrix that includes the ones column.

Definition Let $S$ be a subspace of $\mathbb{R}^n$ and $\mathbf{y}$ a vector in $\mathbb{R}^n$. The orthogonal projection of $\mathbf{y}$ onto $S$ is the vector $\mathbf{p}$ in $S$ for which the residual $\mathbf{y} - \mathbf{p}$ is orthogonal to every vector in $S$. It exists and is unique, and it is the point of $S$ closest to $\mathbf{y}$. For any $\mathbf{z}$ in $S$ the difference $\mathbf{p} - \mathbf{z}$ also lies in $S$, so the Pythagorean identity gives

and the second term is zero only when $\mathbf{z} = \mathbf{p}$. When $S$ is the span of a nonzero vector $\mathbf{a}$, the condition $\mathbf{a}^{\top}(\mathbf{y} - c\,\mathbf{a}) = 0$ gives

The denominator is positive because $\mathbf{a} \ne \mathbf{0}$. On this page the residual is target minus prediction, $\mathbf{r} = \mathbf{y} - \mathbf{p}$.

Definition Vectors $\mathbf{a}_1, \dots, \mathbf{a}_k$ are linearly independent if $c_1\mathbf{a}_1 + \dots + c_k\mathbf{a}_k = \mathbf{0}$ holds only when every $c_j = 0$, and linearly dependent otherwise. So the columns of $X$ are independent exactly when $X\mathbf{w} = \mathbf{0}$ forces $\mathbf{w} = \mathbf{0}$. The rank of $X$ is the dimension of $\operatorname{Col} X$. It equals the largest number of linearly independent columns and also the largest number of linearly independent rows, so $\operatorname{rank} X \le \min(n, p)$. If $X\mathbf{w}_0 = \mathbf{p}$, the coefficient vectors that give the same prediction vector $\mathbf{p}$ are exactly the vectors $\mathbf{w}_0 + \mathbf{h}$ with $X\mathbf{h} = \mathbf{0}$. Hence every vector in $\operatorname{Col} X$ comes from exactly one coefficient vector when $\operatorname{rank} X = p$, and from infinitely many when $\operatorname{rank} X < p$.

Definition A square $m \times m$ matrix $A$ is singular if it has no inverse. Singularity is equivalent to $\det A = 0$, to $\operatorname{rank} A < m$, and to $A\mathbf{v} = \mathbf{0}$ for some nonzero $\mathbf{v}$. For an $n \times p$ matrix $X$, the $p \times p$ matrix $X^{\top}X$ is singular exactly when the columns of $X$ are dependent, because $X^{\top}X\mathbf{v} = \mathbf{0}$ implies $\lVert X\mathbf{v} \rVert_2^2 = \mathbf{v}^{\top}X^{\top}X\mathbf{v} = 0$. This matrix appears when the projection condition for $\operatorname{Col} X$ is written out. The residual must be orthogonal to every column, $X^{\top}(\mathbf{y} - X\mathbf{w}) = \mathbf{0}$, which gives the normal equations

They always have a solution, and every solution gives the projection, $X\mathbf{w} = \mathbf{p}$. The formula $\mathbf{w} = (X^{\top}X)^{-1}X^{\top}\mathbf{y}$ is valid only when $X^{\top}X$ is invertible, that is, when $\operatorname{rank} X = p$.

Definition Conditioning describes how much the answer to a problem can change when its inputs change slightly. For an invertible square matrix $A$, let $\sigma_{\max}$ and $\sigma_{\min}$ be the largest and smallest values of $\lVert A\mathbf{v} \rVert_2 / \lVert \mathbf{v} \rVert_2$ over nonzero vectors $\mathbf{v}$, the most and the least that $A$ stretches a vector. The condition number is $\kappa(A) = \sigma_{\max} / \sigma_{\min} \ge 1$. If $A\mathbf{w} = \mathbf{y}$ with $\mathbf{y} \ne \mathbf{0}$ and $A(\mathbf{w} + \Delta\mathbf{w}) = \mathbf{y} + \Delta\mathbf{y}$, then

A matrix with a large condition number is called ill-conditioned. It is invertible, yet its nearly dependent columns make the solution sensitive. A singular matrix is the limiting case, and its condition number is taken to be infinite. Conditioning belongs to the problem, including the units chosen for the features. Floating-point rounding errors are amplified by it, but they do not cause it.