PCA via Covariance Matrix
Implement Principal Component Analysis from scratch.
Given a 2D dataset, perform PCA to reduce dimensionality to k components:
- Center the data (subtract column means)
- Compute the covariance matrix: C=n−11​XcT​Xc​
- Compute eigenvalues and eigenvectors of C
- Select top k eigenvectors (by eigenvalue magnitude)
- Project the centered data onto these eigenvectors
Return the projected data (n x k matrix), rounded to 4 decimal places.
Note: For simplicity, this problem works with 2D data (2 features → 1 component).
Example:
X = [[2.5, 2.4], [0.5, 0.7], [2.2, 2.9], [1.9, 2.2], [3.1, 3.0], [2.3, 2.7], [2.0, 1.6], [1.0, 1.1], [1.5, 1.6], [1.1, 0.9]] k = 1
[[-0.8280], [1.7776], [-0.9922], [-0.2742], [-1.6758], [-0.9129], [0.0991], [1.1446], [0.4380], [1.2238]]
- First, we center the data by subtracting the column means: μ1​=1.75, μ2​=2.03, resulting in a centered dataset Xc​.
- Then, we compute the covariance matrix C=n−11​XcT​Xc​, where n is the number of data points.
- Next, we calculate the eigenvalues and eigenvectors of C, and select the top k=1 eigenvector corresponding to the largest eigenvalue.
- Finally, we project the centered data Xc​ onto this eigenvector, resulting in the projected data, which is then rounded to 4 decimal places to produce the output: [[-0.8280], [1.7776], [-0.9922], [-0.2742], [-1.6758], [-0.9129], [0.0991], [1.1446], [0.4380], [1.2238]]
Constraints:
- X: 2D list (n x 2) — two features
- k: 1 (project to 1 dimension)
- Return 2D list (n x 1) of projected values, rounded to 4 decimal places
- Use sample covariance (divide by n-1)
Background Knowledge
Principal Component Analysis (PCA) is a widely used technique in dimensionality reduction for high-dimensional data. The primary goal of PCA is to identify the principal components, which are the directions of maximum variance in the data. By selecting the top k principal components, we can reduce the dimensionality of the data from n features to k features, where k<n. This reduction helps to simplify the data, reduce noise, and improve model performance.
The covariance matrix plays a crucial role in PCA. It measures the covariance between each pair of features in the data. The covariance matrix is computed as C=n−11​XcT​Xc​, where Xc​ is the centered data (i.e., the data with the column means subtracted). The eigenvalues and eigenvectors of the covariance matrix are then computed. The eigenvectors represent the directions of maximum variance in the data, and the eigenvalues represent the amount of variance explained by each eigenvector.
In the context of PCA, the eigenvectors are also known as the principal components. By selecting the top k eigenvectors (i.e., the eigenvectors corresponding to the k largest eigenvalues), we can project the centered data onto these eigenvectors to obtain the reduced-dimensional data. This projection is a linear transformation that maps the original high-dimensional data to a lower-dimensional space.
Algorithm/Approach
The general approach to solving this problem involves the following steps:
- Center the data by subtracting the column means
- Compute the covariance matrix
- Compute the eigenvalues and eigenvectors of the covariance matrix
- Select the top k eigenvectors
- Project the centered data onto these eigenvectors
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.