PCA: Explained Variance Ratio via Eigendecompositionhard

PCA: Explained Variance Ratio via Eigendecomposition

hard Classical ML from Scratch 20–25 min

NumPy allowed · plain Python earns 10 bonus points

Implement the real quantity behind every PCA "scree plot" and "how many components do I need to keep 95% of the variance?" decision -- computed from first principles via covariance-matrix eigendecomposition, the same route sklearn's PCA takes internally for dense data.

Task

Implement pca_explained_variance_ratio(X, k): mean-center X, form its (d x d) covariance matrix, eigendecompose it with np.linalg.eigh, sort eigenvalues descending, and return the top-k eigenvalues divided by the sum of all eigenvalues.

Function Signature

pca_explained_variance_ratio(X: list[list[float]], k: int) -> list[float]

Examples

Example 1: Perfectly Collinear Data
Input: X = [[1, 2], [3, 4], [5, 6], [7, 8]]
k = 2
Output: [1, 0]
Explanation: All 4 points lie exactly on a line -- 100% of variance is along one direction

Example 2: Classic 2D PCA Textbook Dataset
Input: X = [[2.5, 2.4],
     [0.5, 0.7],
     [2.2, 2.9],
     [1.9, 2.2],
     [3.1, 3],
     [2.3, 2.7],
     [2, 1.6],
     [1, 1.1],
     [1.5, 1.6],
     [1.1, 0.9]]
k = 1
Output: [0.9631813143]
Explanation: The first principal component alone captures ~96.3% of the variance in this well-known example

Constraints

NumPy is recommended for eigendecomposition (np.linalg.eigh, since the covariance matrix is always symmetric); every test case here is 2D, so a pure-Python closed-form 2x2 eigenvalue solution also works and earns the bonus.
Use the sample covariance (divide by n-1, matching np.cov's default and pandas/sklearn convention).
Deliberately returns variance RATIOS, not the transformed data -- this sidesteps eigenvector sign ambiguity (eigenvectors are only unique up to a sign flip) entirely, since eigenvalues carry no sign ambiguity.

Python3Saved ✓

import numpy as np

def pca_explained_variance_ratio(X: list[list[float]], k: int) -> list[float]:

"""X: list of feature rows. k: number of top principal components.

Center X (subtract each column's mean), compute its covariance

matrix, eigendecompose it, and return the top-k eigenvalues each

divided by the sum of ALL eigenvalues -- the fraction of total

variance each of the top-k principal components explains, sorted

descending."""

# Your implementation here

pass

Case 1: Perfectly Collinear Data

Input: X = [[1, 2], [3, 4], [5, 6], [7, 8]]
k = 2

Expected: [1, 0]

Case 2: Classic 2D PCA Textbook Dataset

Input: X = [[2.5, 2.4],
     [0.5, 0.7],
     [2.2, 2.9],
     [1.9, 2.2],
     [3.1, 3],
     [2.3, 2.7],
     [2, 1.6],
     [1, 1.1],
     [1.5, 1.6],
     [1.1, 0.9]]
k = 1

Expected: [0.9631813143]