Overdetermined linear systems

When analyzing real systems, it is easy to encounter the problem of determining the “solution” of an overdetermined linear system.

The importance of this topic is evident: when observations are made on a real system, they are naturally affected by observation noise. This noise compromises the result of an individual observation but, fortunately, it is normally possible to acquire many more observations than unknowns, thereby obtaining an overdetermined system. Under these conditions, obtaining a solution that minimizes the error requires a numerical regression technique, such as least squares. This first section presents mathematical techniques that are widely used throughout the book: for further details on these techniques, see chapter 4, which is devoted entirely to this topic.

Consider an overdetermined linear system

$$\mathbf{A}\mathbf{x}=\mathbf{y}$$ (1.1)

where $\mathbf{A}$ is a rectangular matrix $m\times n$ and with $m\geq n$. In general, such a system does not admit an exact solution, because the vector $\mathbf{y}$ may not belong to the column space of $\mathbf{A}$. However, for every possible solution $\mathbf{x}\in\mathbb{R}^{n}$, it is possible to define an error value, also called the residual, that this potential solution would produce. We therefore seek solutions that minimize the residual under a particular metric.

We define^1.1 the error metric as the square of the residual norm:

$$\epsilon(\mathbf{x}) = \left\Vert \mathbf{A}\mathbf{x}-\mathbf{y}\right\Vert^{2}.$$ (1.2)

The so-called “least-squares” solution of a linear system (1.1) is represented by the vector $\mathbf {x}$ that minimizes the Euclidean distance of the residual (1.2), that is,

$$\hat{\mathbf{x}} = \underset{\mathbf{x}}{\arg\min}\, \left\Vert\mathbf{A}\mathbf{x}-\mathbf{y}\right\Vert^{2}.$$ (1.3)

Finding the optimal solution of the system in the least-squares regression sense is therefore equivalent to finding the minimum of this error function as $\mathbf {x}$ varies.

Footnotes

... define^1.1

The motivation for this choice will be discussed in detail in the chapter on model analysis.