#!/usr/bin/env python3
# Source: q1-ml-fundamentals.html
import numpy as np

def pca(X, k):
    """PCA by SVD. Returns projected data, components, and explained variance ratio."""
    Xc = X - X.mean(axis=0)                       # centering is required
    U, S, Vt = np.linalg.svd(Xc, full_matrices=False)
    var = S**2 / (len(X) - 1)                     # eigenvalues of the covariance
    components = Vt[:k]                           # rows are principal directions
    Z = Xc @ components.T                         # same as U[:, :k] * S[:k]
    return Z, components, var[:k] / var.sum()
