Revisiting least squares

Section 5.6 Revisiting least squares

Subsection Least squares: three viewpoints

The squared-residual loss.

In the Unit 4 least-squares section, least squares was a projection problem. Given a matrix \(A\) and a target vector \(\mathbf b\text{,}\) a least-squares coefficient vector \(\widehat{\mathbf x}\) makes \(A\widehat{\mathbf x}\) as close as possible to \(\mathbf b\text{.}\)

🔗

We now study the same problem through the squared-residual loss

\begin{equation*} L(\mathbf x)=\|A\mathbf x-\mathbf b\|^2. \end{equation*}

🔗

Squaring the residual norm does not change its minimizers, and the squared expression is easier to differentiate. This subsection connects three viewpoints:

\begin{equation*} \text{residual orthogonality} \longleftrightarrow \text{zero gradient} \longleftrightarrow \text{curvature from }A^TA. \end{equation*}

🔗

Activity 5.6.1. Derivative identities for least squares (U3-LO3).

Compute the following derivatives.

🔗

For a fixed vector \(\mathbf d\text{,}\) let
🔗

\begin{equation*} g(\mathbf x)=\mathbf d\cdot\mathbf x. \end{equation*}

Compute \(\nabla g(\mathbf x)\text{.}\)
🔗

🔗
For a fixed \(n\times n\) matrix \(A\text{,}\) let
🔗

\begin{equation*} q(\mathbf x)=\mathbf x^TA\mathbf x. \end{equation*}

Compute \(\nabla q(\mathbf x)\text{.}\)
🔗

🔗
For a fixed \(m\times n\) matrix \(C\text{,}\) let
🔗

\begin{equation*} F(\mathbf x)=C\mathbf x. \end{equation*}

Compute \(J_F(\mathbf x)\text{.}\)
🔗

🔗

Solution.

Expanding the first function gives

\begin{equation*} g(\mathbf x)=d_1x_1+\cdots+d_nx_n. \end{equation*}

Therefore

\begin{equation*} \frac{\partial g}{\partial x_i}=d_i, \qquad \nabla g(\mathbf x)=\mathbf d. \end{equation*}

🔗

For the quadratic function,

\begin{equation*} q(\mathbf x) = \sum_{i=1}^n\sum_{j=1}^n A_{ij}x_ix_j. \end{equation*}

For \(1\leq k\leq n\text{,}\)

\begin{equation*} \frac{\partial q}{\partial x_k} = \sum_{j=1}^n A_{kj}x_j + \sum_{i=1}^n A_{ik}x_i. \end{equation*}

This is the \(k\)-th entry of

\begin{equation*} (A+A^T)\mathbf x. \end{equation*}

Hence

\begin{equation*} \nabla q(\mathbf x)=(A+A^T)\mathbf x. \end{equation*}

In particular, if \(A\) is symmetric, then

\begin{equation*} \nabla q(\mathbf x)=2A\mathbf x. \end{equation*}

🔗

Finally, the \(i\)-th component of \(F\) is

\begin{equation*} F_i(\mathbf x)=C_{i1}x_1+\cdots+C_{in}x_n. \end{equation*}

Thus

\begin{equation*} \frac{\partial F_i}{\partial x_j}=C_{ij}, \end{equation*}

and therefore

\begin{equation*} J_F(\mathbf x)=C. \end{equation*}

🔗

Activity 5.6.2. Gradient zero gives the normal equations (U5-LO6).

Let \(A\) be an \(m\times n\) matrix and let \(\mathbf b\in\mathbb R^m\text{.}\) Define

\begin{equation*} L(\mathbf x)=\|A\mathbf x-\mathbf b\|^2. \end{equation*}

🔗

Expand \(L(\mathbf x)\) as a quadratic function of \(\mathbf x\text{.}\)
🔗

🔗
Compute \(\nabla L(\mathbf x)\text{.}\)
🔗

🔗
Show that every critical point satisfies
🔗

\begin{equation*} A^TA\mathbf x=A^T\mathbf b. \end{equation*}

🔗
If
🔗

\begin{equation*} \mathbf r=\mathbf b-A\widehat{\mathbf x}, \end{equation*}

show that the normal equations are equivalent to
🔗

\begin{equation*} A^T\mathbf r=\mathbf0. \end{equation*}

How was this condition interpreted in the Unit 4 normal-equations theorem?
🔗

🔗

Solution.

We expand

\begin{align*} L(\mathbf x) \amp=(A\mathbf x-\mathbf b)^T(A\mathbf x-\mathbf b)\\ \amp=\mathbf x^TA^TA\mathbf x -2(A^T\mathbf b)^T\mathbf x +\mathbf b^T\mathbf b. \end{align*}

🔗

Since \(A^TA\) is symmetric, the preceding activity gives

\begin{equation*} \nabla L(\mathbf x) = 2A^TA\mathbf x-2A^T\mathbf b = 2A^T(A\mathbf x-\mathbf b). \end{equation*}

Therefore

\begin{equation*} \nabla L(\mathbf x)=\mathbf0 \end{equation*}

exactly when

\begin{equation*} A^TA\mathbf x=A^T\mathbf b. \end{equation*}

These are the normal equations.

🔗

\begin{equation*} \mathbf r=\mathbf b-A\widehat{\mathbf x}, \end{equation*}

then

\begin{equation*} A^T\mathbf r = A^T\mathbf b-A^TA\widehat{\mathbf x}. \end{equation*}

Thus the normal equations are equivalent to

\begin{equation*} A^T\mathbf r=\mathbf0. \end{equation*}

In Unit 4, this says that the residual is orthogonal to every column of \(A\text{,}\) or equivalently,

\begin{equation*} \mathbf r\perp\operatorname{col}(A). \end{equation*}

🔗

Activity 5.6.3. The same condition in code (U5-LO6, U4-LO4).

Consider the code

🔗

xhat = np.linalg.lstsq(A, b, rcond=None)[0]
r = b - A @ xhat
A.T @ r

What does xhat represent?
🔗

🔗
What does r represent?
🔗

🔗
What condition is checked by A.T @ r?
🔗

🔗
How do the projection and gradient viewpoints interpret the same output?
🔗

🔗

Solution.

The vector xhat is a least-squares coefficient vector. The vector r is the residual

\begin{equation*} \mathbf r=\mathbf b-A\widehat{\mathbf x}. \end{equation*}

The expression A.T @ r checks numerically whether

\begin{equation*} A^T\mathbf r=\mathbf0. \end{equation*}

Unit 4 interprets this condition as residual orthogonality. In the current subsection,

\begin{equation*} \nabla L(\widehat{\mathbf x}) = 2A^T(A\widehat{\mathbf x}-\mathbf b) = -2A^T\mathbf r, \end{equation*}

so the same calculation also checks whether the gradient is zero.

🔗

Activity 5.6.4. Curvature, global minimality, and uniqueness (U5-LO6).

Suppose \(\widehat{\mathbf x}\) satisfies the normal equations, and define

\begin{equation*} \mathbf r=\mathbf b-A\widehat{\mathbf x}. \end{equation*}

Let \(\mathbf z\in\mathbb R^n\text{.}\)

🔗

Compute the Hessian \(H_L(\mathbf x)\text{.}\)
🔗

🔗
Show that
🔗

\begin{equation*} \mathbf z^TA^TA\mathbf z=\|A\mathbf z\|^2. \end{equation*}

What does this say about the curvature of \(L\text{?}\)
🔗

🔗
Use \(A^T\mathbf r=\mathbf0\) to prove the exact identity
🔗

\begin{equation*} L(\widehat{\mathbf x}+\mathbf z) = L(\widehat{\mathbf x})+\|A\mathbf z\|^2. \end{equation*}

🔗
Explain why \(\widehat{\mathbf x}\) is a global minimizer.
🔗

🔗
Suppose the columns of \(A\) are linearly independent. Explain why the minimizer is unique.
🔗

🔗
Suppose \(\mathbf z\neq\mathbf0\) lies in \(\operatorname{null}(A)\text{.}\) Compare
🔗

\begin{equation*} A(\widehat{\mathbf x}+\mathbf z) \quad\text{and}\quad A\widehat{\mathbf x}, \end{equation*}

and compare their loss values.
🔗

🔗

Solution.

From

\begin{equation*} \nabla L(\mathbf x)=2A^T(A\mathbf x-\mathbf b), \end{equation*}

we obtain

\begin{equation*} H_L(\mathbf x)=2A^TA. \end{equation*}

🔗

For every \(\mathbf z\text{,}\)

\begin{equation*} \mathbf z^TA^TA\mathbf z = (A\mathbf z)^T(A\mathbf z) = \|A\mathbf z\|^2 \geq0. \end{equation*}

Thus the loss has nonnegative quadratic curvature in every direction. A direction is flat exactly when

\begin{equation*} A\mathbf z=\mathbf0. \end{equation*}

🔗

Since

\begin{equation*} A(\widehat{\mathbf x}+\mathbf z)-\mathbf b = A\mathbf z-\mathbf r, \end{equation*}

we have

\begin{align*} L(\widehat{\mathbf x}+\mathbf z) \amp= \|A\mathbf z-\mathbf r\|^2\\ \amp= \|A\mathbf z\|^2 -2\mathbf r^TA\mathbf z +\|\mathbf r\|^2. \end{align*}

But

\begin{equation*} \mathbf r^TA\mathbf z = (A^T\mathbf r)^T\mathbf z = 0, \end{equation*}

\begin{equation*} L(\widehat{\mathbf x}+\mathbf z) = \|\mathbf r\|^2+\|A\mathbf z\|^2 = L(\widehat{\mathbf x})+\|A\mathbf z\|^2. \end{equation*}

Since \(\|A\mathbf z\|^2\geq0\text{,}\) no other coefficient vector has smaller loss. Therefore \(\widehat{\mathbf x}\) is a global minimizer.

🔗

If the columns of \(A\) are linearly independent, then

\begin{equation*} A\mathbf z=\mathbf0 \end{equation*}

implies \(\mathbf z=\mathbf0\text{.}\) The displayed identity is then strict for every nonzero \(\mathbf z\text{,}\) so the minimizer is unique. Equivalently, \(A^TA\) is invertible and

\begin{equation*} \widehat{\mathbf x} = (A^TA)^{-1}A^T\mathbf b. \end{equation*}

🔗

If \(\mathbf z\neq\mathbf0\) lies in \(\operatorname{null}(A)\text{,}\) then

\begin{equation*} A(\widehat{\mathbf x}+\mathbf z) = A\widehat{\mathbf x}, \end{equation*}

and

\begin{equation*} L(\widehat{\mathbf x}+\mathbf z) = L(\widehat{\mathbf x}). \end{equation*}

Thus the fitted vector remains the same, but the coefficient vector is not unique.

🔗

Warning 5.6.5.

The second derivative test is a local test. The exact identity

\begin{equation*} L(\widehat{\mathbf x}+\mathbf z) = L(\widehat{\mathbf x})+\|A\mathbf z\|^2 \end{equation*}

gives the stronger global conclusion. Linear independence is needed for uniqueness of the coefficient vector, not for the least-squares problem to have a minimizer.

🔗

One equation, three viewpoints.

Viewpoint	Key calculation	Interpretation
Projection	\(A^T(\mathbf b-A\widehat{\mathbf x})=\mathbf0\)	The residual is orthogonal to \(\operatorname{col}(A)\text{.}\) 🔗
Gradient	\(\nabla L(\widehat{\mathbf x})=\mathbf0\)	The least-squares coefficient vector is a critical point of the squared-residual loss. 🔗
Curvature	\(H_L=2A^TA\) and 🔗 \(L(\widehat{\mathbf x}+\mathbf z)-L(\widehat{\mathbf x})\) 🔗 \(=\\|A\mathbf z\\|^2\) 🔗	The critical point is a global minimizer; it is unique when \(\operatorname{null}(A)=\{\mathbf0\}\text{.}\) 🔗

The normal equations are therefore one condition with three readings. Unit 4 supplied the geometry, the gradient gives the critical-point equation, and \(A^TA\) describes curvature and uniqueness.

🔗

In the fixed-feature subsection, the columns of a design matrix will be fixed nonlinear features. Training only their coefficient vector will then be exactly this least-squares problem.

🔗

Subsection Least squares with fixed nonlinear features

Fixed features and trained coefficients.

A model can be nonlinear in its input and still be linear in the parameters being fitted. Let

\begin{equation*} \phi_0,\phi_1,\ldots,\phi_p \end{equation*}

be fixed scalar-valued feature functions. For a coefficient vector

\begin{equation*} \mathbf c= \begin{bmatrix} c_0\\ c_1\\ \vdots\\ c_p \end{bmatrix}, \end{equation*}

define

\begin{equation*} N_{\mathbf c}(t) = c_0\phi_0(t)+c_1\phi_1(t)+\cdots+c_p\phi_p(t). \end{equation*}

🔗

Equivalently, if

\begin{equation*} \boldsymbol{\phi}(t) = \begin{bmatrix} \phi_0(t)\\ \phi_1(t)\\ \vdots\\ \phi_p(t) \end{bmatrix}, \end{equation*}

then

\begin{equation*} N_{\mathbf c}(t)=\boldsymbol{\phi}(t)^T\mathbf c. \end{equation*}

🔗

Given data

\begin{equation*} (t_1,y_1),\ldots,(t_m,y_m), \end{equation*}

form the design matrix

\begin{equation*} A= \begin{bmatrix} \phi_0(t_1)&\phi_1(t_1)&\cdots&\phi_p(t_1)\\ \phi_0(t_2)&\phi_1(t_2)&\cdots&\phi_p(t_2)\\ \vdots&\vdots&&\vdots\\ \phi_0(t_m)&\phi_1(t_m)&\cdots&\phi_p(t_m) \end{bmatrix}, \qquad \mathbf y= \begin{bmatrix} y_1\\ y_2\\ \vdots\\ y_m \end{bmatrix}. \end{equation*}

🔗

The prediction vector is

\begin{equation*} A\mathbf c= \begin{bmatrix} N_{\mathbf c}(t_1)\\ N_{\mathbf c}(t_2)\\ \vdots\\ N_{\mathbf c}(t_m) \end{bmatrix}. \end{equation*}

🔗

With squared-error loss,

\begin{equation*} L(\mathbf c) = \sum_{i=1}^m \bigl(N_{\mathbf c}(t_i)-y_i\bigr)^2 = \|A\mathbf c-\mathbf y\|^2. \end{equation*}

Thus minimizing \(L\) is exactly the least-squares problem from Least squares: three viewpoints.

🔗

The feature functions determine the columns of \(A\text{.}\) They are fixed before the coefficients are fitted. Only \(\mathbf c\) is trained.

🔗

Activity 5.6.6. Fixed nonlinear features, trained coefficients (U5-LO7).

Let

\begin{equation*} \sigma(t)=\tanh(t), \end{equation*}

and define the fixed feature functions

\begin{equation*} \phi_0(t)=1,\qquad \phi_1(t)=\sigma(t),\qquad \phi_2(t)=\sigma(t-1),\qquad \phi_3(t)=\sigma(t+1). \end{equation*}

The model is

\begin{equation*} N_{\mathbf c}(t) = c_0+c_1\sigma(t)+c_2\sigma(t-1)+c_3\sigma(t+1). \end{equation*}

🔗

For data \((t_i,y_i)\text{,}\) define row \(i\) of \(A\) to be \(\boldsymbol{\phi}(t_i)^T\text{.}\)

🔗

Write the feature vector \(\boldsymbol{\phi}(t)\text{.}\)
🔗

🔗
Write the design matrix \(A\text{.}\)
🔗

🔗
Explain why the prediction vector is \(A\mathbf c\text{.}\)
🔗

🔗
Write the squared-error loss \(L(\mathbf c)\text{.}\)
🔗

🔗
Which quantities are fixed, and which vector is trained?
🔗

🔗
Is the model linear as a function of \(t\text{?}\)
🔗

🔗
Is the model linear as a function of \(\mathbf c\text{?}\)
🔗

🔗
Why is fitting \(\mathbf c\) a least-squares problem?
🔗

🔗

Solution.

The feature vector is

\begin{equation*} \boldsymbol{\phi}(t) = \begin{bmatrix} 1\\ \tanh(t)\\ \tanh(t-1)\\ \tanh(t+1) \end{bmatrix}. \end{equation*}

🔗

Therefore

\begin{equation*} A= \begin{bmatrix} 1&\tanh(t_1)&\tanh(t_1-1)&\tanh(t_1+1)\\ 1&\tanh(t_2)&\tanh(t_2-1)&\tanh(t_2+1)\\ \vdots&\vdots&\vdots&\vdots\\ 1&\tanh(t_m)&\tanh(t_m-1)&\tanh(t_m+1) \end{bmatrix}. \end{equation*}

🔗

Row \(i\) of \(A\) is \(\boldsymbol{\phi}(t_i)^T\text{.}\) Hence the \(i\)-th entry of \(A\mathbf c\) is

\begin{equation*} \boldsymbol{\phi}(t_i)^T\mathbf c = N_{\mathbf c}(t_i). \end{equation*}

🔗

The squared-error loss is

\begin{equation*} L(\mathbf c)=\|A\mathbf c-\mathbf y\|^2. \end{equation*}

🔗

The inputs \(t_i\text{,}\) targets \(y_i\text{,}\) feature functions, and entries of \(A\) are fixed. The trained vector is

\begin{equation*} \mathbf c= \begin{bmatrix} c_0\\ c_1\\ c_2\\ c_3 \end{bmatrix}. \end{equation*}

🔗

The model is nonlinear as a function of \(t\text{,}\) because the feature functions contain \(\tanh\text{.}\) It is linear as a function of \(\mathbf c\text{,}\) because the predictions have the form \(A\mathbf c\text{.}\) Therefore fitting \(\mathbf c\) by squared error is a least-squares problem.

🔗

For

\begin{equation*} \mathbf t= \begin{bmatrix} -2\\-1\\0\\1\\2 \end{bmatrix}, \qquad \mathbf y= \begin{bmatrix} 4\\1\\0\\1\\4 \end{bmatrix}, \end{equation*}

the design matrix has shape \(5\times4\text{.}\) The linked lab constructs this matrix, solves for \(\mathbf c\text{,}\) and compares the fitted values with the data.

🔗

What “fixed hidden layer” means.

In machine-learning language, the feature vector \(\boldsymbol{\phi}(t)\) may be produced by a hidden layer. Calling the hidden layer fixed means that its internal weights, shifts, and nonlinear feature functions are not trained. Training only the final coefficients still gives the model

\begin{equation*} N_{\mathbf c}(t)=\boldsymbol{\phi}(t)^T\mathbf c, \end{equation*}

so squared-error training is ordinary least squares.

🔗

Activity 5.6.7. The same fixed-feature fit in code (U5-LO7).

A = np.column_stack([
    np.ones_like(t),
    np.tanh(t),
    np.tanh(t - 1),
    np.tanh(t + 1)
])

c = np.linalg.lstsq(A, y, rcond=None)[0]
yhat = A @ c
loss = np.linalg.norm(yhat - y)**2

What feature is stored in each column of A?
🔗

🔗
Which vector is trained?
🔗

🔗
What does yhat contain?
🔗

🔗
What quantity is stored in loss?
🔗

🔗
Why can np.linalg.lstsq be used?
🔗

🔗
Is this code fitting the locations of the shifts inside tanh?
🔗

🔗

Solution.

The columns of A are the fixed feature vectors

\begin{equation*} \mathbf 1,\qquad \bigl[\tanh(t_i)\bigr]_{i=1}^m,\qquad \bigl[\tanh(t_i-1)\bigr]_{i=1}^m,\qquad \bigl[\tanh(t_i+1)\bigr]_{i=1}^m, \end{equation*}

where each bracketed vector is evaluated entrywise at the data inputs. The trained vector is \(\mathbf c\text{.}\) The vector yhat contains the fitted values

\begin{equation*} A\mathbf c. \end{equation*}

🔗

The variable loss stores

\begin{equation*} \|A\mathbf c-\mathbf y\|^2. \end{equation*}

🔗

The command np.linalg.lstsq applies because \(A\) is fixed and the prediction vector is linear in \(\mathbf c\text{.}\) The shifts \(0,1,-1\) inside the feature functions are not being fitted.

🔗

Warning 5.6.8.

The least-squares reduction depends on the features being fixed. If the shifts \(\beta_j\) in features such as

\begin{equation*} \tanh(t-\beta_j) \end{equation*}

are also trained, then the design matrix depends on the parameters:

\begin{equation*} A=A(\boldsymbol{\beta}). \end{equation*}

🔗

The loss

\begin{equation*} \|A(\boldsymbol{\beta})\mathbf c-\mathbf y\|^2 \end{equation*}

is no longer a quadratic function of all trained parameters. One least-squares solve does not train the whole model; gradient descent and the chain rule from Unit 3 are then needed.

🔗

Prev Top Next