Concept - Singular Value Decomposition (SVD)

Definition

Factorization of the document-term matrix: $C=U\Sigma V^T$ (s.183, s.192).

Factor	Meaning on the slides	Slide
$U$	representation of documents (docs x topics)	s.181
$\Sigma$	diagonal; each singular value = importance of its semantic dimension	s.181, s.186
$V^T$	representation of terms (topics x terms)	s.181

• $U\Sigma$ = final (dense) representation of documents (s.182).
• $V$ = projection matrix: $CV=U\Sigma$ (s.183). A new sparse doc vector times $V$ gives a dense topic vector (s.184).
• Example singular values: 2.162501, 1.594382, 1.27529, 1.0, 0.393915 (s.181).

Intuition

Each topic = linear combination of words. Keeping all dimensions only rotates/rescales the space (doc4 vs doc5 cosine stays ~0, s.182); the benefit comes from truncation (Concept - Truncated SVD).

Related

Concept - Latent Semantic Analysis (LSA) | Concept - Truncated SVD | Concept - Synonymy and Semantic Relatedness (Eckart-Young, s.191)

Source: 02 Pre-processing - Chunk 07 (s.181-193)

From chunk 06 (s.177-180)

• Introduced as the way to find the projection matrix by matrix decomposition (“Latent Semantic Analysis: SVD”, s.177).
• General definition (s.178): $A_{[m\times n]}=U_{[m\times r]}{\Sigma }_{[r\times r]}(V_{[n\times r]}{)}^T$, $A\approx {\sum }_i{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$. $U$ = left singular vectors (docs x concepts), $\Sigma$ = singular values (diagonal, strength of each concept), $V$ = right singular vectors (terms x concepts), $r$ = rank.
• Properties (s.178): always possible for a real matrix; $U,\Sigma ,V$ unique; $U,V$ column-orthonormal ($U^{T}U=I$, $V^{T}V=I$); $\Sigma$ diagonal, positive, sorted decreasing ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$.
• Users-to-movies example (s.179): 7 users x 5 movies (Matrix, Alien, Serenity, Casablanca, Amelie); $\Sigma =\mathrm{diag}(12.4,9.5,1.3)$; first concept = SciFi (strength 12.4), second = Romance. $U$ = user-to-concept, $V$ = movie-to-concept similarity matrix.
• Reduced SVD (s.180): $C=U\Sigma V^T$ with $C$: $n\times m$, $U$: $n\times r$, $\Sigma$: $r\times r$, $V^T$: $r\times m$, $r$ = rank (usually $\min (m,n)$), $U^{T}U=V^{T}V=I^{r\times r}$.
• Note: s.178 uses $m$ docs x $n$ terms, s.180 uses $n$ docs x $m$ terms.

Source: 02 Pre-processing - Chunk 06 (s.151-180)