# Excercise 6.1 and its solution in Bishop's PRML, Question 1

The problem comes from Exercise 6.1 of "Pattern Recognition and Machine Learning" by Christopher M. Bishop:

Consider the dual formulation of the least squares linear regression problem given in Section 6.1. Show that the solution for the components $$a_n$$ of the vector $$\bf a$$ can be expressed as a linear combination of the elements of the vector $${\bf\phi}({\bf x}_n)$$. Denoting these coefficients by the vector $$\bf w$$, show that the dual of the dual formulation is given by the original representation in terms of the parameter vector $$\bf w$$.

Note that the vector $${\bf\phi}({\bf x}_n)=(\phi_1({\bf x}_n),\phi_2({\bf x}_n),\ldots,\phi_M({\bf x}_n))^T$$. This exercise has an official solution. I copied it below:

We first of all note that $$J({\bf a})$$ depends on $${\bf a}$$ only through the form $$\bf Ka$$. Since typically the number $$N$$ of data points is greater than the number $$M$$ of basis functions, the matrix $${\bf K} = {\bf\Phi\Phi}^T$$ will be rank deficient. There will then be $$M$$ eigenvectors of $$\bf K$$ having non-zero eigenvalues, and $$N-M$$ eigenvectors with eigenvalue zero. We can then decompose $${\bf a} = {\bf a}_{\|}+{\bf a}_{\perp}$$ where $${\bf a}_{\|}^T{\bf a}_{\perp}=0$$ and $${\bf Ka}_{\perp}={\bf 0}$$. Thus the value of $${\bf a}_\perp$$ is not determined by $$J({\bf a})$$. We can remove the ambiguity by setting $${\bf a}_\perp={\bf 0}$$, or equivalently by adding a regularizer term $$\frac{\epsilon}{2}{\bf a}_\perp^T{\bf a}_\perp$$ to $$J({\bf a})$$ where $$\epsilon$$ is a small positive constant. Then $${\bf a}={\bf a}_\|$$ where $${\bf a}_\|$$ lies in the span of $${\bf K}={\bf\Phi\Phi}^T$$ and hence can be written as a linear combination of the columns of $$\bf\Phi$$, so that in component notation $$a_n=\sum\limits_{i=1}^M u_i\phi_i({\bf x}_n)$$ or equivalently in vector notation $${\bf a}={\bf\Phi u}.\tag{122}$$ Substituting (122) into (6.7) we obtain \begin{aligned} J({\bf u})&=\frac{1}{2}({\bf K\Phi u}-{\bf t})^T({\bf K\Phi u}-{\bf t})+\frac{\lambda}{2}{\bf u}^T{\bf\Phi}^T{\bf K\Phi u}\\ &=\frac{1}{2}({\bf\Phi\Phi}^T{\bf\Phi u}-{\bf t})^T({\bf\Phi\Phi}^T{\bf\Phi u}-{\bf t})+\frac{\lambda}{2}{\bf u}^T{\bf\Phi}^T{\bf\Phi\Phi}^T{\bf\Phi u}.\quad\quad\quad\quad(123)\end{aligned} Since the matrix $${\bf\Phi}^T{\bf\Phi}$$ has full rank we can define an equivalent parametrization given by $${\bf w}={\bf\Phi}^T{\bf\Phi u}$$ and substituting this into (123) we recover the original regularized error function (6.2).

Since it is not allowed to ask many questions, this is my first question about the solution:

1. For the first sentence "... $$J({\bf a})$$ depends on $${\bf a}$$ only through the form $$\bf Ka$$", how does the second term of (6.7), $$\frac{\lambda}{2}{\bf a}^T{\bf Ka}$$, depend on $$\bf Ka$$? Yes, there is a $$\bf Ka$$ in it, but there is also an $$\bf a$$ which does not "depend on $${\bf a}$$ only through the form $$\bf Ka$$".
• Please state what $J({\bf a})$ looks like in your 4 questions. Dec 26, 2022 at 8:26

From the explanation, I understand that the form of $$J(\mathbf a)$$ that is first mentioned does not have the regularization term in it. So, it should be $$J(\mathbf a)=\frac{1}{2}(\mathbf{Ka-t})^T(\mathbf{Ka-t})$$
which depend on $$\mathbf a$$ only through $$\mathbf{Ka}$$. And, they make a point stating that the null space of matrix $$\mathbf K$$ poses some problems and one approach to deal with it is to add a regularization.