9 Positive Definite Matrices and the Closest Point Problem
“In the broad light of day mathematicians check their equations and their proofs, leaving no stone unturned in their search for rigour. But, at night, under the full moon, they dream, they float among the stars and wonder at the miracle of the heavens. They are inspired. Without dreams there is no art, no mathematics, no life.”
– Michael Atiyah
We consider \mathbb{R}^m with an inner product \langle \cdot , \cdot \rangle and the associated norm \lVert \cdot \rVert.
9.1 The Closest Point Problem
Let \mathbf{W} \subset \mathbb{R}^m be a subspace of \mathbb{R}^m of dimension n \le m, and let \mathbf{b} \in \mathbf{W}. Find the unique point \tilde{\mathbf{w}} \in \mathbf{W} such that \lVert \mathbf{b} - \tilde{\mathbf{w}} \rVert = \min_{\mathbf{w} \in \mathbf{W}} \lVert \mathbf{b} - \mathbf{w} \rVert
The fact that there is such an unique closest point is a consequence of the theorem in the last section on minimization of positive definite quadratic forms. The quadratic form we will minimize is \lVert \mathbf{b} - \mathbf{w} \rVert^2 = \lVert \mathbf{w} \rVert^2 -2\langle \mathbf{w}, \mathbf{b}\rangle + \lVert \mathbf{b} \rVert^2 If we consider a basis \mathbf{w}_1, \cdots, \mathbf{w}_n of \mathbf{W}, we can write any \mathbf{w} \in \mathbf{W} as \mathbf{w}=x_1\mathbf{w}_1 + \cdots + x_n\mathbf{w}_n.
The term \lVert \mathbf{w} \rVert^2 can be written as \sum_{i,j=1}^n x_ix_j\langle \mathbf{w}_i, \mathbf{w}_j\rangle = \sum_{i,j=1}^n x_ix_j k_{ij} = \mathbf{x}^T \mathbf{K} \mathbf{x}, where \mathbf{x}=[x_i] and \mathbf{K}= [\langle \mathbf{w}_i, \mathbf{w}_j\rangle]. Similarly, \langle \mathbf{w}, \mathbf{b}\rangle can be written as \langle \mathbf{w}, \mathbf{b}\rangle =\sum_{i=1}^n x_i \langle \mathbf{w}_i, \mathbf{b}\rangle = \mathbf{x}^T \mathbf{f}, where \mathbf{f}=[\langle \mathbf{w}_i, \mathbf{b}\rangle]. Therefore, the quadratic form we need to minimize is the same as in the last section: p(\mathbf{x})=\mathbf{x}^T\mathbf{K} \mathbf{x} -2\mathbf{x}^T\mathbf{f} +c, where c=\lVert \mathbf{b} \rVert^2. We note that matrix \mathbf{K} is a Gram matrix formed of linearly independent vectors \mathbf{w}_1, \cdots, \mathbf{w}_n, and therefore is a positive definite matrix. Therefore, we have the following result:
Let \mathbf{w}_1, \cdots, \mathbf{w}_n be a basis for a n-dimensional subspace \mathbf{W} of \mathbb{R}^m, where n \le m. Then there is a unique point \tilde{\mathbf{w}}= \tilde{x}_1\mathbf{w}_1 + \cdots + \tilde{x}_n\mathbf{w}_n \in \mathbf{W} that is closest to \mathbf{b}, where \tilde{\mathbf{x}} is the unique solution of \mathbf{K}\tilde{x}=\mathbf{f}. The corresponding minimum distance is given by \sqrt{\lVert \mathbf{b}\rVert^2 - \mathbf{f}^T \tilde{\mathbf{x}}}.
Exercise 9.1 Let \mathbf{b}=[1,0,0]^T \in \mathbb{R}^3. Find the point in the subspace of \mathbb{R}^3 spanned by [1,2,-1]^T and [2,-3,-1]^T that is closest to \mathbf{b}, and the corresponding minimum distance.
Exercise 9.2 Let \mathbf{b}=[3,1,2,1]^T \in \mathbb{R}^4. Find the point in the subspace of \mathbb{R}^4 spanned by [1,1,0,0]^T and [0,0,1,1]^T that is closest to \mathbf{b}, and the corresponding minimum distance.
Exercise 9.3 Let \mathbf{b}=[1,1,2,-2]^T \in \mathbb{R}^4. Find the point in the subspace of \mathbb{R}^4 spanned by [1,2,-1,0]^T, [0,1,-2,-1]^T and [1,0,3,2]^T that is closest to \mathbf{b}, and the corresponding minimum distance.
Exercise 9.4 Let \mathbf{W} be a subspace of \mathbb{R}^4 and let \mathbf{b} \in \mathbb{R}^4. Prove that the closest point \tilde{\mathbf{w}} \in \mathbf{W} as given by the above theorem is the orthogonal projection of \mathbf{b} onto \mathbf{W}.