Projections, Least Squares and Quadratic Forms

Projection onto a line

The closest point to $\mathbf b$ on the line through $\mathbf a$ is the orthogonal projection

$$\mathbf p = \frac{\mathbf a^\top\mathbf b}{\mathbf a^\top\mathbf a}\,\mathbf a = P\mathbf b, \qquad P = \frac{\mathbf a\mathbf a^\top}{\mathbf a^\top\mathbf a}.$$

The error $\mathbf e = \mathbf b - \mathbf p$ is perpendicular to $\mathbf a$. $P$ is a rank-1, symmetric, idempotent matrix.

Projection onto a subspace

For a subspace $W = C(A)$ where $A$ has independent columns:

$$\hat{\mathbf x} = (A^\top A)^{-1}A^\top\mathbf b, \qquad \mathbf p = A\hat{\mathbf x} = P\mathbf b, \qquad P = A(A^\top A)^{-1}A^\top.$$

If the columns are orthonormal ($A = Q$), this simplifies to $P = QQ^\top$ and $\mathbf p = \sum_i(\mathbf q_i^\top\mathbf b)\mathbf q_i$.

Properties of an orthogonal projection matrix $P$ onto $W$:

Least squares

When $A\mathbf x = \mathbf b$ has no solution (more equations than unknowns), choose $\hat{\mathbf x}$ to minimise $\lVert A\mathbf x - \mathbf b\rVert^2$. The minimiser makes the residual orthogonal to every column of $A$:

$$A^\top(\mathbf b - A\hat{\mathbf x}) = \mathbf 0 \quad\Longleftrightarrow\quad A^\top A\,\hat{\mathbf x} = A^\top\mathbf b \quad\text{(normal equations)}.$$

This is exactly linear regression: $\hat{\boldsymbol\beta} = (X^\top X)^{-1}X^\top\mathbf y$, fitted values $H\mathbf y$, residuals $(I - H)\mathbf y$.

Numerically, solving via QR ($R\hat{\mathbf x} = Q^\top\mathbf b$) or the SVD is more stable than forming $A^\top A$, which squares the condition number.

Quadratic forms

A quadratic form is $Q(\mathbf x) = \mathbf x^\top A\mathbf x = \sum_{i,j}a_{ij}x_ix_j$ with $A$ symmetric (any matrix can be replaced by its symmetric part without changing $Q$).

Reading off the matrix: the coefficient of $x_i^2$ goes on the diagonal; half the coefficient of $x_ix_j$ goes in each of positions $(i,j)$ and $(j,i)$.

$$2x_1^2 + 6x_1x_2 - x_2^2 + 4x_2x_3 \;\longleftrightarrow\; \begin{pmatrix}2&3&0\\3&-1&2\\0&2&0\end{pmatrix}.$$

Definiteness

Sylvester's criterion: $A$ is positive definite iff all leading principal minors are positive. For $2\times 2$: $a > 0$ and $ac - b^2 > 0$. Negative definite iff the leading minors alternate in sign starting negative.

Equivalent characterisations of positive definiteness: all eigenvalues positive; $A = R^\top R$ with $R$ invertible (Cholesky $A = LL^\top$ exists); all pivots positive. Covariance matrices, Gram matrices $X^\top X$ and kernel matrices are positive semi-definite.

Rayleigh quotient

For symmetric $A$ with eigenvalues $\lambda_{\min} \le \dots \le \lambda_{\max}$:

$$\lambda_{\min} \le \frac{\mathbf x^\top A\mathbf x}{\mathbf x^\top\mathbf x} \le \lambda_{\max},$$

with equality at the corresponding eigenvectors. This is why the first principal component (direction of maximum variance) is the top eigenvector of the covariance matrix.

Principal axes

With $A = Q\Lambda Q^\top$ and new coordinates $\mathbf y = Q^\top\mathbf x$, the cross terms disappear:

$$\mathbf x^\top A\mathbf x = \mathbf y^\top\Lambda\mathbf y = \lambda_1y_1^2 + \dots + \lambda_ny_n^2.$$

The level set $\mathbf x^\top A\mathbf x = 1$ of a positive definite form is an ellipsoid with axes along the eigenvectors and semi-axis lengths $1/\sqrt{\lambda_i}$.

Quick revision