Principal Component Analysis

Implement PCA from the covariance matrix.

1. Centre X by subtracting the column means.
2. Build the covariance matrix C = X_centered^T @ X_centered / (n - 1).
3. Take its eigenvectors and sort them by descending eigenvalue.
4. Keep the top n_components and project the centred data onto them.

C is symmetric, so use np.linalg.eigh rather than eig. It returns real eigenvalues in ascending order, so you have to reverse them.

Eigenvectors are only defined up to sign, and eigh may hand you either direction. To make the result deterministic, flip each component so that its largest-magnitude entry is positive.

Return (components, projected) with shapes (n_components, d) and (n, n_components). Each row of components is one unit-length eigenvector.

Function signature

def pca(X, n_components):

Example

Input

X = np.array([[1.0, 1.0], [2.0, 2.0], [3.0, 3.0]])
pca(X, 1)

Output

(array([[0.70710678, 0.70710678]]), array([[-1.41421356],
       [ 0.        ],
       [ 1.41421356]]))

Reasoning

All points lie on the line y = x, so the first component is [1, 1] / sqrt(2). The centred points are (-1, -1), (0, 0) and (1, 1), which project to -sqrt(2), 0 and sqrt(2).

Constraints and notes

• Use np.linalg.eigh and reverse its order.
• Flip each component so its largest magnitude entry is positive.
• Shapes are (n_components, d) and (n, n_components).