Linear Algebra Review with Fitting and Reconstruction, linear algebra I lesson

Three measured points refuse to lie on one straight line. In a second experiment, three hidden inputs can change while two measured totals stay exactly the same. Both problems have the form $A\mathbf{x} = \mathbf{b}$ , yet the first has no exact solution and the second has infinitely many, so they call for different methods and different defenses. This review classifies such problems by rank and compatibility, solves each one under a stated criterion, checks the answer in the original problem, and asks what the result does and does not say about the hidden truth.

Key terms

Overdetermined system

Definition A linear system $A\mathbf{x} = \mathbf{b}$ with a real $m \times n$ matrix $A$ is overdetermined when it has more equations than unknowns, $m > n$ . The count alone decides neither existence nor uniqueness. The system has an exact solution exactly when $\mathbf{b}$ lies in $\operatorname{Col} A$ , a subspace of dimension at most $n < m$ , which data with measurement errors usually miss. When there is no exact solution, ordinary least squares minimizes $\lVert \mathbf{b} - A\mathbf{x} \rVert$ over all $\mathbf{x}$ in $\mathbb{R}^n$ . The minimizers always exist, and they are exactly the solutions of the normal equations

A^{\top}A\hat{\mathbf{x}} = A^{\top}\mathbf{b}.

The minimizer is unique exactly when the columns of $A$ are independent, that is when $\operatorname{rank} A = n$ . A QR factorization or an SVD solves the same problem without forming $A^{\top}A$ , and that is the safer route in floating-point arithmetic. When $\operatorname{rank} A = n$ , the invertible matrix $A^{\top}A$ has condition number $\sigma_1^2/\sigma_n^2$ , where $\sigma_1$ and $\sigma_n$ are the largest and smallest singular values of $A$ , so forming it squares the ratio $\sigma_1/\sigma_n$ of $A$ itself.

In plain words More equations than unknowns means more demands than adjustable numbers. When the demands conflict, a fit stops trying to meet each one exactly and makes the vector of misses as short as possible instead.

Example Tuples such as $(1, 2, 4)$ stand for column vectors on this page, except for data points written $(t_i, y_i)$ . Fit the line $y = a + bt$ to the points $(0, 1)$ , $(1, 2)$ and $(2, 4)$ . The unknowns are $\mathbf{c} = (a, b)$ , and the system $X\mathbf{c} = \mathbf{y}$ has

X = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix} 1 \\ 2 \\ 4 \end{bmatrix}.

The first two points force $a = 1$ and $b = 1$ , and that line predicts $3$ at $t = 2$ , not $4$ , so no exact fit exists. The normal equations are

\begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} 7 \\ 10 \end{bmatrix}.

Subtracting the first equation from the second gives $2b = 3$ , so $b = \tfrac{3}{2}$ , and then $3a = 7 - \tfrac{9}{2} = \tfrac{5}{2}$ gives $a = \tfrac{5}{6}$ . The columns of $X$ are independent, since $\alpha(1, 1, 1) + \beta(0, 1, 2) = \mathbf{0}$ forces $\alpha = 0$ from the first entry and then $\beta = 0$ , so this least-squares line is the only one.

Underdetermined system

Definition A linear system $A\mathbf{x} = \mathbf{b}$ with a real $m \times n$ matrix $A$ is underdetermined when it has fewer equations than unknowns, $m < n$ . Then

\begin{aligned} \dim \operatorname{Null} A &= n - \operatorname{rank} A \\[0.4em] &\ge n - m > 0, \end{aligned}

so the null space contains nonzero vectors. The system can still have no solution, when $\mathbf{b}$ is not in $\operatorname{Col} A$ . If it has a solution $\mathbf{x}_p$ , it has infinitely many, and they are exactly the vectors $\mathbf{x}_p + \mathbf{z}$ with $\mathbf{z}$ in $\operatorname{Null} A$ . Every one of them reproduces $\mathbf{b}$ exactly, so the data alone cannot tell them apart.

In plain words Fewer measurements than unknowns leave some input directions unseen. Moving the input along such a direction changes nothing that was measured.

Example Two totals of three inputs are measured, $x_1 + x_3 = 4$ and $x_2 + x_3 = 3$ , so

A = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}, \qquad \mathbf{b} = \begin{bmatrix} 4 \\ 3 \end{bmatrix}.

With $x_3 = t$ free, every solution is

\mathbf{x} = \begin{bmatrix} 4 - t \\ 3 - t \\ t \end{bmatrix} = \begin{bmatrix} 4 \\ 3 \\ 0 \end{bmatrix} + t\begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix},

and $\operatorname{Null} A$ is the line spanned by $(-1, -1, 1)$ . The rank is $2$ , so every $\mathbf{b}$ in $\mathbb{R}^2$ is reachable. There is nothing to fit here, only a choice to make.

Residual check

Definition The residual of a candidate $\hat{\mathbf{x}}$ for $A\mathbf{x} = \mathbf{b}$ is $\mathbf{r} = \mathbf{b} - A\hat{\mathbf{x}}$ , computed from the original data and in the units of the measurements. A residual check recomputes $\mathbf{r}$ and tests the property the method promises. An exact solution needs $\mathbf{r} = \mathbf{0}$ . A least-squares solution needs

A^{\top}\mathbf{r} = \mathbf{0},

one dot product with each column of $A$ , which is the normal equations in another form. This test certifies the minimum, because when it holds, every $\mathbf{x}$ in $\mathbb{R}^n$ satisfies

\lVert \mathbf{b} - A\mathbf{x} \rVert^2 = \lVert \mathbf{r} \rVert^2 + \lVert A(\hat{\mathbf{x}} - \mathbf{x}) \rVert^2.

The check ends with the null space. In both cases the solutions are exactly the vectors $\hat{\mathbf{x}} + \mathbf{z}$ with $\mathbf{z}$ in $\operatorname{Null} A$ , so the answer is unique exactly when $\operatorname{Null} A = \{\mathbf{0}\}$ .

In plain words Put the answer back into the problem that was asked. For a fit, the misses must be perpendicular to every change in prediction the model can make, otherwise some change would shrink them.

Example For the line with $a = \tfrac{5}{6}$ and $b = \tfrac{3}{2}$ , the predictions are $(\tfrac{5}{6}, \tfrac{7}{3}, \tfrac{23}{6})$ and

\mathbf{r} = \mathbf{y} - X\mathbf{c} = \begin{bmatrix} 1/6 \\ -1/3 \\ 1/6 \end{bmatrix}.

Its entries add to $\tfrac{1}{6} - \tfrac{1}{3} + \tfrac{1}{6} = 0$ , and weighted by the inputs they give $0 \cdot \tfrac{1}{6} + 1 \cdot (-\tfrac{1}{3}) + 2 \cdot \tfrac{1}{6} = 0$ , so $X^{\top}\mathbf{r} = \mathbf{0}$ . The squared error is $\tfrac{1}{36} + \tfrac{1}{9} + \tfrac{1}{36} = \tfrac{1}{6}$ . This perpendicularity holds in the three-dimensional space of observations. In the scatter plot the residuals are vertical gaps at fixed inputs, and they need not meet the line at right angles.

Minimum-norm reconstruction

Definition Let $A\mathbf{x} = \mathbf{b}$ be consistent, with $A$ a real $m \times n$ matrix. Among all its solutions exactly one has the smallest Euclidean norm. It is called the minimum-norm reconstruction and written $\mathbf{x}^{+}$ . It is the only solution that lies in $\operatorname{Row} A$ , which means it is orthogonal to every vector of $\operatorname{Null} A$ , and it equals $A^{+}\mathbf{b}$ , where $A^{+}$ is the pseudoinverse. Every other solution is $\mathbf{x}^{+} + \mathbf{z}$ with a nonzero $\mathbf{z}$ in $\operatorname{Null} A$ , and

\lVert \mathbf{x}^{+} + \mathbf{z} \rVert^2 = \lVert \mathbf{x}^{+} \rVert^2 + \lVert \mathbf{z} \rVert^2.

When $A$ has full row rank, $\operatorname{rank} A = m$ , the pseudoinverse is $A^{+} = A^{\top}(AA^{\top})^{-1}$ . For inconsistent data, $A^{+}\mathbf{b}$ is the least-squares solution of smallest norm. Length is measured in the given coordinates, so a change of units for the inputs can change which solution is shortest.

In plain words When the data leave a whole family of exact answers, pick the shortest one. It has no component in the unseen directions, so it adds nothing the measurements did not ask for. It is a stated choice, not a discovery of the hidden input.

Example For the two totals above,

\begin{aligned} AA^{\top} &= \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, \\[0.4em] A^{+} &= \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \\ 1 & 1 \end{bmatrix}, \end{aligned}

so $\mathbf{x}^{+} = A^{+}(4, 3) = (\tfrac{5}{3}, \tfrac{2}{3}, \tfrac{7}{3})$ , the member of the family with $t = \tfrac{7}{3}$ . Both measurements hold, since $\tfrac{5}{3} + \tfrac{7}{3} = 4$ and $\tfrac{2}{3} + \tfrac{7}{3} = 3$ , and the kernel test gives $-\tfrac{5}{3} - \tfrac{2}{3} + \tfrac{7}{3} = 0$ . The squared norm is $\tfrac{26}{3}$ , and adding $\alpha(-1, -1, 1)$ changes it to $\tfrac{26}{3} + 3\alpha^2$ , which is larger whenever $\alpha \ne 0$ . The data say nothing about the kernel component, so the hidden input could just as well be $(4, 3, 0)$ or $(2, 1, 2)$ .

Effect of an added measurement

Definition Suppose $A\mathbf{x} = \mathbf{b}$ is consistent and a new exact measurement $\mathbf{a}^{\top}\mathbf{x} = \beta$ arrives, with $\mathbf{a}$ a nonzero vector in $\mathbb{R}^n$ . The new system appends the row $\mathbf{a}^{\top}$ to $A$ and the entry $\beta$ to $\mathbf{b}$ , and its solutions are the old solutions that also satisfy the new equation. If $\mathbf{a}$ is not in $\operatorname{Row} A$ , then $\mathbf{a}$ is not orthogonal to $\operatorname{Null} A$ , the rank rises by one, the nullity drops by one, and the new system is still consistent. If $\mathbf{a}$ is in $\operatorname{Row} A$ , say $\mathbf{a} = A^{\top}\mathbf{w}$ , then every old solution has $\mathbf{a}^{\top}\mathbf{x} = \mathbf{w}^{\top}A\mathbf{x} = \mathbf{w}^{\top}\mathbf{b}$ . The measurement is then redundant when $\beta = \mathbf{w}^{\top}\mathbf{b}$ , and when $\beta \ne \mathbf{w}^{\top}\mathbf{b}$ it contradicts the old data and the combined system has no exact solution. Any answer chosen for the old problem, the minimum-norm one included, must be checked against the new equation and recomputed if it fails. If the new measurement is uncertain rather than exact, imposing it as an equation is itself a modeling choice, and a fit with stated weights is one alternative.

In plain words A new exact measurement can only remove possibilities. It removes freedom only when it looks along a direction the old measurements could not see. A measurement that repeats old information either agrees with it or exposes a conflict.

Example Add the exact measurement $x_3 = 2$ to the two totals. Its vector $\mathbf{a} = (0, 0, 1)$ has dot product $1$ with the kernel direction $(-1, -1, 1)$ , so it sees the missing direction. In the family it sets $t = 2$ , and the only solution left is $(2, 1, 2)$ . The new matrix

\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}

is upper triangular with ones on the diagonal, hence invertible. The old answer $(\tfrac{5}{3}, \tfrac{2}{3}, \tfrac{7}{3})$ has $x_3 = \tfrac{7}{3}$ , so it is not even a solution of the new problem. By contrast, a measurement $x_1 - x_2 = 1$ would add nothing, because its row is row 1 minus row 2 of $A$ and $4 - 3 = 1$ , while a reading $x_1 - x_2 = 2$ would contradict the two totals.

Agreement with data versus a validated model

Definition A model agrees with the data when its residual on the observations used to build it is zero or small under the stated error criterion. A model is validated only when further evidence supports it. Its predictions match observations that were not used to fit it, within their measurement uncertainty and over the range where the model will be used, and its assumptions are justified, such as which inputs are fixed, which measurements are exact, the weights and the units. Agreement is one part of evaluating a model and is never sufficient on its own. If the design matrix is square and invertible, as when a polynomial of degree $m - 1$ is fitted to $m$ points with distinct inputs, the residual is zero for any data. Every member of an underdetermined solution family reproduces the data exactly. A small residual can also come with a large error in the solution when $A$ shrinks some input direction strongly.

In plain words A good fit to the points you have is evidence about those points. Whether the model describes the process behind them is a separate question, answered by new data and by checking assumptions, not by a smaller residual.

Example The quadratic $y = 1 + \tfrac{1}{2}t + \tfrac{1}{2}t^2$ passes exactly through $(0, 1)$ , $(1, 2)$ and $(2, 4)$ , so its residual is $\mathbf{0}$ , while the least-squares line has squared error $\tfrac{1}{6}$ . That alone does not make the quadratic the better model, since three coefficients can match any three readings at distinct inputs. At $t = 3$ the quadratic predicts $7$ and the line predicts $\tfrac{5}{6} + \tfrac{9}{2} = \tfrac{16}{3}$ . Only new measurements, such as one at $t = 3$ , or knowledge of the process that produced the data, can decide between them.

Check yourself

Count equations and unknowns in each system, then decide whether it has no solution, exactly one or infinitely many. The first system is $x + y = 2$ , $2x + 2y = 4$ , $x - y = 0$ , and the second is $x + y + z = 1$ , $2x + 2y + 2z = 3$ .

Show the answer

The first system has three equations in two unknowns, so it is overdetermined, yet it has exactly one solution. The second equation is twice the first, and the first and third give $x = y = 1$ , which satisfies all three. The coefficient rows $(1, 1)$ and $(1, -1)$ are independent, so the rank is $2$ and the solution is unique. The second system has two equations in three unknowns, so it is underdetermined, yet it has no solution, because twice the first equation reads $2x + 2y + 2z = 2$ , not $3$ . Counting alone decides neither question. The rank and the right-hand side decide both.

Fit $y = a + bt$ by least squares to the points $(0, 3)$ , $(1, 1)$ and $(2, 2)$ . Check the residual and say whether the coefficients are unique. Someone proposes the line $y = 3 - t$ instead, because it passes through the first point and its residuals add to zero. Does it pass the residual check?

Show the answer

The inputs are the same as in the examples, so $X^{\top}X$ is unchanged, and $X^{\top}\mathbf{y} = (3 + 1 + 2, 0 + 1 + 4) = (6, 5)$ . The normal equations are

\begin{aligned} 3a + 3b &= 6, \\[0.4em] 3a + 5b &= 5. \end{aligned}

Subtracting gives $2b = -1$ , so $b = -\tfrac{1}{2}$ and $a = \tfrac{5}{2}$ . The predictions are $(\tfrac{5}{2}, 2, \tfrac{3}{2})$ and the residual is $\mathbf{r} = (\tfrac{1}{2}, -1, \tfrac{1}{2})$ . Its entries add to $0$ and its input-weighted sum is $0 - 1 + 1 = 0$ , so $X^{\top}\mathbf{r} = \mathbf{0}$ . The squared error is $\tfrac{1}{4} + 1 + \tfrac{1}{4} = \tfrac{3}{2}$ , and the coefficients are unique because the columns of $X$ are independent. For $y = 3 - t$ the predictions are $(3, 2, 1)$ and the residual is $(0, -1, 1)$ . Its entries do add to $0$ , but its input-weighted sum is $-1 + 2 = 1 \ne 0$ , so it fails the check, and its squared error $2$ is larger than $\tfrac{3}{2}$ . A zero sum tests only the first column of $X$ , and the least-squares residual must be orthogonal to every column.

Three survey markers have unknown heights $x_1, x_2, x_3$ , and only differences are measured, $x_1 - x_2 = 1$ and $x_2 - x_3 = 1$ . Find all solutions and the minimum-norm one, and verify it. Then decide what each of the extra exact measurements $x_1 + x_2 + x_3 = 3$ and $x_1 - x_3 = 2$ would do.

Show the answer

With $x_3 = t$ , the measurements give $x_2 = 1 + t$ and $x_1 = 2 + t$ , so

\mathbf{x} = \begin{bmatrix} 2 \\ 1 \\ 0 \end{bmatrix} + t\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix},

and the null space is spanned by $(1, 1, 1)$ . Orthogonality to it requires $(2 + t) + (1 + t) + t = 3 + 3t = 0$ , so $t = -1$ and $\mathbf{x}^{+} = (1, 0, -1)$ . Check the measurements, $1 - 0 = 1$ and $0 - (-1) = 1$ , and the kernel, $1 + 0 - 1 = 0$ . The squared norm is $2$ , and adding $\alpha(1, 1, 1)$ gives $2 + 3\alpha^2$ , so this solution is the unique shortest one. It sets the average height to zero, which is a convention. Differences cannot reveal the overall level, and true heights such as $(102, 101, 100)$ give the same data.

The measurement $x_1 + x_2 + x_3 = 3$ has vector $(1, 1, 1)$ , exactly the unseen direction. In the family it gives $3 + 3t = 3$ , so $t = 0$ and the heights are uniquely $(2, 1, 0)$ . The old answer has height sum $0$ and fails the new measurement, so it must be replaced. The measurement $x_1 - x_3 = 2$ has vector $(1, 0, -1)$ , which is row 1 plus row 2, and $1 + 1 = 2$ . Every old solution already satisfies it, so nothing changes. A reading $x_1 - x_3 = 3$ would instead contradict the first two measurements.

Linear Algebra Review with Fitting and Reconstruction

Key terms

Overdetermined system

Underdetermined system

Residual check

Minimum-norm reconstruction

Effect of an added measurement

Agreement with data versus a validated model

Check yourself

How this lesson connects

Builds on