Sparse SVD (svds) in SciPy - Time & Space Complexity

Time Complexity: Sparse SVD (svds)

O(k * nnz)

Understanding Time Complexity

We want to understand how the time to compute sparse singular value decomposition grows as the input matrix size increases.

How does the computation cost change when we have bigger sparse matrices?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from scipy.sparse.linalg import svds
import scipy.sparse as sp

# Create a large sparse matrix
A = sp.random(10000, 10000, density=0.001, format='csr')

# Compute 6 largest singular values and vectors
u, s, vt = svds(A, k=6)
    

This code creates a large sparse matrix and computes a few singular values and vectors using svds.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Iterative matrix-vector multiplications inside svds.
• How many times: The number of iterations depends on convergence, often proportional to k (number of singular values) and matrix sparsity.

How Execution Grows With Input

As the matrix size grows, the number of operations grows roughly in proportion to the number of non-zero elements times the number of iterations.

Input Size (n x n)	Approx. Operations
10 x 10	Few hundred operations
100 x 100	Thousands of operations
1000 x 1000	Hundreds of thousands of operations

Pattern observation: The cost grows roughly linearly with the number of non-zero elements, which grows with matrix size and density.

Final Time Complexity

Time Complexity: O(k * nnz)

This means the time grows roughly with the number of singular values requested times the number of non-zero elements in the matrix.

Common Mistake

[X] Wrong: "The time complexity depends only on the matrix size n, not on how many values k we ask for or how sparse the matrix is."

[OK] Correct: The algorithm uses iterative multiplications that depend on k and the number of non-zero elements, so sparsity and k directly affect the time.

Interview Connect

Understanding how sparse matrix operations scale helps you explain performance in real data science tasks involving large datasets and dimensionality reduction.

Self-Check

"What if we increase k to request more singular values? How would the time complexity change?"