Source-linked AI summary
Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
Abhishek Kumar, Vikas Sindhwani, Prabhanjan Kambadur
TL;DR
Separable NMF is tractable but exact and approximate formulations are NP-hard. The paper reframes it as conical-hull extreme-ray finding and introduces scalable Xray algorithms that outperform other separable NMF methods on reported topic-modeling tasks.
Problem
Exact and approximate NMF formulations are NP-hard, while much existing algorithmic work treats them as general non-convex programs.
Method
The Xray family identifies conical-hull extreme rays through iterative anchor detection, projection onto the current cone, and residual-based selection.
Results
Among separable NMF techniques, Xray (greedy) and Xray (dist) outperform Hottopixx and GV across three topic-modeling datasets, except Xray (dist) on Reuters.
Takeaways & Limitations
The methods provide highly scalable, local-minima-free alternatives to existing local optimization techniques for separable NMF.
Takeaways & Limitations
The approach assumes separability, and formal noise analysis remains future work.
Abstract
from arXiv · showhide
The separability assumption (Donoho & Stodden, 2003; Arora et al., 2012) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several other favorable properties in relation to existing methods. A parallel implementation of our algorithm demonstrates high scalability on shared- and distributed-memory machines.
1 Introduction
The introduction frames NMF as a conical-hull problem that is generally NP-hard but becomes exactly tractable under separability, where a small subset of data columns serves as anchors. It presents scalable, empirically noise-robust algorithms designed to recover separable NMF solutions after exactly r iterations without additional parameters.
- Problem formulation: NMF seeks r nonnegative generators whose cone contains the cone of the data columns, framing factorization geometrically as a conical-hull containment problem.The columns of X lie inside a cone generated by the columns of W.
- Computational challenge: The resulting polyhedral nesting problem is NP-hard, motivating alternatives to general non-convex optimization methods that offer limited guarantees.Existing approaches typically guarantee convergence only to a stationary point for approximate NMF.
- Separability: Under separability, all data columns lie in a cone generated by a small subset of r columns of X, called anchor columns.Algebraically, the factor matrix W is hidden among the columns of X, while corresponding columns of H form an identity matrix.
- Contributions: The paper introduces a family of highly scalable and empirically noise-robust algorithms for separable NMF with several favorable properties.The algorithms are connected to convex- and conical-hull procedures from computational geometry.
- Contributions: The proposed algorithms recover the correct separable solution after exactly r iterations and require no additional parameters.This property is stated for the separable case.
2 Fast Conical Hull Algorithms
Xray reformulates separable NMF as iterative expansion of a conical hull, identifying one previously unselected extreme ray per iteration and projecting data onto the current cone. Under a unique-maximizer condition, the detection step is provably correct, while alternative exterior-point choices can differ substantially under noise.
- Conical-hull geometry: Geometrically, each iteration rotates a face of the current cone toward an exterior point, expanding the cone by one extreme ray.The process continues until the full dataset lies inside the cone generated by the selected anchors.
- Xray algorithm: Xray alternates detecting an anchor extreme ray and projecting all columns onto the current cone to obtain residuals.Projection uses simultaneous nonnegative least squares; the algorithm repeats until r anchors are selected.
- Correctness: When the maximizer is unique, Xray adds an extreme ray that was not selected in earlier iterations.The result follows from residual sign properties for current extreme rays and positivity for points exterior to the current cone.
- Exterior point selection: Any nonzero exterior-point residual can drive exact separable recovery, enabling random, maximum-residual, and greedy selection criteria.These choices all solve the separable problem exactly but may behave differently with noise; the greedy variant is not guaranteed to solve noisy separable NMF.
3 Empirical Observations
The experiments compare Xray with Hottopixx, GV, and traditional NMF across synthetic noise, topic-modeling datasets, and large-scale parallel settings. Xray shows strong noise robustness and competitive downstream clustering performance without repeated runs.
- Experimental scope: The evaluation includes synthetic and medium-scale topic-modeling comparisons plus scalability benchmarks on large text datasets using multicore and distributed systems.Baselines include Hottopixx, GV, and traditional alternating-optimization NMFs.
- Synthetic experiments: Xray (max) shows the best noise robustness for anchor recovery as Gaussian noise increases from 0 to 1.5.The recovery rate is averaged over 10 synthetic trials for each noise level.
- Text datasets: The study evaluates classification and clustering on TDT-2, BBC, and Reuters using anchor-word features derived from the document-term matrices.Classification uses 5% of documents for training and 95% for testing, with multiclass SVM and four-fold cross-validation.
- Clustering experiments: The proposed Xray methods are among the best-performing methods for document clustering and do not require multiple runs like traditional NMFs.Clustering uses NMI after assigning documents by the maximum element of each row of W and refining with alternating optimization.
- Effect of column normalization: The experiments also examine how ℓ1 column normalization affects prediction performance because it can disturb tf-idf structure.Prior separable-NMF methods require ℓ1-normalized columns, motivating the separate word-normalization experiment.
3.3 Large-scale Experiments
Large-scale experiments show that parallel Xray scales across shared-memory systems, while the authors also implement distributed-memory support and benchmark against Hottopixx. The reported results include substantial multicore speedups and identify optimization opportunities for sparse and dense workloads.
- Parallel implementation: The C++ implementation supports shared-memory task parallelism through PFunc and distributed-memory parallelism through MPI.This enables execution on multicore machines and clusters of multicore machines.
- Shared-memory performance: 409 seconds and 4.2x speedup for RCV1, 9.8 seconds and 4.5x speedup for IBMT, and 1147 seconds for dense PPL2 on 8 cores.Figure 6 reports these multi-threaded results while detecting 100 topics on the 8-core daniel machine.
- Optimization opportunities: Further speedups may come from optimizing sparse-matrix data layout and using tuned BLAS with more BLAS-3 operations for dense problems.These changes target reduced thread memory contention and improved memory-to-compute ratio.
- Comparison with Hottopixx: The study compares Xray with Hottopixx using author-consulted settings, but direct comparison is difficult because their runtime characteristics differ.The detailed comparison is reported in Table 3.2, whose numerical entries are not included in the supplied passage.
4 Conclusions and Future Work
The proposed methods compare favorably with recent separable NMF algorithms and provide scalable, local-minima-free alternatives to local optimization. Future work targets noise analysis, streaming data, and social media content analysis.
- The methods perform favorably against recently proposed separable NMF algorithms while offering highly scalable, local-minima-free alternatives to existing local optimization techniques.
- Future work includes formal noise analysis of the algorithms, online processing of arriving documents or words, and social media content analysis.