Part I: Kernel Principal Components Analysis
You will implement the Kernel PCA (KPCA) algorithm as described in Algorithm 7.2 (Chapter 7, page 208). You need to compute the kernel and then center it, followed by extracting the dominant eigenvectors, which will give you the components of the directions in feature space. Next you will project and visualize the data. To compute the principal components (PCs) from the kernel matrix, you may use the inbuilt numpy function eigh.
Using the linear kernel (i.e., polynomial kernel with degree q = 1 and c = 0; in other words K(x, y) = xT y), how many dimensions are required to capture α = 0.95 fraction of the total variance? For the same linear kernel, compute the projected points along the first two kernel PCs, and create a scatter plot of the projected points.
Next, use the covariance matrix for the original data to compute the regular principal components, i.e., for the covariance matrix. Project the data onto the first two PCs. How do the eigenvalues and the projection compare with that obtained via Kernel PCA with linear kernel?
Finally, use the gaussian kernel and repeat the exercise for kernel PCA. Project the points onto the first two PCs and plot the scatter plot. For the variance or spread of the gaussian kernel, namely σ2, read it from the command line. Try different values and submit your plot for the value that makes most sense to you (observe the projected plots for various spread values and then decide).
Part II: Linear Regression via QR Factorization
You will implement the linear regression algorithm via QR factorization, namely Algorithm 23.1 on page 602 in Chapter 23.
CSCI4390: You can use the numpy.linalg.qr function to compute the QR factorization.
CSCI6390: You must implement QR factorization on your own, as described in Section 23.3.1 (you cannot use numpy.linalg.qr or similar function).
Next, for both sections, using the Q and the R matrices, you must solve for the augmented weight vector w using backsubstitution. See Example 23.4 on how backsolve works. You cannot use numpy.linalg.inv in your solution (but it can be used to verify your answer).
After you have computed the weight vector w, you should compute the SSE value for the predictions, and also the R2 statistic, defined as: R2 = TSS−SSE
TSS where TSS is the total scatter of the response variable T S S = ∑n (y −μ )2
