The Central Idea
Suppose the system
\[ Ax=b \]is inconsistent.
Then there is no vector \(x\) for which \(Ax=b\) exactly.
Least squares instead chooses \(\hat{x}\) so that
\[ \boxed{\|A\hat{x}-b\|} \]is as small as possible.
The vector \(A\hat{x}\) is the orthogonal projection of \(b\) onto the column space of \(A\).
Why Inconsistent Systems Arise
In applications, systems are often built from measured data.
Measurements may contain:
- noise;
- rounding error;
- model mismatch;
- more observations than unknown parameters;
- small inconsistencies between equations.
Exact intersection is then uncommon, even when the underlying model is useful.
Overdetermined Systems
A system with more equations than unknowns is often called overdetermined.
For example,
\[ \begin{aligned} x+y&=2,\\ x-y&=0,\\ 2x+y&=4.2 \end{aligned} \]contains three equations in two unknowns.
Such a system may be inconsistent, but least squares still produces a best approximate solution.
The Column-Space View
Recall that
\[ Ax=b \]is consistent exactly when
\[ b\in\operatorname{Col}(A). \]If \(b\notin\operatorname{Col}(A)\), then least squares seeks the closest vector in the column space:
\[ \boxed{ A\hat{x} = \operatorname{proj}_{\operatorname{Col}(A)}(b)}. \]The Residual Vector
The difference between the observed target \(b\) and the fitted vector \(A\hat{x}\) is called the residual:
\[ \boxed{r=b-A\hat{x}}. \]Least squares chooses \(\hat{x}\) so that the residual has minimum norm.
The Residual Is Orthogonal to the Column Space
Because \(A\hat{x}\) is the orthogonal projection of \(b\) onto \(\operatorname{Col}(A)\),
\[ \boxed{ r=b-A\hat{x} \perp \operatorname{Col}(A)}. \]Therefore the residual is orthogonal to every column of \(A\).
From Orthogonality to the Normal Equations
If \(r\) is orthogonal to every column of \(A\), then
\[ A^Tr=0. \]Substitute
\[ r=b-A\hat{x}. \]Then
\[ A^T(b-A\hat{x})=0. \]Rearranging gives the normal equations:
\[ \boxed{ A^TA\hat{x}=A^Tb}. \]Why They Are Called Normal Equations
The word normal refers to perpendicularity.
The residual is normal, or perpendicular, to the column space of \(A\).
Thus the normal equations encode the geometric condition
\[ b-A\hat{x} \perp \operatorname{Col}(A). \]The Least-Squares Objective
A least-squares solution minimizes
\[ \boxed{ \|Ax-b\|^2}. \]Squaring the norm does not change which \(x\) minimizes the error because the square function is increasing for nonnegative inputs.
The squared form is algebraically convenient.
Why We Square the Errors
Squared errors have several useful properties:
- positive and negative errors cannot cancel;
- larger errors receive greater penalty;
- the objective is smooth and differentiable;
- the resulting algebra leads to linear normal equations.
Least Squares as Optimization
Define
\[ f(x)=\|Ax-b\|^2. \]Since
\[ f(x) = (Ax-b)^T(Ax-b), \]differentiation gives
\[ \nabla f(x) = 2A^T(Ax-b). \]Setting the gradient equal to zero produces
\[ \boxed{A^TAx=A^Tb}. \]Existence of a Least-Squares Solution
For every real matrix \(A\) and vector \(b\), at least one least-squares solution exists.
Geometrically, the projection of \(b\) onto the finite-dimensional subspace \(\operatorname{Col}(A)\) always exists.
Uniqueness of the Least-Squares Solution
The least-squares coefficient vector \(\hat{x}\) is unique when the columns of \(A\) are linearly independent.
In that case,
\[ A^TA \]is invertible.
Therefore,
\[ \boxed{ \hat{x} = (A^TA)^{-1}A^Tb}. \]Why \(A^TA\) Is Important
The matrix
\[ A^TA \]is always square and symmetric.
If the columns of \(A\) are linearly independent, then \(A^TA\) is also positive definite and invertible.
Dimensions in the Normal Equations
Suppose
\[ A\in\mathbb{R}^{m\times n}. \]Then
\[ A^T\in\mathbb{R}^{n\times m}, \]so
\[ A^TA\in\mathbb{R}^{n\times n} \]and
\[ A^Tb\in\mathbb{R}^n. \]The normal equations are therefore a square system in the \(n\) unknown coefficients.
Example: A Simple Least-Squares Problem
Let
\[ A= \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix}, \qquad b= \begin{bmatrix} 2\\ 3\\ 7 \end{bmatrix}. \]We seek the scalar \(x\) minimizing
\[ \left\| x \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} - \begin{bmatrix} 2\\ 3\\ 7 \end{bmatrix} \right\|. \]Solve the Simple Example
Compute
\[ A^TA= \begin{bmatrix} 1&1&1 \end{bmatrix} \begin{bmatrix} 1\\ 1\\ 1 \end{bmatrix} = 3. \]Also,
\[ A^Tb = 2+3+7 = 12. \]The normal equation is
\[ 3\hat{x}=12. \]Therefore,
\[ \boxed{\hat{x}=4}. \]Interpret the Result as an Average
The fitted vector is
\[ A\hat{x} = \begin{bmatrix} 4\\ 4\\ 4 \end{bmatrix}. \]Thus the best constant approximation to the data
\[ 2,\quad3,\quad7 \]is their mean:
\[ \boxed{4}. \]The ordinary arithmetic mean is therefore a least-squares estimate.
The Residual in the Example
The residual is
\[ r = b-A\hat{x} = \begin{bmatrix} 2\\ 3\\ 7 \end{bmatrix} - \begin{bmatrix} 4\\ 4\\ 4 \end{bmatrix} = \begin{bmatrix} -2\\ -1\\ 3 \end{bmatrix}. \]Check orthogonality:
\[ A^Tr = -2-1+3 = 0. \]The residual is orthogonal to the column space.
Projection Matrix for Full Column Rank
If the columns of \(A\) are linearly independent, then the orthogonal projection onto \(\operatorname{Col}(A)\) is
\[ \boxed{ P = A(A^TA)^{-1}A^T}. \]Therefore the fitted vector is
\[ \boxed{\hat{b}=Pb}. \]Projection Matrix Properties
The least-squares projection matrix satisfies
\[ \boxed{P^2=P} \]and
\[ \boxed{P^T=P}. \]Thus it is an orthogonal projection.
Fitted Vector and Residual
The fitted vector is
\[ \hat{b}=Pb. \]The residual is
\[ r=b-\hat{b}. \]Equivalently,
\[ \boxed{ r=(I-P)b}. \]The matrix \(I-P\) projects onto the orthogonal complement of the column space.
Least Squares and Orthonormal Columns
If the columns of \(Q\) are orthonormal, then
\[ Q^TQ=I. \]The normal equations become
\[ \hat{x}=Q^Tb. \]The projection is
\[ \boxed{QQ^Tb}. \]Orthonormal bases therefore simplify least-squares calculations substantially.
Least Squares Using QR Factorization
Suppose the full-column-rank matrix \(A\) has QR factorization
\[ A=QR, \]where \(Q\) has orthonormal columns and \(R\) is upper triangular.
The least-squares problem becomes
\[ \boxed{R\hat{x}=Q^Tb}. \]Why QR Is Often Preferred Numerically
Forming
\[ A^TA \]can amplify numerical conditioning problems.
QR factorization avoids explicitly squaring the conditioning of the matrix and is often more stable in numerical computation.
Thus the normal equations are conceptually important, while QR is often a better computational method.
Least-Squares Lines
Suppose data points
\[ (x_1,y_1),\ldots,(x_m,y_m) \]are to be approximated by a line
\[ y=\beta_0+\beta_1x. \]For each observation,
\[ y_i\approx\beta_0+\beta_1x_i. \]Design Matrix for a Line
Write
\[ A= \begin{bmatrix} 1&x_1\\ 1&x_2\\ \vdots&\vdots\\ 1&x_m \end{bmatrix}, \qquad \beta= \begin{bmatrix} \beta_0\\ \beta_1 \end{bmatrix}, \qquad y= \begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_m \end{bmatrix}. \]Then
\[ A\beta\approx y. \]Least squares chooses the coefficients minimizing
\[ \|A\beta-y\|^2. \]Regression as Projection
The predicted data vector
\[ \hat{y}=A\hat{\beta} \]lies in the column space of the design matrix.
Least-squares regression is therefore an orthogonal projection of the observed data vector onto the model subspace.
Example: Fit a Line to Three Points
Fit
\[ y=\beta_0+\beta_1x \]to
\[ (0,1),\qquad(1,2),\qquad(2,2). \]The design matrix and target vector are
\[ A= \begin{bmatrix} 1&0\\ 1&1\\ 1&2 \end{bmatrix}, \qquad y= \begin{bmatrix} 1\\ 2\\ 2 \end{bmatrix}. \]Build the Normal Equations for the Line
Compute
\[ A^TA = \begin{bmatrix} 3&3\\ 3&5 \end{bmatrix}. \]Also,
\[ A^Ty = \begin{bmatrix} 5\\ 6 \end{bmatrix}. \]Therefore,
\[ \begin{bmatrix} 3&3\\ 3&5 \end{bmatrix} \begin{bmatrix} \hat{\beta}_0\\ \hat{\beta}_1 \end{bmatrix} = \begin{bmatrix} 5\\ 6 \end{bmatrix}. \]Solve the Regression Example
The equations are
\[ 3\hat{\beta}_0+3\hat{\beta}_1=5, \] \[ 3\hat{\beta}_0+5\hat{\beta}_1=6. \]Subtracting gives
\[ 2\hat{\beta}_1=1, \]so
\[ \hat{\beta}_1=\frac12. \]Then
\[ \hat{\beta}_0=\frac76. \]The least-squares line is
\[ \boxed{ y=\frac76+\frac12x}. \]Residuals in Regression
For observation \(i\), the residual is
\[ r_i=y_i-\hat{y}_i. \]The least-squares line minimizes
\[ \boxed{ r_1^2+\cdots+r_m^2}. \]This quantity is often called the residual sum of squares.
Polynomial Least Squares
Least squares is not limited to straight lines.
To fit
\[ y=\beta_0+\beta_1x+\beta_2x^2, \]use the design matrix
\[ A= \begin{bmatrix} 1&x_1&x_1^2\\ 1&x_2&x_2^2\\ \vdots&\vdots&\vdots\\ 1&x_m&x_m^2 \end{bmatrix}. \]The same projection framework applies.
Basis Functions and General Linear Models
More generally, suppose
\[ f(x) = \beta_1\phi_1(x) +\cdots+ \beta_n\phi_n(x), \]where the functions \(\phi_j\) are fixed.
Even if the basis functions themselves are nonlinear in \(x\), the model is linear in the unknown coefficients \(\beta_j\).
Therefore least-squares linear algebra still applies.
Least Squares Is Linear in the Parameters
The phrase linear least squares refers to linearity in the unknown coefficients.
Models involving
\[ 1,\quad x,\quad x^2,\quad \sin x,\quad e^x \]can all produce linear least-squares problems if their coefficients enter linearly.
Multiple Predictors
A model such as
\[ y = \beta_0 + \beta_1x_1 + \beta_2x_2 \]is handled by adding columns to the design matrix.
Each column represents one model direction or predictor.
Least squares determines the coefficient combination whose predicted vector is closest to the observed data.
Weighted Least Squares
Sometimes observations should not receive equal importance.
Weighted least squares minimizes
\[ \boxed{ (Ax-b)^TW(Ax-b)} \]where \(W\) is a positive-definite weight matrix.
The corresponding normal equations are
\[ \boxed{ A^TWA\hat{x}=A^TWb}. \]Why Use Weights?
Weights can represent:
- different measurement reliabilities;
- different variances;
- different business priorities;
- different sampling frequencies;
- different physical units after suitable standardization.
Residual Orthogonality in Weighted Least Squares
In weighted least squares, the residual satisfies a weighted orthogonality condition:
\[ \boxed{ A^TW(b-A\hat{x})=0}. \]The geometry has changed because the inner product has changed.
Rank-Deficient Least Squares
If the columns of \(A\) are linearly dependent, then
\[ A^TA \]is singular.
The fitted vector \(A\hat{x}\) is still uniquely determined as the projection of \(b\) onto \(\operatorname{Col}(A)\), but the coefficient vector \(\hat{x}\) may not be unique.
Redundant Predictors
Column dependence means that one predictor direction can be generated from others.
In regression language, this is a form of exact multicollinearity.
The model may still make unique predictions even though multiple coefficient vectors produce those same predictions.
Minimum-Norm Least-Squares Solutions
When several least-squares coefficient vectors exist, an additional criterion can select the one with smallest norm:
\[ \boxed{ \min\|x\| \quad \text{subject to least-squares optimality}}. \]The Moore-Penrose pseudoinverse provides this solution.
The Pseudoinverse
The Moore-Penrose pseudoinverse is denoted
\[ \boxed{A^+}. \]A canonical least-squares solution is
\[ \boxed{\hat{x}=A^+b}. \]When \(A\) has full column rank,
\[ A^+ = (A^TA)^{-1}A^T. \]Least Squares and Singular Values
The pseudoinverse is naturally computed using the singular value decomposition.
Small singular values identify directions in which the least-squares problem may be sensitive to noise.
The later lesson on singular values and dimensional reduction will develop this structure in detail.
Conditioning and Sensitivity
A least-squares problem can be mathematically solvable yet numerically sensitive.
If columns of \(A\) are nearly dependent, small changes in the data may produce large changes in the fitted coefficients.
This is a conditioning issue rather than an inconsistency issue.
Exact Fit versus Best Fit
If
\[ b\in\operatorname{Col}(A), \]then the least-squares residual can be zero.
In that case, least squares recovers an exact solution of
\[ Ax=b. \]Least squares therefore includes exact linear systems as a special case.
Residual Norm
The quantity
\[ \boxed{\|r\|} \]measures the distance from \(b\) to the column space of \(A\).
Its square,
\[ \|r\|^2, \]is the minimum value of the least-squares objective.
Orthogonal Decomposition of the Data Vector
Least squares decomposes
\[ b \]into
\[ \boxed{ b = A\hat{x} + r}. \]Here
\[ A\hat{x}\in\operatorname{Col}(A) \]and
\[ r\in\operatorname{Col}(A)^\perp. \]This is an orthogonal decomposition.
Pythagorean Interpretation
For any other candidate \(Ax\in\operatorname{Col}(A)\),
\[ b-Ax = r + (A\hat{x}-Ax). \]The two components on the right are orthogonal.
Therefore,
\[ \boxed{ \|b-Ax\|^2 = \|r\|^2 + \|A\hat{x}-Ax\|^2}. \]This proves geometrically that \(A\hat{x}\) is the closest fitted vector.
Normal Equations and Column Orthogonality
Writing
\[ A= \begin{bmatrix} \vert&&\vert\\ a_1&\cdots&a_n\\ \vert&&\vert \end{bmatrix}, \]the normal equations imply
\[ a_j^Tr=0 \]for every column \(a_j\).
Each residual is orthogonal to every model direction.
Least Squares and the Left Null Space
Since
\[ A^Tr=0, \]the residual lies in
\[ \boxed{\operatorname{Null}(A^T)}. \]Because
\[ \operatorname{Null}(A^T) = \operatorname{Col}(A)^\perp, \]this is exactly the expected orthogonal-complement relationship.
Common Error: Solving \(A^TAx=b\)
The normal equations are
\[ \boxed{A^TA\hat{x}=A^Tb}, \]not
\[ A^TAx=b. \]Both sides must be multiplied by \(A^T\).
Common Error: Assuming the Residual Is Zero
In an inconsistent system, the residual is generally nonzero.
Least squares does not force
\[ A\hat{x}=b. \]It minimizes the distance between the two vectors.
Common Error: Assuming Least Squares Minimizes Absolute Error
Standard least squares minimizes
\[ \boxed{ \sum_i r_i^2}, \]not
\[ \sum_i|r_i|. \]Minimizing absolute deviations is a different optimization problem.
Common Error: Confusing Fitted Values with Coefficients
The vector
\[ \hat{x} \]contains model coefficients.
The vector
\[ A\hat{x} \]contains fitted or predicted values.
They live in different spaces when \(A\) is rectangular.
Common Error: Inverting \(A\) in an Overdetermined System
A tall matrix with more rows than columns is not square and therefore has no ordinary two-sided inverse.
Least squares instead uses projection methods, QR factorization, or the pseudoinverse.
Common Error: Assuming \(A^TA\) Is Always Invertible
The matrix
\[ A^TA \]is invertible exactly when the columns of \(A\) are linearly independent.
If the columns are dependent, other methods are needed to choose among multiple least-squares coefficient vectors.
Common Error: Using Normal Equations Without Considering Numerical Stability
The normal equations are mathematically valid, but they can be less stable than QR or SVD methods for ill-conditioned problems.
In computational work, method choice matters.
A Reliable Procedure for Least Squares with Normal Equations
- Write the model as \(Ax\approx b\).
- Compute \(A^TA\).
- Compute \(A^Tb\).
- Solve \(A^TA\hat{x}=A^Tb\).
- Compute the fitted vector \(A\hat{x}\).
- Compute the residual \(r=b-A\hat{x}\).
- Verify \(A^Tr=0\).
A Reliable Procedure Using QR
- Factor \(A=QR\) with orthonormal columns in \(Q\).
- Compute \(Q^Tb\).
- Solve the triangular system \(R\hat{x}=Q^Tb\).
- Compute \(A\hat{x}\) and the residual.
- Verify orthogonality if needed.
A Reliable Procedure for Linear Regression
- Choose the model \(y=\beta_0+\beta_1x\).
- Build one row \([1\ \ x_i]\) for each observation.
- Collect the observed \(y_i\) values into the target vector.
- Solve the least-squares problem for \(\beta_0,\beta_1\).
- Compute predicted values and residuals.
- Interpret the coefficients in the context of the model.
Example: Full Least-Squares Workflow
Consider
\[ A= \begin{bmatrix} 1&0\\ 1&1\\ 1&2 \end{bmatrix}, \qquad b= \begin{bmatrix} 1\\ 2\\ 2 \end{bmatrix}. \]Compute
\[ A^TA = \begin{bmatrix} 3&3\\ 3&5 \end{bmatrix} \]and
\[ A^Tb = \begin{bmatrix} 5\\ 6 \end{bmatrix}. \]Solve
\[ \begin{bmatrix} 3&3\\ 3&5 \end{bmatrix} \begin{bmatrix} \hat{x}_1\\ \hat{x}_2 \end{bmatrix} = \begin{bmatrix} 5\\ 6 \end{bmatrix}. \]This gives
\[ \boxed{ \hat{x} = \begin{bmatrix} 7/6\\ 1/2 \end{bmatrix}}. \]Compute the Fitted Vector
Multiply:
\[ A\hat{x} = \begin{bmatrix} 1&0\\ 1&1\\ 1&2 \end{bmatrix} \begin{bmatrix} 7/6\\ 1/2 \end{bmatrix}. \]Therefore,
\[ \boxed{ A\hat{x} = \begin{bmatrix} 7/6\\ 5/3\\ 13/6 \end{bmatrix}}. \]Compute the Residual
The residual is
\[ r = b-A\hat{x} = \begin{bmatrix} 1\\ 2\\ 2 \end{bmatrix} - \begin{bmatrix} 7/6\\ 5/3\\ 13/6 \end{bmatrix}. \]Thus
\[ \boxed{ r= \begin{bmatrix} -1/6\\ 1/3\\ -1/6 \end{bmatrix}}. \]One can verify that
\[ A^Tr=0. \]Why Least Squares Matters in Multidimensional Systems
Real systems rarely produce perfectly consistent measurements. Least squares provides a disciplined way to fit models, reconcile competing constraints, estimate parameters, and separate explainable structure from residual error.
Its geometry is projection, its algebra is the normal equations, and its numerical implementations connect naturally to QR factorization and singular value decomposition.
Least squares therefore sits at the intersection of linear algebra, statistics, optimization, scientific computing, engineering, economics, and data analysis.
Practice 1: Residual
If
\[ b= \begin{bmatrix} 3\\ 5 \end{bmatrix}, \qquad A\hat{x}= \begin{bmatrix} 2\\ 6 \end{bmatrix}, \]find the residual \(r=b-A\hat{x}\).
Practice 2: Normal Equations
Write the normal equations for a least-squares problem
\[ Ax\approx b. \]Practice 3: Orthogonality Condition
What equation expresses the fact that the residual is orthogonal to the column space of \(A\)?
Practice 4: Full Column Rank
If the columns of \(A\) are linearly independent, what explicit formula gives the unique least-squares solution?
Practice 5: Projection Matrix
For full-column-rank \(A\), write the projection matrix onto \(\operatorname{Col}(A)\).
Practice 6: Best Constant Fit
Find the least-squares constant fitting
\[ 4,\quad6,\quad8. \]Practice 7: Orthonormal Columns
If \(Q^TQ=I\), what is the least-squares coefficient vector for
\[ Qx\approx b? \]Practice 8: QR Least Squares
If \(A=QR\), what triangular system is solved for \(\hat{x}\)?
Practice 9: Regression Design Matrix
For data values \(x_1,x_2,x_3\), write the design matrix for fitting
\[ y=\beta_0+\beta_1x. \]Practice 10: Rank Deficiency
If the columns of \(A\) are linearly dependent, is \(A^TA\) invertible?
Practice 11: Left Null Space
In which fundamental subspace does the least-squares residual lie?
Practice 12: Identify the Error
A student solves an inconsistent system by finding \(\hat{x}\) from the normal equations, then claims
\[ A\hat{x}=b. \]Explain the error.
Practice Answers
Practice 1
\[ r = \begin{bmatrix} 3\\ 5 \end{bmatrix} - \begin{bmatrix} 2\\ 6 \end{bmatrix} = \boxed{ \begin{bmatrix} 1\\ -1 \end{bmatrix}}. \]Practice 2
\[ \boxed{ A^TA\hat{x}=A^Tb}. \]Practice 3
With
\[ r=b-A\hat{x}, \]orthogonality is expressed by
\[ \boxed{A^Tr=0}. \]Practice 4
\[ \boxed{ \hat{x} = (A^TA)^{-1}A^Tb}. \]Practice 5
\[ \boxed{ P= A(A^TA)^{-1}A^T}. \]Practice 6
The best constant is the mean:
\[ \frac{4+6+8}{3} = \boxed{6}. \]Practice 7
\[ \boxed{\hat{x}=Q^Tb}. \]Practice 8
\[ \boxed{R\hat{x}=Q^Tb}. \]Practice 9
\[ \boxed{ A= \begin{bmatrix} 1&x_1\\ 1&x_2\\ 1&x_3 \end{bmatrix}}. \]Practice 10
No. If the columns of \(A\) are dependent, then
\[ \boxed{A^TA\text{ is singular}}. \]Practice 11
Since
\[ A^Tr=0, \]the residual lies in
\[ \boxed{\operatorname{Null}(A^T)}. \]Practice 12
For an inconsistent system, \(b\) does not lie in the column space of \(A\). Least squares gives the closest vector \(A\hat{x}\), not an exact equality. In general,
\[ \boxed{A\hat{x}\neq b}. \]The difference is the residual.
What to Remember
Least squares solves the approximation problem
\[ \boxed{ \min_x\|Ax-b\|^2}. \]- The fitted vector \(A\hat{x}\) is the projection of \(b\) onto \(\operatorname{Col}(A)\).
- The residual is \(r=b-A\hat{x}\).
- The residual is orthogonal to the column space.
- The normal equations are \(A^TA\hat{x}=A^Tb\).
- If the columns of \(A\) are independent, the least-squares coefficients are unique.
- For full column rank, \(\hat{x}=(A^TA)^{-1}A^Tb\).
- QR factorization often provides a more numerically stable solution method.
- Linear regression is a least-squares projection problem.
- Weighted least squares changes the inner product used to measure error.
- Rank-deficient problems can be handled using the pseudoinverse and SVD.
The central geometric statement is:
\[ \boxed{ b=A\hat{x}+r, \qquad A\hat{x}\perp r}. \]Where We Go Next
Least squares finds the best approximation inside a column space. The next major structural tool analyzes matrices through orthogonal input and output directions and measures how strongly each direction is scaled.
The next lesson, Singular Values and Dimensional Reduction, develops singular values, singular vectors, the singular value decomposition, low-rank approximation, pseudoinverses, and the systematic compression of high-dimensional data.