Recitation 5

Reduction in details

Bohan Jiang

2026-10-02

Where we left off

Last week: a word is its row of PPMI weights over contexts. Two rows:

cupbrewmorningshotfoamroastscreen⋯espresso01.9202.2702.300⋯cappuccino1.5701.5103.3200⋯ \small \begin{array}{r|cccccccc} & \text{cup} & \text{brew} & \text{morning} & \text{shot} & \text{foam} & \text{roast} & \text{screen} & \cdots \\ \hline \text{espresso} & 0 & \color{#b22222}{1.92} & 0 & \color{#b22222}{2.27} & 0 & \color{#b22222}{2.30} & 0 & \cdots \\ \text{cappuccino} & \color{#1f3a93}{1.57} & 0 & \color{#1f3a93}{1.51} & 0 & \color{#1f3a93}{3.32} & 0 & 0 & \cdots \end{array}

The rest of each row is all zeros, and the two rows have no nonzero column in common. Three problems:

  • Blind: no shared context ⇒\Rightarrow cosine =0= 0, even for near-synonyms
  • Isolated: every context is its own axis, so car and automobile never meet
  • Huge: ∣C∣≈50,000|C| \approx 50{,}000 dimensions, but models want ≈300\approx 300

Question: why go low-dimensional?

  • On the PPMI rows, cos⁡(espresso,cappuccino)=0\cos(\text{espresso}, \text{cappuccino}) = 0. Does the data say they differ, or does it say nothing?
  • Why would fewer dimensions fix this? (Not just “it’s smaller.”)

Rotating can’t change angles

Goal: a new representation where espresso and cappuccino have a smaller angle.

Cheapest try: keep all ∣C∣|C| dimensions and just switch to a new orthonormal basis QQ (a rotation):

(Q⊤a)⋅(Q⊤b)=a⊤QQ⊤b=a⋅b (Q^\top \mathbf{a}) \cdot (Q^\top \mathbf{b}) = \mathbf{a}^\top Q Q^\top \mathbf{b} = \mathbf{a} \cdot \mathbf{b}

  • Every dot product and every length stays the same ⇒\Rightarrow every cosine stays the same. Still 0.
  • So keeping every dimension can’t help. To change angles, we have to throw some directions away.
  • Two questions: does throwing away really bring vectors closer, and which directions should go?

A toy matrix in 2-D

Toy PPMI rows over two contexts:

brewcupcoffee11espresso10cappuccino01 \begin{array}{r|cc} & \text{brew} & \text{cup} \\ \hline \text{coffee} & 1 & 1 \\ \text{espresso} & 1 & 0 \\ \text{cappuccino} & 0 & 1 \end{array}

Each row is a vector in the (brew, cup) plane.

espresso ⊥\perp cappuccino ⇒\Rightarrow cos⁡=0\cos = 0

From 2-D to 1-D

  • In 1-D, each word keeps a single number twt_w.
  • To compare it with the original vector, turn twt_w back into a point: fix a unit direction u\mathbf{u} and use twut_w \mathbf{u}.
  • All points t ut\,\mathbf{u} form a line through the origin, with tt as the scaler.
  • So choosing a 1-D space = choosing a line u\mathbf{u}.

What is the loss?

If word ww’s vector vw\mathbf{v}_w lands at t ut\,\mathbf{u} on the line, its loss is the squared distance between them:

lossw(t)=∥vw−t u∥2 \text{loss}_w(t) = \|\mathbf{v}_w - t\,\mathbf{u}\|^2

Espresso (1,0)(1, 0) on the diagonal, for example:

  • at (0.5,0.5)(0.5, 0.5):   0.52+0.52=0.5\;0.5^2 + 0.5^2 = 0.5
  • at (1,1)(1, 1):   02+12=1\;0^2 + 1^2 = 1

Smallest at (0.5,0.5)(0.5, 0.5), where the drop is perpendicular to the line. Coincidence?

Minimize the loss ⇒\Rightarrow land perpendicular

Expand the loss, using ∥u∥=1\|\mathbf{u}\| = 1:

lossw(t)=(vw−tu)⋅(vw−tu)=∥vw∥2−2t (vw⋅u)+t2 \text{loss}_w(t) = (\mathbf{v}_w - t\mathbf{u}) \cdot (\mathbf{v}_w - t\mathbf{u}) = \|\mathbf{v}_w\|^2 - 2t\,(\mathbf{v}_w \cdot \mathbf{u}) + t^2

  • Set the derivative to 0:   −2(vw⋅u)+2t=0  ⇒  t∗=vw⋅u\;-2(\mathbf{v}_w \cdot \mathbf{u}) + 2t = 0 \;\Rightarrow\; \boxed{t^* = \mathbf{v}_w \cdot \mathbf{u}}
  • At t∗t^*, the drop is perpendicular: (vw−t∗u)⋅u=vw⋅u−t∗=0(\mathbf{v}_w - t^*\mathbf{u}) \cdot \mathbf{u} = \mathbf{v}_w \cdot \mathbf{u} - t^* = 0. Not a coincidence.
  • Espresso: t∗=(1,0)⋅(1,1)2=12t^* = (1, 0) \cdot \tfrac{(1, 1)}{\sqrt{2}} = \tfrac{1}{\sqrt{2}}, landing at t∗u=(0.5,0.5)t^*\mathbf{u} = (0.5, 0.5) ✓
  • Plug t∗t^* back in: the smallest loss is ∥vw∥2−(vw⋅u)2\|\mathbf{v}_w\|^2 - (\mathbf{v}_w \cdot \mathbf{u})^2, so ∥vw∥2=(vw⋅u)2⏟kept+lossw(t∗)⏟lost \|\mathbf{v}_w\|^2 = \underbrace{(\mathbf{v}_w \cdot \mathbf{u})^2}_{\text{kept}} + \underbrace{\text{loss}_w(t^*)}_{\text{lost}}

Compare two lines

Each word lands at its perpendicular point (×), t∗=vw⋅ut^* = \mathbf{v}_w \cdot \mathbf{u}. Two candidate lines:

Dashed = what the line loses. Different lines, different answers: which one should we pick?

Which line? Lose the least

Landing perpendicularly splits each word’s squared length into kept (shadow) and lost (dashed):

∥vw∥2=(vw⋅u)2⏟kept+(dashed length)2⏟lost \|\mathbf{v}_w\|^2 = \underbrace{(\mathbf{v}_w \cdot \mathbf{u})^2}_{\text{kept}} + \underbrace{(\text{dashed length})^2}_{\text{lost}}

The total is fixed (2+1+1=42 + 1 + 1 = 4), so keep the most = lose the least.

line coffee espresso cappuccino kept lost
brew axis 1 1 0 2 2
diagonal 2 1/2 1/2 3 1
  • Each cell is a word’s kept part, (vw⋅u)2(\mathbf{v}_w \cdot \mathbf{u})^2.
  • The rule never looks at espresso vs. cappuccino. The diagonal wins because coffee, the longest point (2\sqrt{2}), lies on it.

Project and compare

Project every row onto the diagonal u=(1,1)/2\mathbf{u} = (1, 1)/\sqrt{2}:

coffee↦2,espresso↦12,cappuccino↦12 \text{coffee} \mapsto \sqrt{2}, \qquad \text{espresso} \mapsto \tfrac{1}{\sqrt{2}}, \qquad \text{cappuccino} \mapsto \tfrac{1}{\sqrt{2}}

  • Same sign on a 1-D line ⇒\Rightarrow cos⁡(espresso,cappuccino)\cos(\text{espresso}, \text{cappuccino}) goes from 0 to 1.
  • The similarity is borrowed from coffee: one word that uses both contexts (exactly lie on the diagonal)

Rotate and drop

Question: what if coffee weren’t there?

  • Drop the coffee row and keep only espresso (1,0)(1, 0) and cappuccino (0,1)(0, 1).
  • Which direction keeps the most now? Do they still become similar?
  • For any unit u\mathbf{u}:   (vesp⋅u)2+(vcap⋅u)2=u12+u22=1\;(\mathbf{v}_\text{esp} \cdot \mathbf{u})^2 + (\mathbf{v}_\text{cap} \cdot \mathbf{u})^2 = u_1^2 + u_2^2 = 1. Every direction ties.

Takeaways

  • Reduction doesn’t invent similarity from nothing. It spreads evidence through shared contexts (here, coffee).
  • Extend to more general case: low-dimensional space that still approximately recovers the low-rank matrix.

Three routes, one destination

Count and factorize
SVD / LSA
Predict
word2vec, SGNS
Count and fit
GloVe

⟹\Longrightarrow

Dense vectors
vw∈Rd\mathbf{v}_w \in \mathbb{R}^d, d≈100–500d \approx 100\text{–}500
  • The three routes come from different communities and different decades
  • They all end up approximating PMI

Factorization (SVD)

What is rank?

A matrix has rank 1 when every row is a multiple of one row: one pattern, rescaled.

(316200)rows=1⋅(3,1),  2⋅(3,1),  0⋅(3,1) \begin{pmatrix} 3 & 1 \\ 6 & 2 \\ 0 & 0 \end{pmatrix} \qquad \text{rows} = 1\cdot(3,1),\; 2\cdot(3,1),\; 0\cdot(3,1)

  • To store it, you only need the pattern (3,1)(3,1) and the scales (1,2,0)(1,2,0)
  • Rank kk = the matrix is a sum of kk such patterns, and no fewer

The outer product builds patterns

uv⊤,(uv⊤)ij=uivj(120)(31)=(316200) \mathbf{u}\mathbf{v}^\top, \qquad (\mathbf{u}\mathbf{v}^\top)_{ij} = u_i v_j \qquad \begin{pmatrix} 1 \\ 2 \\ 0 \end{pmatrix} \begin{pmatrix} 3 & 1 \end{pmatrix} = \begin{pmatrix} 3 & 1 \\ 6 & 2 \\ 0 & 0 \end{pmatrix}

  • v\mathbf{v} = the pattern: what every row looks like
  • u\mathbf{u} = the weights: how much of the pattern each row gets
  • Every rank-1 matrix is an outer product, and every outer product has rank 1
  • Compare with the inner product u⋅v\mathbf{u}\cdot\mathbf{v}: it sums the index away and returns a scalar

Practice

  • What is the rank of A=(1326−1−3)A = \begin{pmatrix} 1 & 3 \\ 2 & 6 \\ -1 & -3 \end{pmatrix}?
  • Write it as uv⊤\mathbf{u}\mathbf{v}^\top.
  • Rank 1. Every row is a multiple of (1,3)(1, 3).
  • u=(1,2,−1)⊤\mathbf{u} = (1, 2, -1)^\top and v⊤=(1,3)\mathbf{v}^\top = (1, 3)
  • Scaling u\mathbf{u} by cc and v\mathbf{v} by 1/c1/c gives the same matrix, so the factorization is not unique.

SVD: the theorem

Every real matrix M∈Rm×nM \in \mathbb{R}^{m \times n} factors as

M=UΣV⊤ M = U \Sigma V^\top

  • UU, VV: orthogonal (their columns are unit length and mutually perpendicular)
  • Σ\Sigma: diagonal, with σ1≥σ2≥⋯≥0\sigma_1 \ge \sigma_2 \ge \dots \ge 0 (the singular values)

Read Mx=U(Σ(V⊤x))M\mathbf{x} = U(\Sigma(V^\top \mathbf{x})) from right to left:

Step What it does
V⊤V^\top rotate the input space to a new basis
Σ\Sigma stretch each new axis by σi\sigma_i
UU rotate into the output space

SVD, geometrically

Apply A=(3045)A = \begin{pmatrix} 3 & 0 \\ 4 & 5 \end{pmatrix} to the unit circle, one factor at a time:

  1. V⊤V^\top: rotate
  2. Σ\Sigma: stretch
  3. UU: rotate

Red/green: v1,v2\mathbf{v}_1, \mathbf{v}_2 end up as the ellipse’s axes σ1u1,σ2u2\sigma_1\mathbf{u}_1, \sigma_2\mathbf{u}_2, with σ1=35≈6.71\sigma_1 = 3\sqrt{5} \approx 6.71 and σ2=5≈2.24\sigma_2 = \sqrt{5} \approx 2.24.

SVD as a sum of rank-1 pieces

Read UΣV⊤U\Sigma V^\top one column at a time:

M=σ1u1v1⊤+σ2u2v2⊤+⋯+σrurvr⊤ M = \sigma_1 \mathbf{u}_1 \mathbf{v}_1^\top + \sigma_2 \mathbf{u}_2 \mathbf{v}_2^\top + \dots + \sigma_r \mathbf{u}_r \mathbf{v}_r^\top

Factor In a word-context matrix
vi\mathbf{v}_i the ii-th pattern over contexts
ui\mathbf{u}_i how much each word uses that pattern
σi\sigma_i how important the pattern is (sorted)

Running SVD on our PPMI matrix

U, s, Vt = np.linalg.svd(M, full_matrices=False)
print("sigma =", s)
print("U =\n", U)
print("Vt =\n", Vt)
sigma = [2.127 2.016 0.292 0.083]
U =
 [[ 0.     0.697 -0.717  0.   ]
 [ 0.     0.717  0.697  0.   ]
 [ 0.681  0.     0.    -0.733]
 [ 0.733  0.     0.     0.681]]
Vt =
 [[ 0.003  0.    -0.     0.696  0.718  0.   ]
 [ 0.     0.604  0.645  0.     0.     0.468]
 [ 0.     0.414  0.247  0.     0.    -0.876]
 [-0.07   0.    -0.    -0.716  0.694  0.   ]]

Pattern 1: “device-ness”

Term ii adds   σi⋅ui[w]⋅vi[c]  \;\sigma_i \cdot u_i[w] \cdot v_i[c]\; to cell (word ww, context cc). Highlighted: σ1\sigma_{1}, column 1 of UU, row 1 of V⊤V^\top.

U (words)
1 2 3 4
coffee 0.00 0.70 −0.72 0.00
tea 0.00 0.72 0.70 0.00
laptop 0.68 0.00 0.00 −0.73
tablet 0.73 0.00 0.00 0.68
σ
   
1 2.13
2 2.02
3 0.29
4 0.08
Vᵀ (contexts)
the cup brew screen battery morning
1 0.00 0.00 0.00 0.70 0.72 0.00
2 0.00 0.60 0.65 0.00 0.00 0.47
3 0.00 0.41 0.25 0.00 0.00 −0.88
4 −0.07 0.00 0.00 −0.72 0.69 0.00
  • Large in u1\mathbf{u}_1: laptop, tablet. Large in v1\mathbf{v}_1: screen, battery ⇒\Rightarrow term 1 fills the device block: a topic.
  • e.g. (laptop, screen):   2.13×0.68×0.70≈1.01\;2.13 \times 0.68 \times 0.70 \approx 1.01 (observed 1.05)

Pattern 2: “beverage-ness”

Term ii adds   σi⋅ui[w]⋅vi[c]  \;\sigma_i \cdot u_i[w] \cdot v_i[c]\; to cell (word ww, context cc). Highlighted: σ2\sigma_{2}, column 2 of UU, row 2 of V⊤V^\top.

U (words)
1 2 3 4
coffee 0.00 0.70 −0.72 0.00
tea 0.00 0.72 0.70 0.00
laptop 0.68 0.00 0.00 −0.73
tablet 0.73 0.00 0.00 0.68
σ
   
1 2.13
2 2.02
3 0.29
4 0.08
Vᵀ (contexts)
the cup brew screen battery morning
1 0.00 0.00 0.00 0.70 0.72 0.00
2 0.00 0.60 0.65 0.00 0.00 0.47
3 0.00 0.41 0.25 0.00 0.00 −0.88
4 −0.07 0.00 0.00 −0.72 0.69 0.00
  • Large in u2\mathbf{u}_2: coffee, tea. Large in v2\mathbf{v}_2: cup, brew, morning ⇒\Rightarrow the beverage block: another topic.
  • e.g. (tea, brew):   2.02×0.72×0.65≈0.93\;2.02 \times 0.72 \times 0.65 \approx 0.93 (observed 0.98)

Pattern 3: coffee vs. tea

Term ii adds   σi⋅ui[w]⋅vi[c]  \;\sigma_i \cdot u_i[w] \cdot v_i[c]\; to cell (word ww, context cc). Highlighted: σ3\sigma_{3}, column 3 of UU, row 3 of V⊤V^\top.

U (words)
1 2 3 4
coffee 0.00 0.70 −0.72 0.00
tea 0.00 0.72 0.70 0.00
laptop 0.68 0.00 0.00 −0.73
tablet 0.73 0.00 0.00 0.68
σ
   
1 2.13
2 2.02
3 0.29
4 0.08
Vᵀ (contexts)
the cup brew screen battery morning
1 0.00 0.00 0.00 0.70 0.72 0.00
2 0.00 0.60 0.65 0.00 0.00 0.47
3 0.00 0.41 0.25 0.00 0.00 −0.88
4 −0.07 0.00 0.00 −0.72 0.69 0.00
  • Mixed signs: coffee −-, tea ++ in u3\mathbf{u}_3; cup ++, morning −- in v3\mathbf{v}_3. The signs multiply:
  • (coffee, morning): (−)(−)⇒+0.18(-)(-) \Rightarrow +0.18.   \; (tea, morning): (+)(−)⇒−0.18(+)(-) \Rightarrow -0.18
  • Not a new topic: a difference inside the beverage topic (coffee goes with morning more than tea does).

Pattern 4: laptop vs. tablet

Term ii adds   σi⋅ui[w]⋅vi[c]  \;\sigma_i \cdot u_i[w] \cdot v_i[c]\; to cell (word ww, context cc). Highlighted: σ4\sigma_{4}, column 4 of UU, row 4 of V⊤V^\top.

U (words)
1 2 3 4
coffee 0.00 0.70 −0.72 0.00
tea 0.00 0.72 0.70 0.00
laptop 0.68 0.00 0.00 −0.73
tablet 0.73 0.00 0.00 0.68
σ
   
1 2.13
2 2.02
3 0.29
4 0.08
Vᵀ (contexts)
the cup brew screen battery morning
1 0.00 0.00 0.00 0.70 0.72 0.00
2 0.00 0.60 0.65 0.00 0.00 0.47
3 0.00 0.41 0.25 0.00 0.00 −0.88
4 −0.07 0.00 0.00 −0.72 0.69 0.00
  • Mixed signs again: laptop −-, tablet ++; screen −-, battery ++ ⇒\Rightarrow a difference inside the device topic.
  • Tiny σ4\sigma_4, tiny effect: (tablet, battery) gets only +0.04+0.04.
  • Large σ\sigma: topics. Small σ\sigma: distinctions within a topic. Nobody supplied these categories; the factorization found them.

Question

  • u3=(−0.72,+0.70,0,0)\mathbf{u}_3 = (-0.72, +0.70, 0, 0) has opposite signs on coffee and tea.
  • What would it mean if u3\mathbf{u}_3 were all non-negative instead?
  • It would be a third topic: another group of words that share a pattern.
  • With opposite signs, it is a difference inside an existing topic.
  • The sign structure of u\mathbf{u} tells you which of the two you are looking at.

How big is a matrix? The Frobenius norm

Flatten the matrix into one long vector and take its length:

∥A∥F=∑i,jaij2 \|A\|_F = \sqrt{\textstyle\sum_{i,j} a_{ij}^2}

  • Each piece has size exactly its singular value: ∥σiuivi⊤∥F=σi\|\sigma_i \mathbf{u}_i\mathbf{v}_i^\top\|_F = \sigma_i
  • The pieces are mutually orthogonal, so squared sizes add.

∥M∥F2=∑iσi2 \|M\|_F^2 = \textstyle\sum_i \sigma_i^2 

print(np.linalg.norm(M), np.sqrt(np.sum(s**2)))
2.946356663184046 2.9463566631840457

Eckart–Young: why truncation is the right tool

Keep only the top kk terms: Mk=UkΣkVk⊤M_k = U_k \Sigma_k V_k^\top

MkM_k is the best rank-kk approximation of MM in Frobenius norm: ∥M−Mk∥F=min⁡rank(X)≤k∥M−X∥F=∑i>kσi2 \|M - M_k\|_F = \min_{\text{rank}(X) \le k} \|M - X\|_F = \sqrt{\textstyle\sum_{i>k} \sigma_i^2}

  • The error is exactly the terms you dropped.

Practice

A matrix MM has singular values σ=(6,3,2,1)\sigma = (6, 3, 2, 1).

  1. What is ∥M∥F\|M\|_F?
  2. What is the relative error ∥M−Mk∥F/∥M∥F\|M - M_k\|_F / \|M\|_F at k=1k = 1 and k=2k = 2?
  3. What is the smallest kk that keeps at least 90% of ∑σi2\sum \sigma_i^2?
  1. 36+9+4+1=50≈7.07\sqrt{36 + 9 + 4 + 1} = \sqrt{50} \approx 7.07
  2. k=1k=1: 14/50≈0.53\sqrt{14/50} \approx 0.53.   k=2\;k=2: 5/50≈0.32\sqrt{5/50} \approx 0.32
  3. k=1k = 1 keeps 36/50=72%36/50 = 72\%; k=2k = 2 keeps 45/50=90%45/50 = 90\%. So k=2k = 2.

The recipe

  1. Build the PPMI matrix MM, of size ∣V∣×∣C∣|V| \times |C|
  2. Compute M=UΣV⊤M = U\Sigma V^\top
  3. Choose kk
  4. Word vectors = rows of W=UkΣkαW = U_k \Sigma_k^{\alpha}, with α∈[0,1]\alpha \in [0, 1]
print("variance kept by k:", np.cumsum(s**2) / np.sum(s**2))
W = U[:, :2] * s[:2]                       # k = 2, alpha = 1
print("word vectors (coffee, tea, laptop, tablet):\n", W)
variance kept by k: [0.521 0.989 0.999 1.   ]
word vectors (coffee, tea, laptop, tablet):
 [[0.    1.405]
 [0.    1.446]
 [1.448 0.   ]
 [1.558 0.   ]]
  • A big gap between σ2\sigma_2 and σ3\sigma_3 (about 7x): this matrix is basically two-dimensional
  • In practice, α=0\alpha = 0 (throwing the σ\sigma’s away) often works best. It’s a hack that works.

Toy example ↔\leftrightarrow SVD: the pieces

The toy matrix (rows coffee, espresso, cappuccino; columns brew, cup) has this SVD:

(111001)⏟M=(26016−121612)⏟U(3001)⏟Σ12(11−11)⏟V⊤ \underbrace{\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{pmatrix}}_{M} = \underbrace{\begin{pmatrix} \dfrac{2}{\sqrt{6}} & 0 \\[8pt] \dfrac{1}{\sqrt{6}} & -\dfrac{1}{\sqrt{2}} \\[8pt] \dfrac{1}{\sqrt{6}} & \dfrac{1}{\sqrt{2}} \end{pmatrix}}_{U} \underbrace{\begin{pmatrix} \sqrt{3} & 0 \\ 0 & 1 \end{pmatrix}}_{\Sigma} \underbrace{\dfrac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix}}_{V^\top}

In the toy example In the SVD
kept line u1=(1,1)/2\mathbf{u}_1 = (1, 1)/\sqrt{2} v1\mathbf{v}_1, row 1 of V⊤V^\top
dropped direction u2=(−1,1)/2\mathbf{u}_2 = (-1, 1)/\sqrt{2} v2\mathbf{v}_2, row 2 of V⊤V^\top
best line keeps 3, loses 1 σ12=3\sigma_1^2 = 3,   σ22=1\;\sigma_2^2 = 1
total ∑w∥vw∥2=4\sum_w \|\mathbf{v}_w\|^2 = 4 ∥M∥F2=σ12+σ22=4\|M\|_F^2 = \sigma_1^2 + \sigma_2^2 = 4

Careful with names: the toy example’s u1,u2\mathbf{u}_1, \mathbf{u}_2 live in context space, so SVD calls them v1,v2\mathbf{v}_1, \mathbf{v}_2. SVD’s ui\mathbf{u}_i are the word-side weights.

Toy example ↔\leftrightarrow SVD: the steps

In the toy example In the SVD
Rotate into (u1,u2)(\mathbf{u}_1, \mathbf{u}_2): coffee (2,0)(\sqrt{2}, 0), espresso (12,−12)(\tfrac{1}{\sqrt{2}}, -\tfrac{1}{\sqrt{2}}), cappuccino (12,12)(\tfrac{1}{\sqrt{2}}, \tfrac{1}{\sqrt{2}}) rows of UΣ=MVU\Sigma = MV
Drop u2\mathbf{u}_2: landing points t∗=2,12,12t^* = \sqrt{2}, \tfrac{1}{\sqrt{2}}, \tfrac{1}{\sqrt{2}} truncate to k=1k = 1: word vectors U1Σ1U_1 \Sigma_1
One number per word ⇒\Rightarrow rank 1: rows (1,1),(12,12),(12,12)(1, 1), (\tfrac12, \tfrac12), (\tfrac12, \tfrac12) M1=σ1u1v1⊤M_1 = \sigma_1 \mathbf{u}_1 \mathbf{v}_1^\top
Which line? Lose the least: loss 1 Eckart–Young: ∥M−M1∥F2=σ22=1\|M - M_1\|_F^2 = \sigma_2^2 = 1
  • Trying lines by hand found the top singular vector. SVD finds it directly, and Eckart–Young says no line does better.
  • The PPMI example is the same procedure with 6 contexts and k=2k = 2.