Least squares from gradients

Section 5.6 Least squares from gradients

Subsection The least squares problem

We now revisit least squares as an optimization problem. In Unit 4, residual orthogonality led to the normal equations. Here we obtain the same equations by minimizing a loss function and setting its gradient equal to zero.

🔗

For a matrix \(A\text{,}\) consider the least-squares problem

\begin{equation*} \min_{\mathbf{x}\in\mathbb{R}^n}\|A\mathbf{x}-\mathbf{b}\|^2. \end{equation*}

This asks for the minimum of the quantity \(\|A\mathbf{x}-\mathbf{b}\|^2\text{.}\) We now use the methods of optimization we have developed to solve this problem in a series of exercises.

🔗

Activity 5.6.1.

(a)

The gradient of \(g(\mathbf{x}) = \mathbf{d} \cdot \mathbf{x} \text{,}\) for a fixed vector \(\mathbf{d}\text{.}\)

🔗

Solution.

Expanding in components, \(g(\mathbf{x}) = d_1 x_1 + \cdots + d_n x_n\text{,}\) and we see that \(D_i g(\mathbf{x}) = d_i\text{,}\) i.e., so that \(\nabla g(\mathbf{x}) = \mathbf{d}\text{.}\)

🔗

(b)

The gradient of \(f(\mathbf{x}) = \mathbf{x}^T A \mathbf{x}\text{,}\) for an \(n \times n\) matrix \(A\text{.}\)

🔗

Solution.

We start by using the identity

\begin{gather*} \end{gather*}

So the derivative of this quantity in the variable \(x_i\) is

\begin{equation*} 2 A_{ii} x_i + \sum_{j \neq i} (A_{ij} + A_{ji}) x_j = \sum_{j = 1}^n (A_{ij} + A_{ji}) x_j\text{.} \end{equation*}

So the gradient of \(f\) is

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

🔗

(c)

The Jacobian of the vector-valued function \(\mathbf{F}(\mathbf{x}) = C \mathbf{x}\text{,}\) where \(C\) is a fixed \(m \times n\) matrix.

🔗

Solution.

We write

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

\begin{equation*} D_jF_i(\mathbf{x})=C_{ij}. \end{equation*}

Therefore

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

🔗

Activity 5.6.2.

Let \(A\) be an \(m \times n\) matrix with linearly independent columns and suppose \(\mathbf{b} \in \R^m\text{.}\) Consider the least squares problem

\begin{equation*} \min_{\mathbf{x} \in \R^n} \|A \mathbf{x} - \mathbf{b}\|^2. \end{equation*}

🔗

(a)

Find the critical points of the function \(h(\mathbf{x}) = \| A \mathbf{x} - \mathbf{b} \|^2\text{.}\)

🔗

Solution.

We expand

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

Taking gradients thus gives that

\begin{align*} \nabla h \amp = ((A^T A) + (A^T A)^T) \mathbf{x} - 2 A^T \mathbf{b} + 0\\ \amp = 2 (A^T A \mathbf{x} - A^T \mathbf{b})\text{.} \end{align*}

So the critical points of \(h\) occur when \(A^T A \mathbf{x} = A^T \mathbf{b}\text{.}\) This vector-equation is called the normal equation for the least squares problem.

🔗

Activity 5.6.3. Same normal equations in code.

Consider the code

🔗

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

What is xhat?
🔗

🔗
What is r?
🔗

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

🔗
How does this connect the Unit 4 and Unit 5 viewpoints?
🔗

🔗

Tags. [U5-LO6, U4-LO4 | C+T | Core]

🔗

Solution.

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

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

The expression A.T @ r checks whether

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

Unit 4 interpreted this as residual orthogonality: the residual is orthogonal to the columns of \(A\text{.}\) Unit 5 interprets the same condition as a zero-gradient equation for

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

🔗

Activity 5.6.4.

Determine whether any critical point is a local minimum, local maximum, or saddle point. Using this information, solve the least squares optimization problem.

🔗

Solution.

Recall that the Hessian is the Jacobian of the gradient. For \(h(\mathbf{x})=\|A\mathbf{x}-\mathbf{b}\|^2\text{,}\) this gives

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

So we need to determine whether \(A^TA\) is positive definite, negative definite, or indefinite. Let’s consider the quadratic form \(\mathbf{x}^T(A^TA)\mathbf{x}\) for any nonzero vector \(\mathbf{x} \in \R^n\text{:}\)

\begin{align*} \mathbf{x}^T(A^TA)\mathbf{x} \amp = (A\mathbf{x})^T(A\mathbf{x})\\ \amp = \|A\mathbf{x}\|^2 \end{align*}

Since \(A\mathbf{x} \neq \mathbf{0}\) for \(\mathbf{x} \neq \mathbf{0}\) - to see why, \(A\) has linearly independent columns and so has rank \(n\text{.}\) By the rank-nullity theorem Theorem 2.4.31, \(\operatorname{nullity}(A)=n-\operatorname{rank}(A)=0\text{,}\) and this means \(\ker(A) = \{ \mathbf{0} \}\text{.}\) So we conclude that \(\mathbf{x}^T(A^TA)\mathbf{x}\) is always positive when \(\mathbf{x} \neq \mathbf{0}\text{.}\) But if \(\mathbf{x}\) is a unit eigenvector for \(A^T A\) with eigenvalue \(\lambda\text{,}\) then we also find that

\begin{equation*} \mathbf{x}^T (A^T A) \mathbf{x} = \lambda \mathbf{x}^T \mathbf{x} = \lambda\text{,} \end{equation*}

which must be positive since \(\mathbf{x}^T (A^T A) \mathbf{x}\) is always positive. So \(A^T A\) only has positive eigenvalues. So \(H_h\) is positive definite by Theorem 5.4.14, and so \(h\) has a local minimum at any critical point.

🔗

Since \(A^T A\) only has positive eigenvalues, it also must be an invertible matrix. But this means that the least squares problem

\begin{equation*} \min_{\mathbf{x} \in \mathbf{R}^n} \| A \mathbf{x} - \mathbf{b} \|^2 \end{equation*}

has a single global optimum, at the unique solution to the normal equation \(A^T A \mathbf{x} = A^T \mathbf{b}\text{,}\) i.e., for \(\mathbf{x} = (A^T A)^{-1} A^T \mathbf{b}\text{.}\) So we have found a minimizer to the least squares problem.

🔗

This equation is not new. In Unit 4, the normal equations came from residual orthogonality. Now we derive the same equations by minimizing \(h(\mathbf{x})=\|A\mathbf{x}-\mathbf{b}\|^2\text{.}\) The condition \(\nabla h(\mathbf{x})=\mathbf{0}\) gives \(A^TA\mathbf{x}=A^T\mathbf{b}\text{.}\)

🔗

Viewpoint	Key condition	Equation
Projection	Residual orthogonal to \(\operatorname{col}(A)\)	\(A^T(\mathbf{b}-A\hat{\mathbf{x}})=\mathbf{0}\)
Calculus	Gradient of \(\\|A\mathbf{x}-\mathbf{b}\\|^2\) is zero	\(A^TA\hat{\mathbf{x}}=A^T\mathbf{b}\)
Hessian	\(2A^TA\) is positive definite if columns are independent	unique global minimum

🔗

Prev Top Next