Which matrix represents the similarity between words when using SVD?

Two words can be similar if they co-occur "a lot" together. They can also be similar if they have similar vectors. This similarity can be captured using cosine similarity. Let $$A$$ be a $$n \times n$$ matrix counting how often $$w_i$$ occurs with $$w_k$$ for $$i,k = 1, \dots, n$$. Since computing the cosine similarity between $$w_i$$ and $$w_k$$ might be expensive, we approximate $$A$$ using truncated SVD with $$k$$ components as: $$A \approx W_k \Sigma W^{T}_{k} = CD$$

where $$C = W_{k} \Sigma \\ D = W^{T}_{k}$$

Where are the cosine similarities between the words $$w_i$$ and $$w_k$$ captured? In the $$C$$ matrix or the $$D$$ matrix?

• Where did you read this formulation? Edit your question to add these details. – nbro Mar 15 at 18:03

You can find some material here and here but the idea (at least in this case) is the following: consider the full SVD decomposition of the symmetric matrix $$A = W \Delta W^T$$. We want to calculate the cosine similarity between the $$i$$-th column (aka word) $$a_i$$ and the $$j$$-th column $$a_j$$ of $$A$$. Then $$a_k = A e_k$$, where $$e_k$$ is the $$k$$-th vector of the canonical basis of $$\mathbb{R}$$. Let's call $$\cos(a_i,a_j)$$ the cosine between $$a_i,a_j$$. Then $$\cos(a_i,a_j) = \cos(Ae_i,Ae_j) = \cos(W \Delta W^T e_i,W \Delta W^T e_j) = \cos(\Delta W^T e_i,\Delta W^T e_j)$$
where the last equality holds because $$W$$ is an orthogonal matrix (and so $$W$$ is conformal). So you can calculate the cosine similarity between the columns of $$\Delta W^T$$. A $$k$$-truncated SVD gives a well-enough approximation. In general, columns of $$W \Delta$$ and rows of $$W$$ have different meanings!
• But isn't $W^T$ also orthogonal and therefore conformal? If yes, why can't we simply use the diagonal matrix? – nbro Mar 16 at 13:41
• Also $W^T$ is orthogonal and conformal, but you only "simplify" on the left: if $f$ is a conformal map, $g$ any function, then $\cos(f \circ g(x),f \circ g(y)) = \cos(g(x),g(y))$, but in general $\cos(g \circ f(x),g \circ f(y)) \neq \cos(g(x),g(y))$ – dcolazin Mar 16 at 13:48
• @nbro for example, consider this matrix: $\cos(Me_1,Me_3) = 1 = \cos(\Sigma V^T e_1, \Sigma V^T e_3)$ but $\cos(\Sigma e_1,\Sigma e_3) = 0$ (cosine between different columns in a diagonal matrix is always $0$). – dcolazin Mar 16 at 13:57