Why a Least-Squares Fit Can Have Many Coefficient Vectors
In a least-squares problem, the target vector \(\mathbf{b}\) need not be an exact output of the matrix \(\mathbf{A}\). Instead, we seek a coefficient vector \(\mathbf{x}\) for which \(\mathbf{A}\mathbf{x}\) is as close as possible to \(\mathbf{b}\). If the columns of \(\mathbf{A}\) are dependent, different coefficient vectors can produce the very same output. Consequently, the best fitted vector can be unique even when the coefficients that produce it are not.
Throughout this tutorial, \(\mathbf{A}\in\mathbb{R}^{m\times n}\), \(\mathbf{b}\in\mathbb{R}^m\), and \(\mathbf{x}\in\mathbb{R}^n\). The fitted vector is \(\mathbf{A}\mathbf{x}\), and the residual is \(\mathbf{b}-\mathbf{A}\mathbf{x}\). The least-squares objective is the squared residual length, \(\|\mathbf{A}\mathbf{x}-\mathbf{b}\|^2\). Minimizing this quantity is equivalent to minimizing the residual length because length is nonnegative and squaring preserves its order.
The columns of \(\mathbf{A}\) span its column space, \(\operatorname{Col}\mathbf{A}\). Every fitted vector lies in that space. The Best Approximation Theorem says that for a finite-dimensional subspace, each target vector has a unique closest vector in the subspace, namely its orthogonal projection. Since \(\operatorname{Col}\mathbf{A}\) is finite-dimensional and every vector in it is \(\mathbf{A}\mathbf{x}\) for some \(\mathbf{x}\), at least one least-squares minimizer exists. The projection determines a unique best fitted vector; the question here is which coefficient vectors produce it.
The Complete Family of Minimizers
Proof. Write \(\mathbf{p}=\mathbf{A}\mathbf{x}_0\). This is the orthogonal projection of \(\mathbf{b}\) onto \(\operatorname{Col}\mathbf{A}\), so \(\mathbf{b}-\mathbf{p}\) is orthogonal to every vector in \(\operatorname{Col}\mathbf{A}\). First take any \(\mathbf{z}\in\operatorname{Nul}\mathbf{A}\). Then \(\mathbf{A}(\mathbf{x}_0+\mathbf{z})=\mathbf{A}\mathbf{x}_0+\mathbf{A}\mathbf{z}=\mathbf{p}+\mathbf{0}=\mathbf{p}\). Thus \(\mathbf{x}_0+\mathbf{z}\) has the same residual as \(\mathbf{x}_0\), and is also a minimizer. Conversely, let \(\mathbf{x}\) be any minimizer and set \(\mathbf{q}=\mathbf{A}\mathbf{x}\). Both \(\mathbf{p}\) and \(\mathbf{q}\) are closest vectors to \(\mathbf{b}\) in \(\operatorname{Col}\mathbf{A}\). Also, \(\mathbf{q}-\mathbf{p}\in\operatorname{Col}\mathbf{A}\). Orthogonality and the Pythagorean identity give \[ \|\mathbf{b}-\mathbf{q}\|^2 =\|(\mathbf{b}-\mathbf{p})-(\mathbf{q}-\mathbf{p})\|^2 =\|\mathbf{b}-\mathbf{p}\|^2+\|\mathbf{q}-\mathbf{p}\|^2. \] Both \(\mathbf{x}\) and \(\mathbf{x}_0\) are minimizers, so their residual lengths are equal. The displayed identity then forces \(\|\mathbf{q}-\mathbf{p}\|^2=0\), hence \(\mathbf{q}=\mathbf{p}\). Therefore \(\mathbf{A}(\mathbf{x}-\mathbf{x}_0)=\mathbf{0}\), which means \(\mathbf{x}-\mathbf{x}_0\in\operatorname{Nul}\mathbf{A}\). This proves that every minimizer lies in \(\mathbf{x}_0+\operatorname{Nul}\mathbf{A}\), as required. \(\square\)
The theorem separates two kinds of information. The fitted vector \(\mathbf{A}\mathbf{x}_0\) is fixed: it is the projection of \(\mathbf{b}\) onto the column space. The coefficient vector may vary, but only by adding a null-space vector, which changes the coefficients without changing the output.
Worked Example: A Nonexact Fit With One Free Parameter
Find all least-squares minimizers for \(\mathbf{A}=\begin{bmatrix}1&2\\0&0\\1&2\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\1\\0\end{bmatrix}\).
The columns of \(\mathbf{A}\) are \(\mathbf{v}=\begin{bmatrix}1\\0\\1\end{bmatrix}\) and \(2\mathbf{v}\), so \(\operatorname{Col}\mathbf{A}=\operatorname{span}\{\mathbf{v}\}\). The projection of \(\mathbf{b}\) onto this line is \(\frac{\mathbf{b}\cdot\mathbf{v}}{\mathbf{v}\cdot\mathbf{v}}\mathbf{v}\). Here \(\mathbf{b}\cdot\mathbf{v}=1\) and \(\mathbf{v}\cdot\mathbf{v}=2\), so the best fitted vector is \(\frac12\mathbf{v}=\begin{bmatrix}1/2\\0\\1/2\end{bmatrix}\).
For a coefficient vector \(\mathbf{x}=\begin{bmatrix}x_1\\x_2\end{bmatrix}\), the fitted vector is \((x_1+2x_2)\mathbf{v}\). It equals the projection exactly when \(x_1+2x_2=1/2\). Taking \(x_2=t\) as a free variable gives \(x_1=1/2-2t\), where \(t\in\mathbb{R}\). Thus every minimizer is \[ \mathbf{x}=\begin{bmatrix}1/2-2t\\t\end{bmatrix} =\begin{bmatrix}1/2\\0\end{bmatrix} +t\begin{bmatrix}-2\\1\end{bmatrix}. \] Indeed, \(\mathbf{A}\begin{bmatrix}-2\\1\end{bmatrix}=\begin{bmatrix}-2+2\\0\\-2+2\end{bmatrix}=\mathbf{0}\), so the direction of variation belongs to the null space.
Check: For every \(t\), \(\mathbf{A}\mathbf{x}=\begin{bmatrix}(1/2-2t)+2t\\0\\(1/2-2t)+2t\end{bmatrix}=\begin{bmatrix}1/2\\0\\1/2\end{bmatrix}\). The residual is \(\begin{bmatrix}1/2\\1\\-1/2\end{bmatrix}\), whose squared length is \(1/4+1+1/4=3/2\). It is orthogonal to \(\mathbf{v}\), since \(1/2-1/2=0\), confirming that the fitted vector is the projection.
How Free Variables Describe the Family
Once one minimizer \(\mathbf{x}_0\) is known, find the null space by solving the homogeneous system \(\mathbf{A}\mathbf{z}=\mathbf{0}\). In its reduced row echelon form, each nonpivot variable is free. Assigning values to those free variables determines the pivot variables and gives a null-space vector \(\mathbf{z}\). Adding that vector to \(\mathbf{x}_0\) gives a minimizer. Distinct choices of free-variable values give distinct null-space vectors and hence distinct coefficient vectors.
Worked Example: An Exact System With Three Coefficients
Find all least-squares minimizers for \(\mathbf{A}=\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}2\\0\end{bmatrix}\).
Here \(\mathbf{b}\) is in \(\operatorname{Col}\mathbf{A}\), because \(\mathbf{A}\begin{bmatrix}2\\0\\0\end{bmatrix}=\mathbf{b}\). Therefore the smallest possible residual length is \(0\), and the minimizers are exactly the solutions of \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Writing out its two equations gives \(x_1+x_3=2\) and \(x_2+x_3=0\). Set the free variable \(x_3=t\); then \(x_1=2-t\) and \(x_2=-t\). Thus \[ \mathbf{x}=\begin{bmatrix}2-t\\-t\\t\end{bmatrix} =\begin{bmatrix}2\\0\\0\end{bmatrix} +t\begin{bmatrix}-1\\-1\\1\end{bmatrix},\qquad t\in\mathbb{R}. \] The free direction is in the null space: \(\mathbf{A}\begin{bmatrix}-1\\-1\\1\end{bmatrix}=\begin{bmatrix}-1+1\\-1+1\end{bmatrix}=\mathbf{0}\).
Check: Multiplying the general coefficient vector back gives \(\mathbf{A}\begin{bmatrix}2-t\\-t\\t\end{bmatrix}=\begin{bmatrix}(2-t)+t\\-t+t\end{bmatrix}=\begin{bmatrix}2\\0\end{bmatrix}=\mathbf{b}\). Every member of the family is therefore an exact solution and has residual zero. Different values of \(t\) give different coefficient vectors, but not different fitted vectors.
An exact solution family is a special case of a least-squares family: when \(\mathbf{b}\in\operatorname{Col}\mathbf{A}\), the best residual is zero. When \(\mathbf{b}\notin\operatorname{Col}\mathbf{A}\), no coefficient vector solves \(\mathbf{A}\mathbf{x}=\mathbf{b}\), but the family theorem still applies to the minimizers.
Worked Example: Two Free Parameters in a Nonexact Fit
Find all least-squares minimizers for \(\mathbf{A}=\begin{bmatrix}1&2&-1\\1&2&-1\\0&0&0\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}1\\0\\1\end{bmatrix}\).
The columns are \(\mathbf{v}=\begin{bmatrix}1\\1\\0\end{bmatrix}\), \(2\mathbf{v}\), and \(-\mathbf{v}\), so the column space is \(\operatorname{span}\{\mathbf{v}\}\). Since \(\mathbf{b}\cdot\mathbf{v}=1\) and \(\mathbf{v}\cdot\mathbf{v}=2\), the projected fitted vector is \(\frac12\mathbf{v}=\begin{bmatrix}1/2\\1/2\\0\end{bmatrix}\). For \(\mathbf{x}=\begin{bmatrix}x_1\\x_2\\x_3\end{bmatrix}\), multiplication gives \(\mathbf{A}\mathbf{x}=(x_1+2x_2-x_3)\mathbf{v}\). The fit equals the projection when \(x_1+2x_2-x_3=1/2\).
Choose \(x_2=s\) and \(x_3=t\) freely. Then \(x_1=1/2-2s+t\), so the complete family is \[ \mathbf{x}=\begin{bmatrix}1/2-2s+t\\s\\t\end{bmatrix} =\begin{bmatrix}1/2\\0\\0\end{bmatrix} +s\begin{bmatrix}-2\\1\\0\end{bmatrix} +t\begin{bmatrix}1\\0\\1\end{bmatrix},\qquad s,t\in\mathbb{R}. \] Both directions are in the null space: \(\mathbf{A}\begin{bmatrix}-2\\1\\0\end{bmatrix}=\mathbf{0}\) and \(\mathbf{A}\begin{bmatrix}1\\0\\1\end{bmatrix}=\mathbf{0}\).
Check: For arbitrary \(s,t\), the scalar multiplying \(\mathbf{v}\) in \(\mathbf{A}\mathbf{x}\) is \((1/2-2s+t)+2s-t=1/2\). Hence every member gives \(\mathbf{A}\mathbf{x}=\begin{bmatrix}1/2\\1/2\\0\end{bmatrix}\). Its residual is \(\begin{bmatrix}1/2\\-1/2\\1\end{bmatrix}\), which is orthogonal to \(\mathbf{v}\) because \(1/2-1/2=0\). The residual’s squared length is \(1/4+1/4+1=3/2\), verifying the least-squares fit.
When Is the Minimizer Unique?
Proof. By the family theorem, if \(\mathbf{x}_0\) is a minimizer, all minimizers are \(\mathbf{x}_0+\mathbf{z}\) with \(\mathbf{z}\in\operatorname{Nul}\mathbf{A}\). The columns are linearly independent exactly when the equation \(\mathbf{A}\mathbf{z}=\mathbf{0}\) has only the solution \(\mathbf{z}=\mathbf{0}\): the equation expresses a linear combination of the columns equal to zero, and independence means every coefficient in that combination must be zero. If the columns are independent, the null space contains only \(\mathbf{0}\), so the family contains only \(\mathbf{x}_0\). If the columns are dependent, there is a nonzero vector \(\mathbf{z}\) with \(\mathbf{A}\mathbf{z}=\mathbf{0}\). Then \(\mathbf{x}_0+\mathbf{z}\ne\mathbf{x}_0\), and both are minimizers by the family theorem. Thus the minimizer is not unique. \(\square\)
Dependence therefore means nonuniqueness of coefficients, not nonuniqueness of the best fit. The theorem on the minimizer family guarantees that every coefficient vector in that family produces the same projection of \(\mathbf{b}\) onto \(\operatorname{Col}\mathbf{A}\).
Common Pitfall: Confusing Least Squares With an Exact Solve
A dependent-column least-squares problem does not require \(\mathbf{A}\mathbf{x}=\mathbf{b}\) to have a solution. For the first example, a mistaken attempt to solve exactly would require \(x_1+2x_2=1\), \(0=1\), and \(x_1+2x_2=0\). The middle equation is impossible, so there is no exact solution. It would be wrong to conclude that no least-squares minimizer exists. The correction is to project \(\mathbf{b}\) onto the column space: that gives the fitted vector \(\begin{bmatrix}1/2\\0\\1/2\end{bmatrix}\) and the entire minimizer family \(\begin{bmatrix}1/2-2t\\t\end{bmatrix}\).
A second error is to treat the free variables as changing the fit. They change the coefficient vector, but the difference between any two minimizers lies in \(\operatorname{Nul}\mathbf{A}\). If \(\mathbf{x}_1=\mathbf{x}_0+\mathbf{z}\) with \(\mathbf{A}\mathbf{z}=\mathbf{0}\), then \(\mathbf{A}\mathbf{x}_1=\mathbf{A}\mathbf{x}_0+\mathbf{0}=\mathbf{A}\mathbf{x}_0\). The output, and therefore the residual, stays fixed.
Check Your Understanding
For each question, distinguish the coefficient vector from the fitted vector.
- State the complete set of minimizers if \(\mathbf{x}_0\) is one minimizer and \(\operatorname{Nul}\mathbf{A}=\operatorname{span}\left\{\begin{bmatrix}1\\-1\end{bmatrix}\right\}\).
- For \(\mathbf{A}=\begin{bmatrix}1&1\\0&0\end{bmatrix}\) and \(\mathbf{b}=\begin{bmatrix}3\\1\end{bmatrix}\), find the projected fitted vector and parameterize all minimizers.
- Explain why adding a vector in \(\operatorname{Nul}\mathbf{A}\) preserves the fitted vector.
- Can a least-squares problem have multiple minimizers when \(\mathbf{b}\notin\operatorname{Col}\mathbf{A}\)? Explain using the family theorem.
- Prove that if the columns of \(\mathbf{A}\) are dependent, then every least-squares problem with that matrix has more than one minimizer.
