Optimality and least squares · Definition

Linear least squares

continuous optimizationoptimality and least squares

Before you start you need to know

When a linear system \(Ax=b\) has no exact solution, we look for the \(x\) that makes the error as small as possible. This problem appears in data fitting, regression, and estimation.

Definition

Optimization problem that minimizes the sum of squared residuals \(\|Ax-b\|_2^2\) to approximate a vector \(b\) by linear combinations of the columns of \(A\).

\[\min_{x}\ \|Ax-b\|_2^2 \quad \Rightarrow \quad A^\top A\,x = A^\top b\]

The function \(f(x)=\|Ax-b\|_2^2\) is convex, and if the columns of \(A\) are linearly independent its solution is unique. The gradient \(\nabla f(x)=2A^\top(Ax-b)\) vanishes exactly at the normal equations \(A^\top A x=A^\top b\). Geometrically, \(Ax^*\) is the orthogonal projection of \(b\) onto the column space of \(A\).

To fit the line \(y=c_0+c_1 t\) to the points \((0,1),(1,2),(2,2)\), the matrix \(A\) has rows \((1,0),(1,1),(1,2)\) and \(b=(1,2,2)\). The normal equations give \(A^\top A=\begin{pmatrix}3&3\\3&5\end{pmatrix}\) and \(A^\top b=(5,6)^\top\), so \(c_1=\tfrac{1}{2}\) and \(c_0=\tfrac{7}{6}\).

A typical mistake is solving \(Ax=b\) with the inverse of \(A\) when \(A\) is not square or not invertible. Another frequent error is forgetting the transpose in the normal equations and writing \(AA^\top x=b\), which gives a different solution.

Think about it

What would happen to the minimizers if the columns of \(A\) were linearly dependent?

There would be infinitely many solutions because \(A^\top A\) would be singular, but \(Ax^*\) would still be unique.

Exercises 10

  1. What is the gradient of \(f(x)=\|Ax-b\|_2^2\) with respect to \(x\)?
  2. What are the normal equations of the least squares problem?
  3. If \(A\) has linearly independent columns, how many solutions does the least squares problem have?
  4. What does \(Ax^*\) represent geometrically, where \(x^*\) is the least squares solution?
  5. If \(A\) is a \(3\times 2\) matrix, what is the dimension of \(A^\top A\)?
  6. Given \(A=\begin{pmatrix}1&0\\0&1\\1&1\end{pmatrix}\) and \(b=(1,2,4)^\top\), what is \(A^\top b\)?
  7. With \(A^\top A=\begin{pmatrix}2&1\\1&2\end{pmatrix}\) and \(A^\top b=(3,3)^\top\), what is the least squares solution?
  8. To fit \(y=c\,t\) (no intercept) to the points \((1,2)\) and \((2,3)\), what is \(c\)?
  9. Why is it not advisable to compute the least squares solution as \(x=(A^\top A)^{-1}A^\top b\) when \(A^\top A\) is ill-conditioned?
  10. Let \(A=\begin{pmatrix}1&1\\1&2\\1&3\end{pmatrix}\) and \(b=(1,2,2)^\top\). Compute the least squares solution \(x^*\) and the residual \(\|Ax^*-b\|_2^2\).

References

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.