PCA, kernel PCA and ICA

The slides' examples of "big and high-dimensional" data:

• Documents: one feature per word (thousands) or per word pair (millions).
• Netflix ratings: a 480,189 users × 17,770 movies matrix. Just loading it into memory is a problem.
• MEG brain imaging: 120 sensor locations × 500 time points × 20 subjects, with strong dependence between neighboring locations and times.
• Images: a 100 × 100 color image is already numbers.

In each case the features are highly redundant, so a much smaller set of numbers could describe each example almost as well. Learning that smaller representation helps with (slide 5):

Look at a 2-D cloud that is long in one direction and thin in the other. Both original coordinates vary, so you seem to need both. But if you rotate your axes to line up with the cloud, almost all the spread is along one new axis. Describing each point by its position along that axis loses very little. Slide 7 puts it this way: the data is "intrinsically lower dimensional than the dimension of the ambient space".

PCA formalizes this. It is an orthogonal projection of the data onto a (possibly lower-dimensional) subspace chosen so that the variance of the projected data is as large as possible (slide 6).

• The first principal component (PC1) is the direction of greatest variance.
• The second (PC2) is the direction of greatest remaining variance, at a right angle to PC1.
• And so on: in dimensions you get at most mutually orthogonal PCs (21:50).

Slide 7 also notes that PCA follows rotations: rotate the data and the PCs rotate with it, so the same single coordinate stays important. That's because PCA is a purely linear operation (07:00). In 3-D, the same idea finds the plane a cloud lies near and projects onto it (slide 8, 09:21).

Setup. We have data points . The slides stack them as columns of a matrix .

Step 0: center the data. Subtract the sample mean from every point. From now on means the centered point, so .

Step 1: projecting onto a direction. Take a unit vector (). The scalar projection of onto is , the point's coordinate along . The projected point itself, back in , is .

Step 2: the objective. Because the data is centered, the projections have mean 0, so their variance is the mean of their squares:

Step 3: Lagrange multiplier. Fold the constraint into the objective with a multiplier and set the gradient to zero:

So the best direction must be an eigenvector of . Which one? Multiply both sides by :

The variance captured along an eigenvector is its eigenvalue. To maximize it, take the eigenvector with the largest eigenvalue. That's PC1. Slide 12 calls the eigenvalue "the amount of energy along that dimension".

The iterative definition (slide 10). After finding PC1 , remove it from every point. The residual is what's left after subtracting the projection:

PC2 is the unit vector that maximizes the variance of the residuals, . Then take residuals again and repeat for PC3, and so on. The professor points out that doing this one direction at a time is slow (15:02).

The one-shot answer (slide 12). You don't actually need the loop. Do one eigendecomposition of , sort the eigenvalues , and the matching eigenvectors are PC1, PC2, …, PC in order. Because is symmetric, its eigenvectors are automatically orthogonal, which is exactly the constraint the iterative definition imposes.

Projecting. Put the first PCs as columns of a matrix . Each point's new coordinates are

Slide 13 sums up the geometry: PCA is centering followed by a rotation (and, if you drop components, a projection). Two facts follow:

• The new features are uncorrelated. The covariance of the 's is : zero off the diagonal.
• Total variance is preserved by the full rotation: = the sum of the original features' variances.

Slide 28 ("What you should know") lists both viewpoints, so know both and why they agree.

• Maximum variance: choose to maximize .
• Minimum reconstruction error: choose so that replacing each point by its projection loses as little as possible:

Why they're the same: Pythagoras (slide 16). The residual is perpendicular to , so the point, its projection and its residual form a right triangle:

Average over all points: the left side is a constant (the total variance), so more projected variance means exactly that much less reconstruction error. The figure below sweeps every direction for the worked example's data.

With components the same argument gives a useful formula: the mean squared reconstruction error equals the sum of the discarded eigenvalues, .

The lecture never runs PCA on actual numbers, so here's a complete one. Data: four points in 2-D,

1. Center. The mean is , . Subtracting it gives , , , .
2. Covariance (with , as on the slides). Sums over the centered points: , , . Divide by :
3. Eigenvalues. Solve : So , . Check: they sum to the trace .
4. Eigenvectors. For : the first row of says , so . Normalize: , about , at 18.4° from the -axis. PC2 is perpendicular: .
5. Project onto PC1. , which is on the centered coordinates: , , , . Their mean square is . ✓
6. Reconstruct. gives , , , . Squared errors: , , , ; mean . ✓
7. Explained variance ratio. PC1 keeps of the variance; PC2 holds the other .

Each row obeys Pythagoras (‖x‖² = z² + residual²), and the bottom row is the whole story of Section 5: 12 = 11 + 1.

Reduce. Keep the top PCs and represent each point by : numbers instead of . If some eigenvalues are exactly 0, keeping the nonzero ones loses nothing at all (slide 17). In practice noise makes every eigenvalue slightly positive, so we drop the small ones and accept a small loss (slide 18).

Reconstruct (decompress). Map back with the transpose and add the mean (Géron Eq. 8-3):

Choose k. Each PC's explained variance ratio is its eigenvalue over the total, and the cumulative version adds them up:

The cumulative curve always increases and ends at 1. The rule from the lecture (23:06): pick a threshold such as 90% or 95% of the "energy", draw a horizontal line there, and keep the smallest where the curve crosses it. The threshold is your choice; 99% is fine too, it just keeps more components.

Géron's version of the same rule: np.argmax(np.cumsum(pca.explained_variance_ratio_) >= 0.95) + 1, or simply PCA(n_components=0.95). On MNIST, 95% of the variance needs about 154 of 784 dimensions, under 20% of the original size, and the decompressed digits still look right. Other ways to pick : look for an elbow where the curve flattens, use or 3 for plots, or treat as a hyperparameter and cross-validate the downstream model.

Eigenfaces (slide 19). Flatten each face image into one long vector (one entry per pixel), stack thousands of them, and run PCA. Each PC is itself a vector of pixel values, so it can be displayed as an image: a ghostly "eigenface". With 15 PCs learned from 7,562 images, every face is approximately the mean face plus a weighted sum of the 15 eigenfaces, so it can be stored and compared as just 15 numbers instead of thousands of pixels. (The slide says "linear combination of the rest"; the reconstruction formula above adds the mean face too.)

Before clustering (slide 20). Run PCA first, then k-means (week 9) on the reduced data. The slide's experiments report a k-means cost increase under 5% with a 10× to 100× speedup.

The two weaknesses on the slide motivate the last two methods of the lecture: kernel PCA removes the linearity limit, and ICA goes beyond second-order statistics.

Eigendecomposition (slide 31). Any symmetric matrix, such as , factors as

SVD (slides 32–33). You can skip forming and factor the data matrix directly. With as (columns are points), the slides write

Comparing with : the eigenvalues of are (and the covariance's are ). The rows of are each point's coordinates along the PCs (slide 33). This is how scikit-learn computes PCA (Géron: U, s, Vt = np.linalg.svd(X_centered)), because it's numerically more accurate than forming .

Power method (slide 30). When is huge and you only need the top one or two PCs, iterate:

Each multiplication stretches the component by and the others by smaller factors, so after normalizing, swings toward ; the leftover error shrinks roughly by per step. Computing costs per iteration without ever forming the matrix, which is why the lecture calls it linear-cost (39:32). Slide 30's claim: after iterations, with high probability . For the next PC, subtract each point's component (the residuals of Section 4) and repeat.

(Worked example, , : the angle shrinks about elevenfold per step.)

At scale (Géron). Randomized PCA (svd_solver="randomized") approximates the top PCs much faster than a full SVD when . Incremental PCA (IncrementalPCA with partial_fit) processes mini-batches, for datasets that don't fit in memory, which was the Netflix-matrix worry from the start of the lecture.

Linear PCA can only rotate and project. If the data lies near a curve or a curved surface, no flat subspace fits it well. Kernel PCA borrows week 5's idea: map each point into a high-dimensional feature space with , run ordinary PCA there, and use a kernel so you never compute explicitly (slide 22).

The problem: PCA as written uses the matrix , which isn't made of dot products between points. The kernel trick needs the matrix of dot products, (slide 24). The derivation (slides 25–26) rewrites PCA so only appears.

1. The PC lies in the span of the data. Any component of perpendicular to all data points contributes nothing to the variance but uses up length, so the best is a combination of the points: This is the same move as the SVM dual's (30:14).
2. Substitute into :
3. Left-multiply by : Now the data appears only through the inner-product matrix , whose entry is .
4. Swap in a kernel. Replace by with , and cancel one from both sides: So kernel PCA is an eigendecomposition of the kernel matrix.
5. Project a point (slide 27). Its coordinate along this kernel PC is which needs only kernel evaluations against the training points.