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$".
  • $\begingroup$ Please state what $J({\bf a})$ looks like in your 4 questions. $\endgroup$
    – statmerkur
    Dec 26, 2022 at 8:26

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.