Latent Semantic Indexing

Concepts#

1. 1 Singular Value Decompositionfactorisation $A = USV$ into column-orthonormal $U$, diagonal $S$ and row-orthonormal $V$; truncation gives the best rank-$k$ approximation start here
2. 2 LSI Rankingscores documents with the rank-$k$ approximation $A_k = U_k S_k V_k$ instead of $A$

How it fits together#

Starting point. In the vector space model the term-document matrix $A \in \mathbb{R}^{m \times n}$ ($m$ terms, $n$ documents) scores all documents for a query vector $q \in \mathbb{R}^m$ at once as $q^\top A$. A document only gets a score from the terms it shares with the query.

Factorise, then truncate. The SVD writes $A = USV$ with $U \in \mathbb{R}^{m \times r}$, $S \in \mathbb{R}^{r \times r}$ and $V \in \mathbb{R}^{r \times n}$, where $r$ is the rank of $A$. Some exams write $A = U S V^\top$ instead, so check which convention the task uses. Keeping the $k \le r$ largest singular values gives $A_k = U_k S_k V_k$, the best rank-$k$ approximation of $A$. Each of the $k$ dimensions is a latent concept: $U_k$ maps terms to concepts, $S_k V_k$ maps documents to concepts.

Ranking. LSI Ranking replaces $A$ by $A_k$. The three ways of computing the scores (approximated matrix $q^\top A_k$, query in concept space, document expansion $q^\top U_k U_k^\top A$) give the same scores, because $A_k = U_k U_k^\top A$. They differ in what is precomputed and in cost. $A_k$ is dense even if $A$ is sparse, so the factors are stored instead of $A_k$.

The linear algebra the exams test.

• Rank: $r$ is the number of linearly independent rows (or columns) of $A$, hence the number of nonzero singular values and the largest useful $k$. Typical tasks: argue the rank of a small matrix, change few entries to lower or raise it.
• Orthonormality: $U^\top U = I_r$ and $V V^\top = I_r$, but $U U^\top$ and $V^\top V$ are in general not identity matrices (only when $r = m$ resp. $r = n$).
• Recovering a factor: from $A = USV$ and $U^\top U = I_r$ follows $U^\top A = SV$, hence $V = S^{-1} U^\top A$; the singular values follow from $A A^\top = U S^2 U^\top$.
• Dimension check for every NumPy expression: $(1 \times m)(m \times k)(k \times k)(k \times n) = 1 \times n$, one score per document.

Choosing $k$. Small $k$ merges more terms into one concept (more recall for synonyms, less precision). $k = r$ gives back $A$ and plain vector-space ranking.

Key Formulas#

• SVD: $A = USV$, $U^\top U = I_r$, $VV^\top = I_r$ (Singular Value Decomposition)
• Rank-$k$ approximation: $A_k = U_k S_k V_k = U_k U_k^\top A$ (Singular Value Decomposition)
• LSI scores: $q^\top A_k$ (LSI Ranking)
• Recovering $V$: $V = S^{-1} U^\top A$

Exercises & Exam Questions#

Exam occurrences#

Lectures#

• Not lectured in WS 25/26. The material comes from the past exams of the predecessor course Information Retrieval (see the course CLAUDE.md).

Related Topics#

• Inverted Index and Ranking — the vector space model and term-document matrix that LSI approximates