Homogeneous linear systems

We now consider the case in which the linear system to be solved is homogeneous.

A homogeneous linear system has the form

$$\mathbf{A}\mathbf{x}=0.$$ (1.22)

The trivial solution $\mathbf{x}=0$, which is also obtained through least-squares minimization, is normally not useful for the problem at hand.

In this case, still in the least-squares regression sense, it is necessary to find a nonzero $\mathbf{x}\in\mathbb{R}^{n}$ representing a direction belonging to the kernel of $\mathbf{A}$. The generating vector of the subspace is determined up to one or more multiplicative factors, depending on the dimension of the null space. To obtain a unique solution, an additional constraint must be imposed, for example $\Vert\mathbf{x}\Vert=1$, thereby formulating the problem as constrained minimization:

$$\hat{\mathbf{x}} = \underset{\mathbf{x}}{\arg\min}\, \Vert\mathbf{A}\mathbf{x}\Vert^{2}, \qquad \Vert\mathbf{x}\Vert=1.$$ (1.23)

In this case too, the SVD proves to be an extremely effective technique: the bases of the kernel of $\mathbf{A}$ are in fact the columns of $\mathbf{V}$ associated with the zero singular values of the matrix $\mathbf{\Sigma}$. In the presence of noise, there will generally be no exactly zero singular value; in this case, the direction associated with singular values sufficiently small relative to the scale of the problem must be identified.

The eigenvectors associated with zero singular values are not, strictly speaking, eigenvectors of the matrix $\mathbf{\Sigma}$, but the columns of $\mathbf{V}$ associated with these singular values are eigenvectors of $\mathbf{A}^{\top}\mathbf{A}$ associated with the zero eigenvalue. They therefore form a basis of the kernel of $\mathbf{A}$. The number of zero singular values represents the dimension of the kernel itself.

The presence of zero singular values also explains why the pseudoinverse defined through the normal equations is not a general definition: in their presence, $\mathbf{A}^{\top}\mathbf{A}$ is not invertible. The definition based on the SVD naturally resolves this problem instead, by replacing each zero singular value with a zero value in the matrix $\mathbf{\Sigma}^{+}$.

The general solution of the homogeneous system can be expressed as

$$\mathbf{x} = \sum_{i=1}^{N}\beta_i\mathbf{v}_i$$ (1.24)

where $\mathbf{v}_i$ are the columns of the matrix $\mathbf{V}$ corresponding to the $N$ zero singular values of $\mathbf{A}$.

This result will be used in section 2.9.1 in the discussion of the PCA algorithm, where the SVD will once again be used to identify the principal directions of a data set.

From a numerical standpoint, the SVD is therefore one of the most stable and versatile techniques for solving and analyzing linear systems, and this technique will be used extensively throughout the book.