Singular value decomposition (svd) in MATLAB - Time & Space Complexity

Time Complexity: Singular value decomposition (svd)

O(n^3)

Understanding Time Complexity

We want to understand how the time needed to perform singular value decomposition (SVD) changes as the size of the matrix grows.

Specifically, how does the work increase when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following MATLAB code snippet.

A = rand(n, n);  % Create an n-by-n random matrix
[U, S, V] = svd(A);
    

This code computes the singular value decomposition of a square matrix A of size n-by-n.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The algorithm repeatedly performs matrix multiplications and transformations on the n-by-n matrix.
• How many times: These operations happen multiple times, roughly proportional to the size of the matrix cubed.

How Execution Grows With Input

As the matrix size n grows, the number of operations grows quickly because the algorithm works on all rows and columns together.

Input Size (n)	Approx. Operations
10	About 1,000
100	About 1,000,000
1000	About 1,000,000,000

Pattern observation: When n increases ten times, the work increases about a thousand times, showing a cubic growth pattern.

Final Time Complexity

Time Complexity: O(n^3)

This means the time needed grows roughly with the cube of the matrix size, so doubling the size makes the work about eight times bigger.

Common Mistake

[X] Wrong: "SVD runs in linear time because it just processes each element once."

[OK] Correct: SVD involves complex matrix operations that combine rows and columns many times, so it takes much more work than just touching each element once.

Interview Connect

Understanding how SVD scales helps you explain performance when working with large data or images, showing you know how algorithms behave with bigger inputs.

Self-Check

"What if the matrix A was not square but rectangular with size m-by-n? How would the time complexity change?"

Practice

1. What does the MATLAB function svd(A) return when applied to a matrix A?

easy

A. The determinant of matrix A.

B. The inverse of matrix A.

C. Three matrices: U, S, and V such that A = U * S * V'.

D. The transpose of matrix A.

Solution

1. Step 1: Understand the purpose of svd

   The svd function decomposes a matrix into three parts: U, S, and V.

2. Step 2: Recall the decomposition formula

   It satisfies the equation A = U * S * V', where U and V are orthogonal matrices and S is diagonal.

3. Final Answer:

   Three matrices: U, S, and V such that A = U * S * V'. -> Option C

4. Quick Check:

   svd(A) = U, S, V [OK]

Hint: Remember svd splits matrix into U, S, V parts [OK]

Common Mistakes:

• Confusing svd with inverse or transpose
• Expecting a single matrix output
• Thinking svd returns determinant

2. Which of the following is the correct MATLAB syntax to compute the singular value decomposition of matrix A and store the results in U, S, and V?

easy

A. [U, S, V] = svd(A);

B. svd(U, S, V) = A;

C. U, S, V = svd(A);

D. svd(A, U, S, V);

Solution

1. Step 1: Recall MATLAB function output syntax

   In MATLAB, multiple outputs are assigned using square brackets on the left side.

2. Step 2: Match correct svd syntax

   The correct syntax is [U, S, V] = svd(A); to get all three matrices.

3. Final Answer:

   [U, S, V] = svd(A); -> Option A

4. Quick Check:

   Use square brackets for multiple outputs [OK]

Hint: Use square brackets for multiple outputs in MATLAB [OK]

Common Mistakes:

• Using parentheses instead of brackets for outputs
• Trying to assign outputs on the right side
• Incorrect argument order in svd

3. Given the MATLAB code:

A = [3 1; 1 3];
[U, S, V] = svd(A);
disp(diag(S));

What will be the output of disp(diag(S))?

medium

A. [0; 0]

B. [3; 1]

C. [1; 3]

D. [4; 2]

Solution

1. Step 1: Calculate singular values of A

   Matrix A is symmetric. Its singular values are the absolute values of eigenvalues. Eigenvalues of A are 4 and 2.

2. Step 2: Understand svd output

   The diagonal of S contains singular values in descending order: 4 and 2.

3. Final Answer:

   [4; 2] -> Option D

4. Quick Check:

   Singular values = eigenvalues for symmetric matrix [OK]

Hint: For symmetric matrices, singular values = absolute eigenvalues [OK]

Common Mistakes:

• Confusing singular values with matrix entries
• Mixing order of singular values
• Expecting singular values to be zero

4. Consider the MATLAB code snippet:

A = [1 2; 3 4];
[U, S, V] = svd(A);
U = svd(A);

What is the error in this code?

medium

A. Matrix A is not square, so svd cannot be applied.

B. The second call to svd assigns a matrix to U instead of three outputs.

C. The variable V is not assigned in the second svd call.

D. The svd function requires four output variables.

Solution

1. Step 1: Analyze the first svd call

   The first call correctly assigns three outputs: U, S, V.

2. Step 2: Analyze the second svd call

   The second call assigns U = svd(A); which returns only singular values as a vector, not a matrix U.

3. Final Answer:

   The second call to svd assigns a matrix to U instead of three outputs. -> Option B

4. Quick Check:

   svd(A) alone returns singular values vector [OK]

Hint: svd(A) alone returns singular values vector, not matrices [OK]

Common Mistakes:

• Expecting svd(A) to return U matrix alone
• Thinking svd requires square matrix only
• Ignoring number of outputs in function call

5. You want to approximate a matrix A by keeping only the largest singular value and corresponding vectors using MATLAB. Which code snippet correctly performs this low-rank approximation?

hard

A. [U, S, V] = svd(A);A_approx = U(:,1) * S(1,1) * V(:,1)';

B. [U, S, V] = svd(A);A_approx = U(:,1) * V(:,1)';

C. [U, S, V] = svd(A);A_approx = S(1,1) * V(:,1)';

D. [U, S, V] = svd(A);A_approx = U(:,1) * S(:,1) * V(:,1)';

Solution

1. Step 1: Understand low-rank approximation using svd

   Keeping only the largest singular value means using the first column of U, the first singular value, and the first column of V.

2. Step 2: Construct the approximation

   The approximation is A_approx = U(:,1) * S(1,1) * V(:,1)', multiplying the first singular value and vectors.

3. Final Answer:

   [U, S, V] = svd(A); A_approx = U(:,1) * S(1,1) * V(:,1)'; -> Option A

4. Quick Check:

   Low-rank approx = U(:,1)*S(1,1)*V(:,1)' [OK]

Hint: Multiply first U column, singular value, and V column for approximation [OK]

Common Mistakes:

• Omitting singular value in multiplication
• Using entire S matrix instead of first singular value
• Incorrect matrix dimensions in multiplication