Skip to main content

MATH 345: Linear Algebra and Optimization

Sebastien Roch with Jacob Denson and Kaitlyn Phillipson

Section 4.3 Least squares as projection

Least squares is projection when the subspace is \(\operatorname{col}(A)\text{.}\)
🔗

Projection as an optimization problem.

Orthogonal projection can also be read as an optimization problem. Given a subspace \(U\subseteq \mathbb R^n\) and a vector \(\mathbf{x}_0\text{,}\) the projection \(\operatorname{proj}_U(\mathbf{x}_0)\) is the vector \(\mathbf{x}^*\in U\) that minimizes \(\|\mathbf{x}-\mathbf{x}_0\|\text{.}\)
🔗
This is the first version of a pattern that will recur in Units 5 and 7: choose a space of allowable approximations, choose a way to measure error, and find the point in the allowable space with smallest error.
🔗
🔗

Least squares as projection.

The equation \(A\mathbf{x}=\mathbf{b}\) may have no solution because \(\mathbf{b}\notin\operatorname{col}(A)\text{.}\) The least-squares problem asks for \(\mathbf{x}\) so that \(A\mathbf{x}\) is as close as possible to \(\mathbf{b}\text{:}\)
\begin{equation*} \min_{\mathbf{x}}\|A\mathbf{x}-\mathbf{b}\|. \end{equation*}
🔗
Unit 2 asked whether a target vector was reachable. Least squares asks for the closest reachable output when the target is not reachable.
🔗

Note 4.3.1. Column spaces and null spaces.

Let \(A\) be an \(m\times n\) matrix with columns \(\mathbf{a}_1,\ldots,\mathbf{a}_n\text{.}\) Then
\begin{equation*} \operatorname{col}(A)^\perp=\operatorname{null}(A^T). \end{equation*}
Indeed, a vector \(\mathbf{r}\) is in \(\operatorname{col}(A)^\perp\) exactly when it is orthogonal to every column of \(A\text{.}\) That means
\begin{equation*} \mathbf{a}_1\cdot \mathbf{r}=0,\ldots,\mathbf{a}_n\cdot \mathbf{r}=0, \end{equation*}
which is exactly the matrix equation \(A^T\mathbf{r}=\mathbf{0}\text{.}\)
🔗
🔗
Geometrically, \(A\mathbf{x}\) is a point in \(\operatorname{col}(A)\text{.}\) Thus the best possible \(A\hat{\mathbf{x}}\) is the projection of \(\mathbf{b}\) onto the column space:
\begin{equation*} A\hat{\mathbf{x}}=\operatorname{proj}_{\operatorname{col}(A)}(\mathbf{b}). \end{equation*}
The residual \(\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}\) is orthogonal to every column of \(A\text{.}\) Equivalently, \(\mathbf{r}\in\operatorname{col}(A)^\perp=\operatorname{null}(A^T)\text{,}\) so
\begin{equation*} A^T(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0},\qquad A^TA\hat{\mathbf{x}}=A^T\mathbf{b}. \end{equation*}
🔗
The closest point \(A\hat{\mathbf{x}}\) in \(\operatorname{col}(A)\) is unique. The coefficient vector \(\hat{\mathbf{x}}\) is unique when the columns of \(A\) are linearly independent. If the columns are dependent, several different coefficient vectors may produce the same closest point.
🔗

Activity 4.3.1. Why \(A^TA\) is invertible for independent columns.

Let \(A\) be an \(m\times n\) matrix. Prove that \(A\) has linearly independent columns if and only if \(A^T A\) is invertible.
🔗
Solution.
Suppose that the columns of \(A\) are linearly independent. To show that \(A^T A\) is invertible, it is enough to show that \((A^T A)\mathbf{x}=\mathbf{0}\) has only the trivial solution. If \((A^T A)\mathbf{x}=\mathbf{0}\text{,}\) then
\begin{equation*} 0=\mathbf{x}^T(A^T A)\mathbf{x}=(A\mathbf{x})^T(A\mathbf{x})=\|A\mathbf{x}\|^2. \end{equation*}
Therefore \(A\mathbf{x}=\mathbf{0}\text{.}\) Since the columns of \(A\) are linearly independent, \(\mathbf{x}=\mathbf{0}\text{.}\) Hence \(A^T A\) is invertible.
🔗
Conversely, suppose that \(A^T A\) is invertible and \(A\mathbf{x}=\mathbf{0}\text{.}\) Then
\begin{equation*} A^T A\mathbf{x}=A^T\mathbf{0}=\mathbf{0}. \end{equation*}
Since \(A^T A\) is invertible, \(\mathbf{x}=\mathbf{0}\text{.}\) Therefore the columns of \(A\) are linearly independent.
🔗
🔗
🔗

Activity 4.3.2. Unit 2 target revisited.

Let
\begin{equation*} A=\begin{bmatrix}1&0\\0&1\\1&1\end{bmatrix}, \qquad \mathbf{b}=\begin{bmatrix}1\\2\\4\end{bmatrix}. \end{equation*}
🔗
  1. Explain why \(A\mathbf{x}=\mathbf{b}\) has no solution.
    🔗
    🔗
  2. Form \(A^TA\) and \(A^T\mathbf{b}\text{.}\)
    🔗
    🔗
  3. Solve the normal equations.
    🔗
    🔗
  4. Compute \(A\hat{\mathbf{x}}\) and \(\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}\text{.}\)
    🔗
    🔗
  5. Check \(A^T\mathbf{r}=\mathbf{0}\text{.}\)
    🔗
    🔗
Solution.
If \(\mathbf{x}=\begin{bmatrix}x_1\\x_2\end{bmatrix}\text{,}\) then
\begin{equation*} A\mathbf{x} = \begin{bmatrix}x_1\\x_2\\x_1+x_2\end{bmatrix}. \end{equation*}
The first two coordinates of \(A\mathbf{x}=\mathbf{b}\) force \(x_1=1\) and \(x_2=2\text{,}\) but then the third coordinate would be \(3\text{,}\) not \(4\text{.}\) So the target is not reached exactly.
🔗
The normal equations use
\begin{equation*} A^TA=\begin{bmatrix}2&1\\1&2\end{bmatrix}, \qquad A^T\mathbf{b}=\begin{bmatrix}5\\6\end{bmatrix}. \end{equation*}
Solving
\begin{equation*} \begin{bmatrix}2&1\\1&2\end{bmatrix}\hat{\mathbf{x}} = \begin{bmatrix}5\\6\end{bmatrix} \end{equation*}
gives
\begin{equation*} \hat{\mathbf{x}}=\begin{bmatrix}4/3\\7/3\end{bmatrix}. \end{equation*}
🔗
Therefore
\begin{equation*} A\hat{\mathbf{x}} = \begin{bmatrix}4/3\\7/3\\11/3\end{bmatrix}, \qquad \mathbf{r} = \mathbf{b}-A\hat{\mathbf{x}} = \begin{bmatrix}-1/3\\-1/3\\1/3\end{bmatrix}. \end{equation*}
Finally,
\begin{equation*} A^T\mathbf{r} = \begin{bmatrix}1&0&1\\0&1&1\end{bmatrix} \begin{bmatrix}-1/3\\-1/3\\1/3\end{bmatrix} = \begin{bmatrix}0\\0\end{bmatrix}. \end{equation*}
The residual is not zero, so the target is still not reached exactly. But the residual is orthogonal to the column space, so the fitted output is the closest reachable output.
🔗
🔗
🔗
🔗

Regression example.

Fit \(y=c_0+c_1t\) to \((0,1)\text{,}\) \((1,2)\text{,}\) and \((2,2)\text{.}\) Then
\begin{equation*} A=\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix},\qquad \mathbf{b}=\begin{bmatrix}1\\2\\2\end{bmatrix}. \end{equation*}
The normal equations are \(A^TA\mathbf{c}=A^T\mathbf{b}\text{.}\) Since
\begin{equation*} A^TA=\begin{bmatrix}3&3\\3&5\end{bmatrix},\qquad A^T\mathbf{b}=\begin{bmatrix}5\\6\end{bmatrix}, \end{equation*}
we get \(c_0=7/6\) and \(c_1=1/2\text{.}\)
🔗
The fitted line is \(y=7/6+(1/2)t\text{.}\) The fitted values are
\begin{equation*} A\mathbf{c}=\begin{bmatrix}7/6\\5/3\\13/6\end{bmatrix}, \end{equation*}
so the residual is
\begin{equation*} \mathbf{r}=\mathbf{b}-A\mathbf{c}=\begin{bmatrix}-1/6\\1/3\\-1/6\end{bmatrix}. \end{equation*}
Check the orthogonality condition:
\begin{equation*} A^T\mathbf{r}= \begin{bmatrix}1&1&1\\0&1&2\end{bmatrix} \begin{bmatrix}-1/6\\1/3\\-1/6\end{bmatrix} = \begin{bmatrix}0\\0\end{bmatrix}. \end{equation*}
🔗
🔗

Code snapshot: fitting and checking the residual.

Code snapshot: fitting and checking the residual
🔗
xhat = np.linalg.lstsq(A, b, rcond=None)[0]
r = b - A @ xhat
A.T @ r
The vector \(\mathbf{r}\) is the residual. The output of A.T @ r should be close to zero because the least-squares residual is orthogonal to the columns of \(A\text{.}\)
🔗
🔗
QR will compute the same least-squares solution without directly forming \(A^TA\text{.}\)
🔗
🔗
PrevTopNext