PCA Projection
PCA Projection
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.
Algorithm
-
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.
Examples
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).
Hint 1
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).
Hint 2
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.
Requirements
- Center the data by subtracting the column means
- Compute the covariance matrix using n-1 (sample covariance)
- Find the top-k eigenvectors ordered by decreasing eigenvalue
- Project the centered data onto these k eigenvectors
- Return an n x k list of floats
Constraints
- X has at least 2 rows and k <= d (number of features)
- The top-k eigenvalues are distinct (no ties)
- Return an n x k list of floats
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: number
PCA Projection
PCA Projection
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.
Algorithm
-
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.
Examples
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).
Hint 1
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).
Hint 2
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.
Requirements
- Center the data by subtracting the column means
- Compute the covariance matrix using n-1 (sample covariance)
- Find the top-k eigenvectors ordered by decreasing eigenvalue
- Project the centered data onto these k eigenvectors
- Return an n x k list of floats
Constraints
- X has at least 2 rows and k <= d (number of features)
- The top-k eigenvalues are distinct (no ties)
- Return an n x k list of floats
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: number