Word Embedding Similarity and Low-Rank Approximation

The problem in brief

You take a short English text (three paragraphs about a seaside town), split it into lowercase tokens, and look up each distinct token in the pretrained GloVe embeddings, where every word is a vector of 100 numbers. After normalising the vectors you build the matrix $S$ of all pairwise cosine similarities, use it to find each word's closest neighbour, and then study $S$ with linear algebra: is it invertible, how does its eigen-decomposition relate to the SVD of the embedding matrix, what is its Frobenius norm, and how well can it be approximated with far fewer numbers. Fifteen short parts mix explanation, NumPy one-liners and proofs, with strict rules (no loops, no @, no np.linalg except for the SVD).

How you are scored

90 points over 15 parts (5 or 10 each). Code parts are checked by running them; "reasoning required" parts need a proof. Here is a summary of our answers, all checked by solution.py:

part	answer
5.1	225 occurrences, then 158 distinct tokens
5.5	$\text{sim}_{ij} \in [-1, 1]$
5.6	$S = WW^\top$
5.8	all diagonal entries equal 1 (up to float32 rounding, within $4\times10^{-7}$)
5.9	sim_dict["bright"] == "lights" reproduced
5.10	not invertible: $\operatorname{rank} S \le 100 < N = 158$
5.12	$Q = U$, $\lambda = (\sigma_1^2, \dots, \sigma_{100}^2, 0, \dots, 0)$
5.13	$\lVert S\rVert_F = \sqrt{\sum_i \sigma_i^4} \approx 60.80$
5.14	$W_r = U_r\Sigma_r$, $S_r = W_rW_r^\top$, error $\sum_{i>r}\sigma_i^4 / \sum_i \sigma_i^4$

First look at the data

The text has 225 tokens, all of which happen to be in GloVe's 400 000-word vocabulary, and 158 distinct ones. It was clearly written with groups of near-synonyms (walk, stroll, wander; happy, cheerful, pleased; tired, weary), so nearest neighbours should be meaningful. One surprise appears as soon as $S$ is drawn: 98 % of the off-diagonal similarities are positive (mean 0.34, minimum only $-0.20$, for "conversation" and "seabirds"). GloVe vectors are not spread evenly around the origin; they share a common direction. This will explain why the low-rank approximation works so well.

Question by question

5.1 and 5.2: the two lengths and set

The first print(len(tokens)) counts every occurrence of every token that GloVe knows (225, repeated words such as "the" or "and" counted each time). tokens = list(set(tokens)) then builds a set, which keeps one copy of each distinct token, and converts it back to a list: 158 tokens. That is the answer to 5.2 too, with one caveat worth stating: a set has no order, so the order of the resulting list is arbitrary (it can change between Python runs). Our script sorts the list afterwards so that row $n$ of every matrix always refers to the same word.

5.3 and 5.4: the matrices

vectors_arr = np.array(vectors)                                        # (N, 100)
W = vectors_arr / np.sqrt((vectors_arr ** 2).sum(axis=1, keepdims=True))

keepdims=True makes the norms a column of shape $(N, 1)$, so broadcasting divides each row by its own norm.

5.5: the range

$\text{sim}_{ij} = \hat v^{(i)\top}\hat v^{(j)}$ is the cosine of the angle between two unit vectors. By Cauchy-Schwarz, $\lvert \hat v^{(i)\top}\hat v^{(j)}\rvert \le \lVert\hat v^{(i)}\rVert\,\lVert\hat v^{(j)}\rVert = 1$, so $\text{sim}_{ij} \in [-1, 1]$: 1 for the same direction, $-1$ for opposite directions, 0 for orthogonal ones.

5.6 and 5.7: $S$ from $W$

Entry $(i, j)$ of $WW^\top$ is row $i$ of $W$ dotted with row $j$ of $W$, which is exactly $\text{sim}_{ij}$. So $S = WW^\top$. Without @:

S = np.einsum("ik,jk->ij", W, W)        # or: S = np.dot(W, W.T)

5.8: the diagonal

print(np.diag(S)) shows values all equal to 1 (in float32 they range from 0.9999996 to 1.0000002). Interpretation: $\text{sim}_{ii} = \lVert\hat v^{(i)}\rVert^2 = 1$, every word is perfectly similar to itself. This is a sanity check on the normalisation, and also a warning for the next part: the most similar token to any word is always itself.

5.9: nearest neighbours

So we mask the diagonal before taking the row-wise maximum:

S_off = S.copy()
np.fill_diagonal(S_off, -np.inf)
sim_dict = dict(zip(tokens, [tokens[j] for j in S_off.argmax(axis=1)]))

We get "bright": "lights" as the statement promises, and the neighbours are convincingly semantic: happy $\to$ pleased (0.74), walk $\to$ stroll, tired $\to$ weary, talked $\to$ spoke, night $\to$ evening (0.84), bread $\to$ baked, boats $\to$ fishermen. Note the last two: embeddings capture words that occur in the same contexts, not only synonyms.

5.10: is $S$ invertible?

No. $S = WW^\top$ with $W \in \mathbb{R}^{N \times 100}$. Every column of $S$ is $W$ times a vector, so it lies in the column space of $W$, which has dimension at most 100. Hence

$$\operatorname{rank} S \le \operatorname{rank} W \le 100 < 158 = N .$$

An $N \times N$ matrix of rank less than $N$ is singular. Concretely, there is a nonzero $z \in \mathbb{R}^N$ with $W^\top z = 0$ (the $100 \times N$ system $W^\top z = 0$ has more unknowns than equations), and then $Sz = W(W^\top z) = 0$. In general: a Gram matrix of $N$ vectors in $\mathbb{R}^d$ can be invertible only if $N \le d$.

5.11 and 5.12: SVD of $W$ and spectral decomposition of $S$

U, sigma, Vt = np.linalg.svd(W, full_matrices=True)    # U: N x N, sigma sorted decreasing
V = Vt.T

Substituting $W = U\Sigma V^\top$:

$$S = WW^\top = U\Sigma V^\top V \Sigma^\top U^\top = U\,(\Sigma\Sigma^\top)\,U^\top ,$$

since $V^\top V = I$. $U$ is orthonormal and $\Sigma\Sigma^\top$ is an $N\times N$ diagonal matrix with entries $\sigma_1^2 \ge \dots \ge \sigma_{100}^2$ followed by $N - 100 = 58$ zeros. This is a spectral decomposition, already sorted in decreasing order:

Q = U
lam = np.concatenate([sigma ** 2, np.zeros(N - len(sigma))])

full_matrices=True matters: with the economy SVD, $U$ would be only $N \times 100$ and not a square orthonormal $Q$. (The 58 zero eigenvalues are another proof of 5.10.)

5.13: the Frobenius norm

The Frobenius norm satisfies $\lVert M\rVert_F^2 = \operatorname{tr}(M^\top M)$, and it is unchanged by orthonormal factors. Using 5.12 and the cyclic property of the trace:

$$\lVert S\rVert_F^2 = \operatorname{tr}(S^\top S) = \operatorname{tr}(Q\Lambda Q^\top Q\Lambda Q^\top) = \operatorname{tr}(Q\Lambda^2 Q^\top) = \operatorname{tr}(\Lambda^2 Q^\top Q) = \sum_i \lambda_i^2 = \sum_{i=1}^{100}\sigma_i^4 .$$

So $\lVert S\rVert_F = \sqrt{\sum_i \sigma_i^4}$. Numerically both sides give 60.8046. A bonus identity: $\operatorname{tr} S = \sum_i \sigma_i^2 = N$, because the diagonal of $S$ is all ones; indeed $\sum_i\sigma_i^2 = 158.000$.

5.14: the best approximation with $rN$ numbers

Keep the $r$ largest singular directions:

$$W_r = U_r\Sigma_r \in \mathbb{R}^{N\times r} \quad(\text{first } r \text{ columns of } U, \text{ scaled by } \sigma_1,\dots,\sigma_r), \qquad S_r = W_rW_r^\top = \sum_{i=1}^{r}\sigma_i^2\, u_iu_i^\top .$$

By the same trace argument, $S - S_r = \sum_{i>r}\sigma_i^2 u_iu_i^\top$ and

$$\frac{\lVert S - S_r\rVert_F^2}{\lVert S\rVert_F^2} = \frac{\sum_{i>r}\sigma_i^4}{\sum_{i}\sigma_i^4} .$$

Why this is the minimum: any $S_r = W_rW_r^\top$ has rank at most $r$, and by the Eckart-Young theorem the closest rank-$r$ matrix to $S$ in Frobenius norm is obtained by keeping its $r$ largest eigen-components, which is exactly our $S_r$. Note that $W_r$ is not "the first $r$ coordinates of the embeddings": that naive choice (renormalised) gives a relative error of 7.3 at $r = 1$ and still 0.32 at $r = 50$, against 0.088 and 0.0006 for the SVD.

5.15: the plot

The key idea

A similarity matrix is a Gram matrix, so everything about it is governed by the SVD of the data matrix. $S = WW^\top$ immediately gives its rank (at most 100, hence singular), its eigenvectors (the left singular vectors of $W$), its eigenvalues ($\sigma_i^2$), its norm ($\sqrt{\sum\sigma_i^4}$) and its best compressions (truncate the SVD).

The plot also tells a story about GloVe. A single rank-one term already captures 91 % of $\lVert S\rVert_F^2$. That first direction is almost exactly the average word vector (cosine 0.997 between the top right-singular vector and the mean of the rows of $W$): all words share a common component, which is why nearly all similarities are positive. This "anisotropy" is common in embeddings, and subtracting the mean vector before computing similarities is a standard fix when one wants the remaining, more semantic directions to dominate. Because the error is measured with fourth powers of $\sigma_i$, this one dominant eigenvalue weighs enormously; reaching 1 % error needs $r = 17$ and 5 % needs $r = 4$.

The full solution

solution.py follows the starter code (only its imports), sorts the token list for reproducibility, and checks every claim with an assertion: $S\in[-1,1]$, $Q\Lambda Q^\top = S$ and $Q^\top Q = I$, the Frobenius identity, and the error formula of 5.14 against direct computation of $\lVert S - S_r\rVert_F^2$ for several $r$. The plotting part of 5.15 is:

err = [(sigma[r:] ** 4).sum() / (sigma ** 4).sum() for r in range(1, 101)]
plt.plot(range(1, 101), err); plt.xlabel("r"); plt.ylabel("relative squared Frobenius error")

Results

check	value
tokens / distinct tokens	225 / 158
diagonal of $S$ (float32)	1 within $4\times10^{-7}$
sim_dict["bright"]	"lights"
$\operatorname{rank} W$	100, so $S$ ($158\times158$) is singular
$\lVert S\rVert_F$ vs $\sqrt{\sum\sigma_i^4}$	60.8046 vs 60.8046
relative error, best rank 1 / 5 / 10 / 20 / 50	0.088 / 0.037 / 0.019 / 0.0073 / 0.0006
same with naive "first $r$ coordinates"	7.29 / 1.86 / 0.99 / 0.61 / 0.32
smallest $r$ for error $\le$ 5 % / 1 %	4 / 17

What to remember

• Cosine similarity of normalised rows is one matrix product: $S = WW^\top$; mask the diagonal before searching for nearest neighbours.
• A Gram matrix of $N$ vectors in $\mathbb{R}^d$ has rank at most $d$, so it is singular whenever $N > d$.
• The SVD of $W$ hands you the eigen-decomposition of $WW^\top$: same left vectors, squared singular values (and use full_matrices=True if you need a square $Q$).
• Frobenius norms and low-rank errors are sums over singular values, and truncating the SVD is optimal (Eckart-Young); cutting coordinates is not.
• Look at the spectrum: one huge eigenvalue means a shared component (here, the mean word vector), which inflates all similarities.