Overdetermined linear systems

We now consider the case of an overdetermined system

$$\mathbf{A}\mathbf{x}\simeq\mathbf{b}, \qquad \mathbf{A}\in\mathbb{R}^{m\times n}, \qquad m>n.$$ (1.37)

Suppose that $\mathbf{A}$ has full column rank. As discussed in section 1.1, the least-squares solution can be expressed using the singular value decomposition

$$\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^{\top},$$ (1.38)

as

$$\hat{\mathbf{x}} = \mathbf{A}^{+}\mathbf{b} = \mathbf{V}\mathbf{\Sigma}^{-1}\mathbf{U}^{\top}\mathbf{b}.$$ (1.39)

Expanding the preceding relation gives

$$\hat{\mathbf{x}} = \sum_{i=1}^{n} \frac{\mathbf{u}_i^{\top}\mathbf{b}}{\sigma_i} \mathbf{v}_i.$$ (1.40)

This expression clearly illustrates the role of the singular values. The component of the vector $\mathbf{b}$ along $\mathbf{u}_i$ contributes to the solution in the direction $\mathbf{v}_i$ with a factor $1/\sigma_i$. Consequently, a perturbation of the component $\mathbf{u}_i^{\top}\mathbf{b}$ is amplified when $\sigma_i$ assumes small values.

In this case, the condition number can be defined, in the 2-norm, as

$$\kappa_2(\mathbf{A}) = \frac{\sigma_1}{\sigma_n}.$$ (1.41)

where $\sigma_n$ is the smallest nonzero singular value. If $\sigma_n$ tends to zero, the problem becomes increasingly sensitive to perturbations in the data.

Conditioning therefore provides a geometric interpretation of the solution: directions associated with larger singular values are determined more robustly, whereas those associated with smaller singular values are determined more sensitively with respect to perturbations.