Two observations about the rows of M

Assume M = A·W with A separable 1:08:35.

  1. Anchor rows expose W directly. For an anchor row aᵢ (only the i-th entry non-zero), the product with W gives M[aᵢ, ·] = A[aᵢ, i] · W[i, ·]. In words: the rows of W appear as rows of M, up to scaling — W is hiding inside the observable M 1:09:01, 1:09:38, 1:10:26.
  2. Every other row is a non-negative combination. For an arbitrary row j: M[j, ·] = Σᵢ₌₁ᵏ A[j,i] · W[i, ·] 1:10:26, 1:10:53.

Normalization turns combinations into convex combinations

  • W.l.o.g. rescale so the rows of M, A and W all sum to 1 1:10:53, 1:12:03.
  • Then for an anchor row the scaling factor becomes exactly 1, so M[aᵢ, ·] = W[i, ·] 1:12:03, 1:12:19.
  • And every other row becomes a convex combination rather than merely non-negative 1:12:19.

Conclusion: every row of M is either a row of W or lies in the convex hull of the rows of W 1:12:19.

The resulting geometric problem

  • Given: n points v₁ … vₙ lying in the convex hull of k unknown ones v_{a₁} … v_{a_k} (which are the rows of W) 1:13:06.
  • Find: the indices a₁ … a_k, or equivalently the corresponding rows 1:13:54.
  • Picture: points scattered inside a triangle, with the triangle's vertices included among the given points — recover the vertices 1:13:54, 1:14:37.
  • This is equivalent to NMF under the separability assumption 1:14:37.

One more (degeneracy) assumption

  • A row of W could in principle sit inside the hull — but then that row can be dropped, yielding a smaller factorization. It's the analogue of factoring a rank-R matrix with R+1 columns, which is not what we want 1:15:06, 1:15:34.
  • So assume the rows of W are all vertices of the convex hull 1:16:00.

The algorithm

After removing duplicate points, for each point vᵢ test whether it lies in the convex hull of all the other points 1:16:13.

  • Claim: vᵢ is a vertex ⟺ vᵢ is not in the convex hull of the rest 1:16:13, 1:17:19.
  • Proof sketch: an interior point stays inside after removing duplicates; a vertex, once removed from the set, is outside the shrunken hull 1:17:19, 1:17:52.
  • The membership test is a linear program: find αⱼ ≥ 0 with Σ_{j≠i} αⱼ = 1 and vᵢ = Σ_{j≠i} αⱼ vⱼ 1:17:52, 1:18:15.
  • Feasible ⇒ interior point. Infeasible ⇒ vertex (an anchor word / row of W) 1:18:43, 1:19:12.
flowchart TD
    S[Rows of M, duplicates removed] --> LP["LP: is v_i a convex combination<br/>of the other points?"]
    LP -->|feasible| I[Interior point → discard]
    LP -->|infeasible| V[Vertex → anchor word,<br/>row of W recovered]

What breaks in practice, and the fixes

  1. Probabilities cannot be estimated accurately — in fact estimates are far from accurate 1:19:12.
  2. Even a small perturbation moves points, possibly out of the low-dimensional subspace, so exact hull membership stops holding. Fix: test whether a point is close to the convex hull of the others — still an LP, but harder 1:19:38, 1:19:59.
  3. M itself cannot be estimated well enough. Fix: estimate instead the probability that two words co-occur in the same document — a quantity estimable to arbitrary accuracy given enough documents 1:19:59, 1:20:26.

Empirical outcome

The improved version of this algorithm can actually be implemented, is pretty fast, runs on a New York Times article corpus, produces results comparable to previous heuristic algorithms, and is even faster than them 1:20:53, 1:21:24.