Bird
Raised Fist0

Implement PCA - Covariance Matrix, Eigenvectors, Projection

CODINGadvancedInterview freq: high
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🤖
Implement PCA - Covariance Matrix, Eigenvectors, Projection
Implement PCA from scratch using covariance matrix and eigenvectors.
codingadvancedFreq: highClassical ML Coding
Prerequisites:Dimensionality Reduction - PCA, t-SNE, UMAP
📝
Problem Statement

Implement Principal Component Analysis (PCA) using the covariance matrix and eigenvectors. Given a dataset X, reduce its dimensionality to k dimensions.

I/O Specification
Input:  numpy.ndarray X of shape (n_samples, n_features), int k
Output: numpy.ndarray of shape (n_samples, k)
Example
{
  "input": "X = np.array([[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, 1.6], [1, 1.1], [1.5, 1.6], [1.1, 0.9]]), k = 1",
  "expected_output": "array([[ 0.82797019], [-1.77758033], [ 0.99219749], [ 0.27421042], [ 1.67580142], [ 0.9129491 ], [ 0.09910944], [-1.14457216], [-0.43804614], [-1.22382056]])"
}
🎯
Interview Angles
  • Testing understanding of PCA and its mathematical foundation.
  • Evaluating ability to optimize algorithms using linear algebra techniques like SVD.
  • Assessing knowledge of numerical stability and computational efficiency in high-dimensional data.
🔵
Naive Approach

Compute the covariance matrix of the dataset, find its eigenvectors and eigenvalues, and project the data onto the top k eigenvectors.

Time: O(n^2 * d + d^3) - O(n^2 * d) for covariance matrix, O(d^3) for eigen decomposition. Space: O(d^2) for covariance matrix.
Why Insufficient
O(d^3) eigen decomposition is computationally expensive for high-dimensional data, making it impractical for large d.
🐍
Naive Code
Python
import numpy as np

def pca_naive(X, k):
    # Center the data
    X_centered = X - np.mean(X, axis=0)
    # Compute the covariance matrix
    covariance_matrix = np.cov(X_centered, rowvar=False)
    # Compute eigenvalues and eigenvectors
    eigenvalues, eigenvectors = np.linalg.eigh(covariance_matrix)
    # Sort eigenvectors by eigenvalues in descending order
    sorted_indices = np.argsort(eigenvalues)[::-1]
    top_k_eigenvectors = eigenvectors[:, sorted_indices[:k]]
    # Project the data onto the top k eigenvectors
    X_reduced = np.dot(X_centered, top_k_eigenvectors)
    return X_reduced

# Driver example
X = np.array([[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, 1.6], [1, 1.1], [1.5, 1.6], [1.1, 0.9]])
k = 1
print(pca_naive(X, k))
💡
Key Insight
Use Singular Value Decomposition (SVD) to avoid explicitly computing the covariance matrix, reducing the complexity of eigen decomposition.
🐍
Optimized Code
Python
import numpy as np

def pca_optimized(X, k):
    # Center the data
    X_centered = X - np.mean(X, axis=0)
    # Perform SVD
    U, S, Vt = np.linalg.svd(X_centered, full_matrices=False)
    # Select the top k components
    X_reduced = np.dot(U[:, :k], np.diag(S[:k]))
    return X_reduced

# Driver example
X = np.array([[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, 1.6], [1, 1.1], [1.5, 1.6], [1.1, 0.9]])
k = 1
print(pca_optimized(X, k))
🔍
Line-by-Line
X_centered = X - np.mean(X, axis=0)
Center the data by subtracting the mean of each feature to ensure the PCA is performed on zero-centered data.
U, S, Vt = np.linalg.svd(X_centered, full_matrices=False)
Perform SVD on the centered data to obtain the singular values and vectors, which are used for dimensionality reduction.
X_reduced = np.dot(U[:, :k], np.diag(S[:k]))
Project the data onto the top k singular vectors, effectively reducing its dimensionality.
np.linalg.svd(X_centered, full_matrices=False)
Use SVD to decompose the matrix without computing the covariance matrix, which is more efficient for high-dimensional data.
np.dot(U[:, :k], np.diag(S[:k]))
Multiply the top k left singular vectors by the top k singular values to get the reduced representation.
⚡
Complexity
Time: O(n * d^2) - SVD is more efficient than eigen decomposition for large n. Space: O(n * d) for storing the centered data and SVD components.
Output
array([[ 0.82797019], [-1.77758033], [ 0.99219749], [ 0.27421042], [ 1.67580142], [ 0.9129491 ], [ 0.09910944], [-1.14457216], [-0.43804614], [-1.22382056]])
🔲
Edge Cases
Empty dataset
Returns an empty array since there's no data to reduce.
X_centered = X - np.mean(X, axis=0)
Single feature
Returns the centered data since there's only one dimension to reduce.
np.linalg.svd(X_centered, full_matrices=False)
⚠️
Common Mistakes
Not centering the data before applying PCA.
Symptom: The principal components are incorrect, leading to inaccurate dimensionality reduction.
Incorrectly sorting eigenvectors by eigenvalues.
Symptom: The reduced data does not capture the maximum variance.
Using full_matrices=True in SVD unnecessarily.
Symptom: Increased computational cost and memory usage without benefit.

Practice

(1/5)
1. 
import numpy as np

# Forward pass for a single neuron
inputs = np.array([1.0, 2.0, 3.0])
weights = np.array([0.2, 0.8, -0.5])
bias = 2.0

output = np.dot(inputs, weights) + bias
print(output)
easy
A. 2.8
B. 2.0
C. 3.0
D. 2.3

Solution

  1. Step 1: Calculate dot product

    np.dot(inputs, weights) = 1.0*0.2 + 2.0*0.8 + 3.0*(-0.5) = 0.2 + 1.6 - 1.5 = 0.3

  2. Step 2: Add bias

    0.3 + 2.0 = 2.3

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Dot product then add bias [OK]
Hint: Dot product then add bias [OK]
Common Mistakes:
2. What is the time complexity of the following non-max suppression implementation? 
def non_max_suppression(boxes, scores, iou_threshold):
    indices = np.argsort(scores)[::-1]
    keep = []
    while len(indices) > 0:
        current = indices[0]
        keep.append(current)
        indices = indices[1:]
        indices = [i for i in indices if iou(boxes[current], boxes[i]) < iou_threshold]
    return keep
easy
A. O(n^3)
B. O(n^2)
C. O(n)
D. O(n log n)

Solution

  1. Step 1: Analyze the loop structure

    The outer loop runs n times, and the inner loop (IoU calculation) also runs n times in the worst case.

  2. Step 2: Determine complexity

    Each IoU calculation is O(1), making the overall complexity O(n^2).

  3. Final Answer:

    Option B -> Option B

  4. Quick Check:

    Nested loops suggest O(n^2) [OK]
Hint: Nested loops suggest O(n^2) [OK]
Common Mistakes:
3. What is the time complexity of calculating the mean Average Precision (mAP) for a single image with N predicted bounding boxes and M ground truth boxes?
easy
A. O(N + M)
B. O(N^2)
C. O(N * M)
D. O(M^2)

Solution

  1. Step 1: Understand the Process

    For each predicted box, IoU is calculated with each ground truth box, leading to N * M comparisons.

  2. Step 2: Determine Complexity

    Each comparison is constant time, so the overall complexity is O(N * M).

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    IoU comparisons drive complexity [OK]
Hint: IoU comparisons drive complexity [OK]
Common Mistakes:
4. What does the following Python code snippet output when implementing sinusoidal positional encoding?
import numpy as np

def positional_encoding(position, d_model):
    angle_rads = np.arange(position)[:, np.newaxis] / np.power(10000, (2 * (np.arange(d_model)[np.newaxis, :] // 2)) / np.float32(d_model))
    angle_rads[:, 0::2] = np.sin(angle_rads[:, 0::2])
    angle_rads[:, 1::2] = np.cos(angle_rads[:, 1::2])
    return angle_rads

pe = positional_encoding(4, 4)
print(pe)
easy
A. A 4x4 matrix with alternating sine and cosine values
B. A 4x4 matrix with random values
C. A 4x4 identity matrix
D. A 4x4 matrix with all zeros

Solution

  1. Step 1: Understand the code logic

    The code generates a matrix where each row corresponds to a position and each column to a dimension, filled with sinusoidal values.

  2. Step 2: Eliminate wrong options

    A 4x4 matrix with all zeros is incorrect because the matrix is not filled with zeros. A 4x4 identity matrix is incorrect because the matrix is not an identity matrix. A 4x4 matrix with random values is incorrect because the values are not random but deterministic sinusoidal values.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Sinusoidal encoding alternates sine/cosine. [OK]
Hint: Sinusoidal encoding alternates sine/cosine. [OK]
Common Mistakes:
5. In a Random Forest implementation, how would you apply feature sampling to handle high-dimensional data effectively?
medium
A. Use all features for each tree to ensure accuracy
B. Use a fixed subset of features for all trees
C. Randomly select a small subset of features for each tree
D. Select features based on their correlation with the target

Solution

  1. Step 1: Understand Feature Sampling

    Feature sampling involves selecting a random subset of features for each tree to reduce dimensionality.

  2. Step 2: Evaluate Options

    Using all features (A) or a fixed subset (C) doesn't reduce dimensionality; correlation-based selection (D) isn't random.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Random subsets reduce dimensionality [OK]
Hint: Random subsets reduce dimensionality [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard