Arora 2012 - FastAnchorWords Algorithm and Guarantees

Summary

FastAnchorWords greedily picks the point farthest from the span of those already chosen (after a random projection to $4\log V/{ϵ}^2$ dimensions), then runs a clean-up pass. For a $\gamma$-robust simplex perturbed by at most $ϵ$, it outputs $K$ points that $O(ϵ/\gamma )$-cover the vertices in $\tilde{O}(V^2+VK/{ϵ}^2)$ time, avoiding all linear programs.

Main Content

$\gamma$-robust simplex and $ϵ$-covering (Defs 4.1-4.2)

A simplex $P$ is $\gamma$-robust if for every vertex $v$ the ${\ell }_2$ distance from $v$ to the convex hull of the other vertices is at least $\gamma$. A point $a_i$ $ϵ$-covers vertex $v_j$ if writing $a_i={\sum }_j{c}_j{v}_j$ (convex combination), $c_j\ge 1-ϵ$; a set of $K$ points $ϵ$-covers the vertices if each vertex is $ϵ$-covered by some point.

Anchor finding (Thm 4.3)

Let $A=\{a_1,\dots ,a_V\}$ have convex hull a $\gamma$-robust simplex with vertices $v_1,\dots ,v_K\in A$, and let $d_i$ satisfy $\Vert a_i-d_i\Vert \le ϵ$. If $20Kϵ/{\gamma }^2<\gamma$, FastAnchorWords runs in $\tilde{O}(V^2+VK/{ϵ}^2)$ and outputs a subset of $\{d_i\}$ of size $K$ that $O(ϵ/\gamma )$-covers the vertices.

Algorithm 4. (1) Project points to a random $4\log V/{ϵ}^2$-dimensional subspace (in practice dimension 1000 is used: runtime $O(V^2+1000VK)$). (2) $S\leftarrow \{d_i$ farthest from the origin$\}$. (3) For $i=\mathrm{1..}K-1$: add the point with the largest distance to $\text{span}(S)$ (distance = norm of projection onto the orthogonal complement). (4) Clean-up: for each $i$, replace $v_i^{\prime }$ by the point farthest from $\text{span}(\{v^{\prime }\}\setminus v_i^{\prime })$. This greedily maximises simplex volume; the larger the volume the more words per document the model can explain.

Lemmas (proof ideas). Suppose $S$ contains $k$ points, each $\delta$-close to distinct vertices, $\delta <\gamma /20K$.

• Lemma 4.4 (A.1): some vertex is at distance at least $\gamma /2$ from $\text{span}(S)$ - a volume argument; simplex volume is proportional to a determinant of edge vectors, and Lemma A.3 gives $\text{vol}(S)(1-2\delta /\gamma {)}^{K-1}\le \text{vol}(S^{\prime })\le \text{vol}(S)(1+4\delta /\gamma {)}^{K-1}$ for perturbations $\Vert v_i^{\prime }-v_i\Vert \le \delta$ with $10\sqrt{K}\delta <\gamma$ (via Claim A.4: $\det (A+E)/\det (A)\ge (1-\delta /\gamma {)}^K$).
• Lemma 4.5 (A.2): the point found is $\delta =O(ϵ/{\gamma }^2)$-close to a vertex; the new $\delta$ depends on $ϵ,\gamma$ only, not the previous $\delta$, so errors do not compound exponentially.
• Lemma 4.6: after $K-1$ points, the cleanup finds the missing vertex within $1-O(ϵ/\gamma )$.

Recovery guarantee (App. B). Lemma B.1: for a $\gamma$-robust simplex with perturbed vertices (error ${\delta }_1$) and point (error ${\delta }_2$), representation coefficients change by at most $4({\delta }_1+{\delta }_2)/\gamma$ when $10\sqrt{K}{\delta }_1\le \gamma$.

Sample complexity of FastAnchorWords + RecoverL2 (Thm B.2)

With $M\ge \max \{O(a{K}^3\log V/D(\gamma p{)}^6),O((aK{)}^3\log V/D^3(\gamma p{)}^4)\}$ documents (up to $ϵ$-dependent factors that are garbled in the text extraction of the PDF; check the appendix of the PDF for exact exponents) the algorithm learns $A$ with entry-wise error at most $ϵ$.

Related work: separability = “pure pixel” assumption in hyperspectral unmixing; VCA (no cleanup) and N-FINDR (greedy volume) are similar but only proven in the infinite-data case; Thurau et al. 2010 and Kumar et al. 2012 use NMF under separability but need the term-document matrix to approximate its expectation, which fails for short documents - working with the Gram matrix $Q$ avoids this.

Examples

Greedy farthest-point on a triangle

$K=3$ vertices at $(0,0),(1,0),(0,1)$ with 20 interior points. Start: farthest from the origin in the projected rows is a vertex; the second step picks the point farthest from that vertex’s span (another vertex); the third picks the point farthest from the plane/line spanned by the two (the remaining vertex). Interior points are never farthest because distances from a subspace are convex in the point. See code in Arora 2012 - Recover Algorithms RecoverKL and RecoverL2.

Connections

Arora 2012 - Separability and Anchor Words, Concept - Topic Model Evaluation and Stability (stability across restarts: anchors are deterministic).

See Also

Arora 2012 - Practical Provable Topic Modeling - Overview