Many applications require solving a system of linear equations 𝑨𝒙 = 𝒚 for 𝒙 given 𝑨 and 𝒚. In practice, often there is no exact solution for 𝒙, so one seeks an approximate solution. This chapter focuses on least-squares formulations of this type of problem. It briefly reviews the 𝑨𝒙 = 𝒚 case and then motivates the more general 𝑨𝒙 ≈ 𝒚 cases. It then focuses on the over-determined case where 𝑨 is tall, emphasizing the insights offered by the SVD of 𝑨. It introduces the pseudoinverse, which is especially important for the under-determined case where 𝑨 is wide. It describes alternative approaches for the under-determined case such as Tikhonov regularization. It introduces frames, a generalization of unitary matrices. It uses the SVD analysis of this chapter to describe projection onto a subspace, completing the subspace-based classification ideas introduced in the previous chapter, and also introduces a least-squares approach to binary classifier design. It introduces recursive least-squares methods that are important for streaming data.

We study the solution of overdetermined systems of equations. Introduce weak, and in particular least squares solutions. For full rank systems, we show existence and uniqueness via the normal equations. We introduce projection matrices and the QR factorization. We discuss the computation of the QR factorization with the help of Householder reflectors. For rank defficient systems we prove the existence and uniqueness of a minimal norm least squares solution. We introduce the Moore-Penrose pseudoinverse, show how it relates to the SVD, and how it can be used to solve rank defficient systems.