Principal Component Analysis (PCA) in MATLAB - Time & Space Complexity

Time Complexity: Principal Component Analysis (PCA)

O(n d^2 + d^3)

Understanding Time Complexity

We want to understand how the time needed to run PCA changes as the data size grows.

How does the work increase when we add more data points or features?

Scenario Under Consideration

Analyze the time complexity of the following PCA code snippet.

% X is data matrix with n samples and d features
X_centered = X - mean(X);
C = (X_centered' * X_centered) / (size(X,1) - 1);
[V, D] = eig(C);
[~, idx] = sort(diag(D), 'descend');
V = V(:, idx);

% Project data onto first k principal components
Y = X_centered * V(:, 1:k);
    

This code centers the data, computes the covariance matrix, finds eigenvectors and eigenvalues, sorts them, and projects data onto the top components.

Identify Repeating Operations

Look at the parts that repeat work based on input size.

• Primary operation: Multiplying matrices to get covariance (X_centered' * X_centered) and eigen decomposition.
• How many times: Matrix multiplication does about d * d * n steps; eigen decomposition works on d x d matrix.

How Execution Grows With Input

As we add more samples (n) or features (d), the work changes differently.

Input Size (n, d)	Approx. Operations
n=10, d=5	Small matrix multiply and eigen on 5x5 matrix
n=100, d=50	Matrix multiply ~50*50*100 = 250,000 steps; eigen decomposition on 50x50 matrix
n=1000, d=200	Matrix multiply ~200*200*1000 = 40,000,000 steps; eigen decomposition on 200x200 matrix

Pattern observation: Work grows linearly with number of samples n but grows faster with number of features d, especially for eigen decomposition.

Final Time Complexity

Time Complexity: O(n d^2 + d^3)

This means the time grows mostly by multiplying the number of samples by the square of features, plus the cube of features for eigen calculations.

Common Mistake

[X] Wrong: "The time depends only on the number of samples n, not on features d."

[OK] Correct: The number of features affects matrix sizes and eigen decomposition, which can be much more costly than just handling samples.

Interview Connect

Understanding how PCA scales helps you explain performance in data analysis tasks and shows you can think about algorithm costs clearly.

Self-Check

"What if we used Singular Value Decomposition (SVD) directly on X instead of covariance matrix? How would the time complexity change?"

Practice

1.

What is the main purpose of Principal Component Analysis (PCA) in MATLAB?

easy

A. To reduce the number of variables by finding main directions of data

B. To sort data in ascending order

C. To calculate the sum of all data points

D. To generate random numbers for data simulation

Solution

1. Step 1: Understand PCA goal

   PCA finds new axes (principal components) that capture most data variation.

2. Step 2: Identify main purpose

   It reduces data dimensions by focusing on important directions, simplifying analysis.

3. Final Answer:

   To reduce the number of variables by finding main directions of data -> Option A

4. Quick Check:

   PCA = Dimensionality reduction [OK]

Hint: PCA simplifies data by finding main directions [OK]

Common Mistakes:

• Thinking PCA sorts data
• Confusing PCA with summing data
• Assuming PCA generates random data

2.

Which MATLAB command correctly performs PCA on a data matrix X?

easy

A. score = pca(X, 'score');

B. pca = X.coeff();

C. [coeff, score, latent] = pca(X);

D. coeff = pca(X, 'coeff');

Solution

1. Step 1: Recall MATLAB PCA syntax

   The function pca returns coefficients, scores, and variances as outputs.

2. Step 2: Match correct syntax

   Only [coeff, score, latent] = pca(X); correctly calls PCA and stores outputs.

3. Final Answer:

   [coeff, score, latent] = pca(X); -> Option C

4. Quick Check:

   Correct PCA syntax = [coeff, score, latent] = pca(X); [OK]

Hint: Use brackets to capture multiple PCA outputs [OK]

Common Mistakes:

• Using dot notation on matrix
• Passing output names as strings
• Assigning only one output without brackets

3.

Given the MATLAB code below, what is the size of score if X is a 100x5 matrix?

 [coeff, score, latent] = pca(X); 

medium

A. 5x5

B. 100x5

C. 100x100

D. 5x100

Solution

1. Step 1: Understand PCA output sizes

   score contains transformed data points in principal component space, same rows as X.

2. Step 2: Match dimensions

   Since X is 100x5, score is 100x5 (100 samples, 5 components).

3. Final Answer:

   100x5 -> Option B

4. Quick Check:

   score size = samples x components = 100x5 [OK]

Hint: Score matches rows of X and number of components [OK]

Common Mistakes:

• Confusing score size with coeff size
• Assuming score is square matrix
• Swapping rows and columns

4.

Identify the error in this MATLAB PCA code snippet:

 X = rand(50,3);
 [coeff, score, latent] = pca(X);
 disp(score(1,4)); 

medium

A. Indexing score at column 4 causes an error

B. Missing semicolon after rand function

C. Incorrect function name, should be pca_analysis

D. Matrix X size is invalid for PCA

Solution

1. Step 1: Check size of PCA outputs

   Input X has 3 columns, so score has 3 columns (components).

2. Step 2: Identify indexing error

   Accessing score(1,4) tries to get 4th column which does not exist, causing an error.

3. Final Answer:

   Indexing score at column 4 causes an error -> Option A

4. Quick Check:

   score columns = 3, index 4 invalid [OK]

Hint: Check matrix size before indexing columns [OK]

Common Mistakes:

• Assuming more components than input columns
• Ignoring MATLAB indexing errors
• Thinking semicolon omission causes error here

5.

You want to reduce a dataset X (200x10) to 2 principal components using MATLAB PCA. Which code correctly achieves this?

 % Options:
 A) [coeff, score] = pca(X, 'NumComponents', 2);
 B) [coeff, score] = pca(X, 'NumComponents', 2); score = score(:,3:4);
 C) [coeff, score] = pca(X); score = score(:,11:12);
 D) [coeff, score] = pca(X, 'Components', 2); 

hard

A. [coeff, score] = pca(X, 'Components', 2);

B. [coeff, score] = pca(X, 'NumComponents', 2); score = score(:,3:4);

C. [coeff, score] = pca(X); score = score(:,11:12);

D. [coeff, score] = pca(X, 'NumComponents', 2);

Solution

1. Step 1: Understand PCA dimension reduction parameter

   MATLAB's pca accepts 'NumComponents' to limit output components.

2. Step 2: Identify correct usage

   [coeff, score] = pca(X, 'NumComponents', 2); uses correct parameter 'NumComponents', 2 to get 2 components directly.

3. Step 3: Check other options

   B: [coeff, score] = pca(X, 'NumComponents', 2); score = score(:,3:4); tries to slice non-existent columns 3-4; C: [coeff, score] = pca(X); score = score(:,11:12); tries to slice non-existent columns 11-12; D: [coeff, score] = pca(X, 'Components', 2); uses invalid parameter.

4. Final Answer:

   [coeff, score] = pca(X, 'NumComponents', 2); -> Option D

5. Quick Check:

   Use 'NumComponents' to limit PCA output [OK]

Hint: Use 'NumComponents' to get desired PCA components [OK]

Common Mistakes:

• Using wrong parameter name 'Components'
• Using invalid slice indices on PCA score
• Assuming PCA auto-limits components without parameter