Exercise 3.16

Steps of the algorithm that combines ${\Phi }_3$ with linear regression.

1.

For each $x\in X$, apply ${\Phi }_3$ to obtain the matrix $Z$.

2.

Compute the pseudo-inverse $X^{\text{†}}$ of the matrix $Z$.

3.

Return $w_{\mathit{lin}}=X^{\text{†}}y$.

If the dimension of data is large and the order of polynomial transformation is big, the resulting dimension in the feature space will grow in the polynomial. The matrix $Z$ will be of size $N\times \tilde{d}$. The main computational cost will be spent on the calculation of the pseudo-inverse $X^{\text{†}}$.