Projection and Least Squares Workshop

Definition The error criterion of a problem is the quantity its answer must make zero or as small as possible, and it is fixed before any calculation. Three questions are common. An exact solve asks for $\mathbf{x}$ with $A\mathbf{x} = \mathbf{b}$, and a solution exists exactly when $\mathbf{b}$ lies in $\operatorname{Col} A$. A projection asks for the point $\mathbf{p}$ of a given subspace $W$ of $\mathbb{R}^m$ that minimizes the Euclidean distance $\lVert \mathbf{b} - \mathbf{p} \rVert$. A least-squares fit first chooses a model, given by a design matrix $X$ whose columns span the possible predictions, and then minimizes the sum of squared residuals $\lVert \mathbf{y} - X\mathbf{c} \rVert^2$ over coefficient vectors $\mathbf{c}$. At a minimizer $\hat{\mathbf{c}}$ the fitted vector $X\hat{\mathbf{c}}$ is the projection of $\mathbf{y}$ onto $\operatorname{Col} X$. A weighted criterion with positive weights $w_1, \dots, w_m$ minimizes

which is ordinary least squares after row $i$ of $X$ and the entry $y_i$ are multiplied by $\sqrt{w_i}$.

Definition Let $\mathbf{n}$ be a nonzero vector in $\mathbb{R}^3$, and let $W = \{\mathbf{x} : \mathbf{n} \cdot \mathbf{x} = 0\}$ be the plane through the origin with normal $\mathbf{n}$. For $\mathbf{b}$ in $\mathbb{R}^3$, the part of $\mathbf{b}$ along $\mathbf{n}$ is the residual, and the projection $\mathbf{p}$ onto $W$ is what remains,

The point $\mathbf{p}$ lies in $W$, the residual $\mathbf{r}$ is perpendicular to $W$, and for every $\mathbf{q}$ in $W$

so $\mathbf{p}$ is the unique closest point of $W$ to $\mathbf{b}$, at distance $\lVert \mathbf{r} \rVert = \lvert \mathbf{b} \cdot \mathbf{n} \rvert / \lVert \mathbf{n} \rVert$. The same formulas hold for a hyperplane $\mathbf{n} \cdot \mathbf{x} = 0$ in $\mathbb{R}^m$. A plane $\mathbf{n} \cdot \mathbf{x} = d$ with $d \ne 0$ misses the origin and is not a subspace, and for it $\mathbf{b} \cdot \mathbf{n}$ is replaced by $\mathbf{b} \cdot \mathbf{n} - d$.

Definition Given data points $(t_1, y_1), \dots, (t_m, y_m)$, a least-squares line $y = a + bt$ is one that minimizes the sum of squared vertical residuals

where $\mathbf{y} = (y_1, \dots, y_m)$, $\mathbf{c} = (a, b)$, and the design matrix $X$ is the $m \times 2$ matrix whose row $i$ is $\begin{bmatrix} 1 & t_i \end{bmatrix}$. The minimizers are exactly the solutions of the normal equations

When at least two of the inputs $t_i$ differ, the columns of $X$ are independent, $X^{\top}X$ is invertible, and the line is unique.

Definition Suppose one column of a design matrix $X$ is a multiple of another, $\mathbf{x}_2 = k\mathbf{x}_1$ for some scalar $k$. Then $X$ does not have full column rank, $X^{\top}X$ is singular, and the normal equations have infinitely many solutions. The fitted vector is still unique, because it is the projection of $\mathbf{y}$ onto $\operatorname{Col} X$, but the coefficients are not. Two least-squares coefficient vectors differ by a vector of $\operatorname{Null} X$, such as $(k, -1)$ when $X$ has these two columns only. In general the coefficients are unique exactly when $X$ has full column rank.

Definition Let $A$ be an invertible $n \times n$ matrix, viewed as a measurement map, with data $\mathbf{b}$ and solution $\mathbf{x}$ of $A\mathbf{x} = \mathbf{b}$. A change $\delta\mathbf{b}$ in the measurements changes the solution by $\delta\mathbf{x} = A^{-1}\delta\mathbf{b}$, so

and when $\mathbf{b} \ne \mathbf{0}$ the relative change in $\mathbf{x}$ is at most the condition number $\kappa_2(A) = \lVert A \rVert_2 \lVert A^{-1} \rVert_2$ times the relative change in $\mathbf{b}$. The ratio $\lVert \delta\mathbf{x} \rVert / \lVert \delta\mathbf{b} \rVert$ reaches its largest value $\lVert A^{-1} \rVert_2$ when $\delta\mathbf{b}$ is a nonzero multiple of $A\mathbf{v}$, where $\mathbf{v}$ is a unit input direction that $A$ stretches least. If the data are uncertain by about $\lVert A\mathbf{v} \rVert$ along the direction of $A\mathbf{v}$, the solution is uncertain by about one unit along $\mathbf{v}$, however many digits are printed.

Definition A projection or a fit is checked in the original problem. The answer must lie in the model space, so a projection $\mathbf{p}$ must lie in $W$ and a fitted vector must have the form $X\mathbf{c}$. The residual must be orthogonal to the model space in observation space, which for a fit means $X^{\top}\mathbf{r} = \mathbf{0}$, one dot product for each design column. Membership and orthogonality are needed together. For the plane $W$ with normal $\mathbf{n}$, every point of $W$ passes the first test, and every point $\mathbf{b} - t\mathbf{n}$ on the normal line through $\mathbf{b}$ passes the second, but only $\mathbf{p}$ passes both. The units must agree, with residuals in the units of the observations and each coefficient in the units that make its term match them. Finally, the rank of $X$ decides whether the coefficients are unique, and the sensitivity of the problem decides whether the data constrain them reliably.