Principal Component Analysis (PCA) finds the directions of maximum variance in the data and projects it onto a lower-dimensional subspace. This is done by computing the eigenvectors of the covariance matrix and projecting onto the top-k eigenvectors (principal components).
Given a data matrix X (n samples, d features) and the number of components k, project the data onto its top-k principal components.
Center the data by subtracting the mean of each feature
Compute the d x d covariance matrix using sample covariance (divide by n-1)
Find the top-k eigenvectors of C sorted by eigenvalue in descending order (e.g., using power iteration with deflation)
Project the centered data onto these eigenvectors
Where W is the d x k matrix whose columns are the top-k eigenvectors.
Input:
X = [[1, 0], [2, 0], [3, 0], [4, 0], [5, 0]], k = 1
Output:
[[-2.0], [-1.0], [0.0], [1.0], [2.0]]
All variance is in the first dimension. After centering (mean = [3, 0]), the principal component is [1, 0]. Projecting gives the centered first coordinates.
Input:
X = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]], k = 1
Output:
[[-2.83], [-1.41], [0.0], [1.41], [2.83]]
The data lies along the line y = x. The principal component is [1/sqrt(2), 1/sqrt(2)]. Projecting the centered data onto this direction gives the values above (approximately).
For centering: means = [sum(X[i][j] for i in range(n))/n for j in range(d)]. For covariance: C = X_c^T @ X_c / (n-1). For eigenvectors: use power iteration (multiply by C, normalize, repeat until convergence).
After finding each eigenvector, deflate the matrix: C = C - eigenvalue * outer(v, v). Then repeat power iteration for the next component. Finally, project: result = X_centered @ W where W columns are eigenvectors.
Sign in to take notes on this problem
Accepts: array
Accepts: number
Principal Component Analysis (PCA) finds the directions of maximum variance in the data and projects it onto a lower-dimensional subspace. This is done by computing the eigenvectors of the covariance matrix and projecting onto the top-k eigenvectors (principal components).
Given a data matrix X (n samples, d features) and the number of components k, project the data onto its top-k principal components.
Center the data by subtracting the mean of each feature
Compute the d x d covariance matrix using sample covariance (divide by n-1)
Find the top-k eigenvectors of C sorted by eigenvalue in descending order (e.g., using power iteration with deflation)
Project the centered data onto these eigenvectors
Where W is the d x k matrix whose columns are the top-k eigenvectors.
Input:
X = [[1, 0], [2, 0], [3, 0], [4, 0], [5, 0]], k = 1
Output:
[[-2.0], [-1.0], [0.0], [1.0], [2.0]]
All variance is in the first dimension. After centering (mean = [3, 0]), the principal component is [1, 0]. Projecting gives the centered first coordinates.
Input:
X = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]], k = 1
Output:
[[-2.83], [-1.41], [0.0], [1.41], [2.83]]
The data lies along the line y = x. The principal component is [1/sqrt(2), 1/sqrt(2)]. Projecting the centered data onto this direction gives the values above (approximately).
For centering: means = [sum(X[i][j] for i in range(n))/n for j in range(d)]. For covariance: C = X_c^T @ X_c / (n-1). For eigenvectors: use power iteration (multiply by C, normalize, repeat until convergence).
After finding each eigenvector, deflate the matrix: C = C - eigenvalue * outer(v, v). Then repeat power iteration for the next component. Finally, project: result = X_centered @ W where W columns are eigenvectors.
Sign in to take notes on this problem
Accepts: array
Accepts: number