Singular Value Decomposition › SVD Computational Complexity

Computing the full SVD of an $m \times n$ matrix takes $O(mn \cdot \min(m, n))$ time. For a vocabulary of $V$ words, a word-word co-occurrence matrix is $V \times V$, making the full SVD $O(V^3)$ in time. A vocabulary of 100,000 words would require on the order of $10^{15}$ operations: completely infeasible with any current hardware.

The memory requirement for storing the full dense co-occurrence matrix is $V^2$ entries. At 100,000 words and 4 bytes per float, that is already 40 gigabytes. Larger vocabularies (500,000 words, as in some production systems) would require 1 terabyte just to store the matrix in dense form. These numbers make clear that full SVD on large NLP matrices is not just slow: it is impossible without specialized techniques.

Several strategies address this, and understanding them clarifies why LSA became computationally practical:

Sparse matrix storage: Co-occurrence matrices are extremely sparse. Even with a window of 5 words, most word pairs never co-occur in any reasonable corpus. The fraction of nonzero entries in a PPMI matrix for a 100,000-word vocabulary on a billion-word corpus is typically well below 1%. Sparse formats like compressed sparse row (CSR) store only the nonzero entries, reducing memory by 100x or more compared to dense storage.

Truncated SVD via Lanczos iteration: When you only need the top $k$ singular vectors rather than all of them, specialized algorithms exploit the structure of the problem. The Lanczos algorithm builds a sequence of orthogonal vectors that progressively refine estimates of the top singular vectors. Starting from a random vector, it applies the matrix repeatedly and uses Gram-Schmidt orthogonalization to build a Krylov subspace, a subspace that converges rapidly to the dominant singular directions. The algorithm requires only matrix-vector products with $\mathbf{M}$ and $\mathbf{M}^T$, which can be done efficiently for sparse matrices without ever constructing a dense representation. The computational cost is roughly $O(k \cdot \text{nnz})$, where nnz is the number of nonzero entries.

Vocabulary truncation: Only retaining the top $V'$ most frequent words dramatically reduces the matrix size. Words that appear very rarely (fewer than 5-10 times in the corpus) contribute mostly noise to the SVD and can safely be excluded. Keeping the top 30,000-50,000 vocabulary items is common in practice, which reduces the matrix from $V^2$ to $(V')^2$ entries, a reduction of 4-16x relative to a 100,000-word vocabulary.

PPMI matrix factorization via co-occurrence streaming: Rather than forming the full dense PPMI matrix and then applying SVD, some implementations stream through the corpus to accumulate only the co-occurrences needed, building the sparse PPMI matrix incrementally without ever materializing it fully in memory.