Source-linked AI summary
Factoring nonnegative matrices with linear programs
Victor Bittorf, Benjamin Recht, Christopher Re, Joel A. Tropp
TL;DR
NMF is computationally difficult and lacks reliable guarantees for many heuristic methods. The paper formulates feature selection as a linear program that identifies salient rows, then uses them to construct an NMF. The resulting framework provides exact recovery for separable data, scalable implementations, and broader applicability, while leaving extensions to other localization problems for future work.
Problem
NMF is widely used for feature selection, but its computational difficulty and limited theoretical understanding constrain reliable algorithmic guarantees.
Method
The paper uses a data-driven linear-programming formulation to select salient rows that express the remaining data and yield a low-rank NMF.
Results
The method constructs a rank-r NMF for separable matrices, improves the AGKM error bound in the high-SNR regime, and supports large-scale experiments.
Takeaways & Limitations
The framework provides a scalable basis for analyzing and deploying factorization problems expressible as linear or convex factorization-localizing programs.
Takeaways & Limitations
The paper identifies applicability to other factorization-localizing algorithms, such as subspace clustering, as future work.
Abstract
from arXiv · showhide
This paper describes a new approach, based on linear programming, for computing nonnegative matrix factorizations (NMFs). The key idea is a data-driven model for the factorization where the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C such that X approximately equals CX and some linear constraints. The constraints are chosen to ensure that the matrix C selects features; these features can then be used to find a low-rank NMF of X. A theoretical analysis demonstrates that this approach has guarantees similar to those of the recent NMF algorithm of Arora et al. (2012). In contrast with this earlier work, the proposed method extends to more general noise models and leads to efficient, scalable algorithms. Experiments with synthetic and real datasets provide evidence that the new approach is also superior in practice. An optimized C++ implementation can factor a multigigabyte matrix in a matter of minutes.
1 Introduction
NMF is widely used for feature selection, but its computational hardness limits rigorous, practical methods. This paper introduces a scalable linear-programming formulation with theoretical guarantees, broader noise-model applicability, and efficient large-scale implementations.
- NMF is popular for feature selection, yet limited theory establishes when heuristic methods are correct.
- NP-hardness means practical NMF methods require additional assumptions about the data.
- The AGKM algorithm is polynomial-time and provably correct under an appropriate data model, but its computational cost limits practical impact.
- The proposed method uses a single linear program, succeeds under AGKM-like assumptions plus a margin constraint, and improves its high-SNR error bound.
- The formulation supports scalable solvers, including stochastic gradient descent and parallel implementations for extremely large datasets.
- The data-driven model selects a small collection of rows whose values can express the remaining rows.
2 Separable Nonnegative Matrix Factorizations and Hott Topics
This section frames separable NMF through simplicial rows whose convex hull contains the remaining data, enabling feature selection and factor recovery. It also explains why the earlier AGKM method is costly and tied to a particular noise norm.
- Exact NMF factors Y into nonnegative matrices F and W, typically with rank r much smaller than the numbers of features and examples.
- A vector set is α-robust simplicial when each vector lies at least ℓ1 distance α from the convex hull of the others.
- Separable NMF uses r simplicial rows whose convex hull contains the remaining rows, allowing efficient recovery of an NMF.
- The algorithm identifies simplicial rows, called hott rows or hott topics, then expresses other rows as convex combinations of them.
- The model assumes a few selected feature values can reconstruct all features, with examples in text, vision, and audio applications.
- AGKM requires parameter knowledge, computes all pairwise row distances at O(f^2n), and solves a linear program for every row.
- The proposed linear-programming approach addresses AGKM's computational drawbacks and is not restricted to its particular error norm.
3 Main Theoretical Results: NMF by Linear Programming
The paper formulates separable NMF as a feature-selection problem solvable through linear programming, then extends the approach to approximately separable noisy data. Its guarantees rely on separability and, for robustness, an additional margin constraint.
- Exact separable NMF: A linear program identifies a localizing matrix C whose selected rows and columns recover an exact rank-r NMF under separability.C belongs to Φ(Y), satisfies CY = Y and structural constraints, and its integral diagonal identifies the selected features.
- Exact separable NMF: The factorization is data-driven: a small collection of rows from the data matrix expresses the remaining rows.This localization strategy is related to exemplar-based factorizations such as rank-revealing QR and interpolative decomposition.
- Robustness to Noise: For noisy observations X = Y + ∆, the robustness theorem assumes normalized rows and a margin separating non-hot rows from hot rows.Under these assumptions, the method returns a nonnegative factorization and correctly identifies the hot topics.
- Exact separable NMF: Algorithm 2 selects indices with Cii = 1, uses the corresponding rows of Y for W, and extracts columns of C for F.The algorithm minimizes a distinct-cost linear objective over Φ(Y) before performing these extractions.
- Robustness to Noise: Compared with AGKM, the method supports a more favorable approximation under the margin condition and does not require prior knowledge of α.The AGKM approach requires prior parameters and incurs costly row-distance and convex-hull computations.
- Scalability: Large-scale deployment requires specialized solvers because off-the-shelf linear-programming runtimes become prohibitive for large matrix-factorization problems.The paper therefore develops efficient algorithms for solving the formulation at scale.
4 Incremental Gradient Algorithms for NMF
The scalable implementation solves the localization objective with dual decomposition and incremental projected gradient descent. Randomized updates, efficient projections, and parallel memory-aware execution make the method suitable for very large datasets.
- Optimization method: Dual subgradient ascent alternates between minimizing the Lagrangian over Φ0 and taking subgradient steps in the dual variables.The constraint set Φ0 retains nonnegativity, bounded diagonal entries, and the symmetry-breaking constraints Cij ≤ Cjj.
- Optimization method: The dual updates adjust wi using reconstruction residuals and β using the trace constraint, although experiments typically update only β.The paper reports that updating wi makes very little difference in solution quality.
- Optimization method: Projected incremental gradient descent samples one summand at random, follows its subgradient, and projects the iterate onto Φ0.Projection can be performed after sorting individual columns of C plus a linear-time operation.
- Hottopixx: Hottopixx repeats incremental updates in epochs, then forms W from identified hot rows and obtains F by solving the nonnegative fitting problem.Its procedure is presented as an implementation of approximate separable NMF by incremental gradient descent.
- Large-scale implementation: Parallel execution exploits sparse updates, contiguous storage, cache-aware row assignment, and repeated scans of X by worker threads.The implementation uses a dense representation for C to trade additional space for runtime performance.
5 Experiments
Synthetic and real-data experiments compare Hottopixx with prior methods on reconstruction error, runtime, scalability, and feature-selection performance. Hottopixx offers strong noise performance without AGKM’s parameter requirements, while its optimized implementation scales to large datasets and parallel hardware.
- Synthetic experiments: Over 2000 experiments with 405 parameter settings were compared using performance profiles across error and runtime metrics.Higher performance-profile curves indicate algorithms that more often achieve values near the best observed result.
- Synthetic experiments: The linear programming solver typically achieves the lowest (∞, 1)-norm error, but SDPT3 is prohibitively slow on larger matrices.Hottopixx achieves better noise performance than AGKM in much less time and requires neither ϵ nor α.
- Synthetic experiments: Hottopixx achieves about the same error performance as AGKM without requiring the parameters ϵ and α.This comparison concerns the standard Hottopixx configuration in the performance profiles.
- Synthetic experiments: Four epochs make Hottopixx the fastest variant, while its reconstruction error remains competitive in noisy examples and can beat AGKM at very high noise.The four-epoch variant sacrifices some optimal noise performance, whereas AGKM degrades as η approaches or exceeds 1; RMSE results are qualitatively similar.
- Large-scale experiments: Hottopixx shows superlinear speedups over serial execution for up to 20 threads on the jumbo and ClueWeb datasets.The speedup is reported relative to a serial implementation.
- Large-scale experiments: On three large datasets, the C++ implementation trains all datasets in minutes and correctly identifies the hott topics on the jumbo set.The large-data experiments include jumbo, ClueWeb09, and RCV1.
- Large-scale experiments: With 1500 hott topics, RCV1 achieves 7% misclassification error versus 5.5% using all features.For ClueWeb, RMSE decreases quickly over the first few hundred topics.
6 Discussion
The discussion presents the work as a general framework for factorization problems expressible through linear or convex factorization-localizing programs. It identifies extending the approach to other localization algorithms as future work.
- Discussion: The framework analyzes and deploys factorization problems that can be posed as linear or convex factorization-localizing programs.The stated scope extends beyond the specific NMF application.
- Discussion: Figure 3 summarizes parallel speedup, ClueWeb RMSE, and RCV1 test error as complementary large-scale evaluation axes.The figure compares speedup on jumbo and ClueWeb, RMSE on ClueWeb, and test error versus hott topics on RCV1.
- Discussion: Future work should test Hottopixx on other factorization-localizing algorithms, including subspace clustering, and revisit earlier theoretical bounds.The paper identifies applicability and prior theoretical guarantees as open questions.
A Proofs
The proof analyzes how approximate convex representations of distinguished “hott” rows must concentrate weight near the represented row under separability and margin assumptions.
- Assumptions: An α-robust simplicial factorization separates each hott row from convex combinations of the other hott rows by at least α in ℓ1 distance.The proof assumes δ < α so each hott row is uniquely included among rows within δ distance.
- Coefficient bounds: Rows outside B_δ(i) have limited coefficient on hott row i: M_ℓi ≤ 1 − δ/2 when their ℓ1 distance from that hott row exceeds δ.This bound follows by expressing the row as a convex combination of hott rows and using the distance condition.
- Coefficient bounds: The proof combines the distance bound with α-robust simpliciality to lower-bound the weight assigned to the neighborhood of the target hott row.The argument uses the unit ℓ1 row norms and the convex-combination structure of the separable factorization.
- Localizing representations: Any representation of a hott row with ℓ1 error at most τ must assign substantial weight to rows within δ of that hott row.The proof formalizes this using w_i, the total coefficient weight on the δ-neighborhood B_δ(i).
- Localizing representations: A minimizing representation can eliminate coefficients on every nearby non-hott row while preserving the represented vector and the coefficient constraints.Each such non-hott row is replaced by a convex combination of hott rows, reducing w_i without changing c^T Y.
A.1 Proof of Theorem 3.1
The proof shows that the linear-program constraints identify the hott rows, including one representative from each group of duplicated rows.
- Distinct rows: Without duplicated rows, exact separability and the trace constraint force every hott row to have diagonal weight one and every non-hott row diagonal weight zero.Thus feasible matrices identify the hott rows on the diagonal.
- Duplicated rows: With duplicated rows, the objective assigns diagonal weight to the duplicate with the smallest p_j within each topic group.The diagonal still identifies all r distinct hott topics while selecting one duplicate for each topic.
A.2 Proof of Theorem 3.2
The proof transfers localization guarantees from an ideal matrix Y to noisy observations X, then uses diagonal weights to identify hott topics and recover an accurate factorization.
- Noise model: The observed matrix is modeled as X = Y + Δ, with rows scaled to unit sum and Δ representing perturbation.The analysis assumes a rank-r separable NMF for Y with α-robust simplicial rows.
- Localization program: An exact factorization-localizing matrix for Y becomes an approximate factorization-localizing matrix for X under the perturbation model.This establishes feasibility of the linear program used for the noisy problem.
- Topic identification: Every C in Φ_2ε(X) satisfies C_ii ≥ 1 − (8ε + 4ε^2)/min{αd_0, α^2} for each hott topic i.The bound uses unit row sums, the margin assumption, and the localization lemma.
- Topic identification: When each hott diagonal weight exceeds 1 − 1/(r + 1), every hott row carries more weight than any non-hott row and can be identified.The trace constraint limits the total remaining weight on non-hott rows.
- Factor recovery: After identifying the hott topics, a second linear program computes a 2ε-accurate factorization.The second optimization operates on the selected set of rows.
B Projection onto Φ0
The projection onto Φ_0 is reduced to independent column projections, each solved through a thresholded construction that has a linear-time implementation.
- Projection decomposition: Projection onto Φ_0 can be computed one column at a time after permuting each column’s entries.This decomposes the matrix projection into simpler vector projections.
- Optimality and implementation: The constructed vector x̂ is optimal, and Algorithm 5 computes it in linear time.The optimality argument recasts the problem as a linear program whose cost signs determine the solution.
- Optimality and implementation: Algorithm 5, Column Squishing, returns the projection of z onto the set defined by 0 ≤ x_i ≤ x_1 for all i and x_1 ≤ 1.The algorithm clips selected coordinates and retains positive parts for the remaining coordinates.