Source-linked AI summary
Algorithms, Initializations, and Convergence for the Nonnegative Matrix Factorization
Amy N. Langville, Carl D. Meyer, Russell Albright, James Cox, David Duling
TL;DR
NMF algorithms are sensitive to initialization, especially ALS methods, and practical convergence control remains difficult. The paper develops ACLS and AHCLS, compares six initialization procedures, and evaluates convergence criteria. It concludes that the new ALS methods are fast, initialization matters, and alternative stopping criteria should be considered, while their stationary points are not guaranteed to be local minima.
Problem
NMF algorithms, particularly ALS methods, are sensitive to initialization, while fixed-iteration stopping is problem-dependent and objective-based convergence is expensive.
Method
The paper presents ACLS and AHCLS, compares six initialization procedures on these ALS algorithms, and examines practical convergence criteria.
Results
ACLS and AHCLS are among the fastest available NMF algorithms, and the experiments compare their accuracy and speed across initialization choices and convergence approaches.
Takeaways & Limitations
Fast ALS-type methods can provide initializations for slower algorithms when convergence to a local minimum is required, and practical NMF implementations should consider alternatives to fixed iteration counts.
Takeaways & Limitations
Because ad-hoc nonnegativity enforcement lacks a proof of convergence to a local minimum, saddle points remain possible.
Abstract
from arXiv · showhide
It is well known that good initializations can improve the speed and accuracy of the solutions of many nonnegative matrix factorization (NMF) algorithms. Many NMF algorithms are sensitive with respect to the initialization of W or H or both. This is especially true of algorithms of the alternating least squares (ALS) type, including the two new ALS algorithms that we present in this paper. We compare the results of six initialization procedures (two standard and four new) on our ALS algorithms. Lastly, we discuss the practical issue of choosing an appropriate convergence criterion.
1 Introduction
Nonnegative matrices arise across text, images, recommendations, and gene-expression analysis. NMF offers interpretable factors while retaining performance close to SVD for clustering and retrieval.
- Applications: Nonnegative matrices represent documents, images, purchase histories, and gene-expression measurements.Document-term matrices contain term counts, image matrices contain nonnegative pixel values, recommendation matrices record sparse purchases or ratings, and gene-expression matrices record experimental observations.
- Goals: These matrices support clustering, similarity retrieval, and identification of interpretable dimensions.The paper identifies these as three common goals in mining information from nonnegative data.
- Motivation: SVD supports clustering and retrieval but does not provide interpretable mathematical factors.The paper presents interpretability as the key limitation of SVD for the third goal.
- Motivation: NMF can work nearly as well as SVD for clustering and retrieval while also achieving interpretable factorization.The comparison is stated at the level of the three information-mining goals.
- Scope: Although examples emphasize text mining, the term-by-document framing also applies to gene, purchase, and other application matrices.The paper notes that its terminology can be replaced according to the application area.
2 Low Rank Approximations
Low-rank approximations compress and structure large data matrices, but SVD and NMF trade off optimality, robustness, sparsity, interpretability, and convergence behavior.
- Overview: Low-rank approximation replaces a large matrix with a lower-rank representation that can reduce storage and clarify relationships.The paper focuses on SVD and NMF as low-rank approximations for data-mining problems.
- SVD: Truncated SVD is the best rank-k approximation in Frobenius norm and provides a fast, robust, well-defined baseline.Its singular components are used to form the rank-k approximation.
- SVD: SVD factors are often dense and mixed in sign, which can increase storage and prevent direct interpretation of nonnegative data.The loss of nonnegative structure is identified as the source of interpretability problems.
- NMF: NMF factors A≈W_kH_k are nonnegative, generally sparse, and support additive parts-based interpretations.For text data, W columns can represent topics through their prominent terms; for images, basis vectors can represent facial components.
- NMF: NMF reconstructs images as well as SVD in the cited comparison while offering sparser, interpretable basis vectors.The image discussion contrasts sparse NMF bases and weights with nearly dense SVD factors.
- NMF limitations: NMF lacks unique factorization, and its optimization is not jointly convex in W and H, so initialization can affect the resulting factors.Different algorithms or parameter settings may produce different factors and local minima are not guaranteed.
3 ALS Algorithms for the NMF
The paper introduces ACLS and AHCLS as ALS-based NMF algorithms designed to produce sparse factors and avoid locking, while improving control over sparsity.
- Motivation: ACLS and AHCLS address the lack of sparse factors in several popular NMF algorithms.The paper motivates sparsity through storage, accuracy, and interpretability considerations.
- ALS framework: Both methods modify ALS by alternately solving for H with W fixed and for W with H fixed.This alternating least-squares structure is the common computational foundation of the two algorithms.
- ACLS: ACLS adds rewards for sparse factors using user-set parameters λ_H and λ_W.Increasing these parameters increases sparsity, but selecting them requires trial and error because they have no upper bounds.
3.1 The ACLS Algorithm
ACLS alternates regularized least-squares updates for H and W, then enforces nonnegativity by truncating negative entries to zero.
- Update formulation: ACLS solves a constrained least-squares problem for each alternating update.The variables are columns of A and H, with the H update requiring nonnegative decision variables.
- Computational trade-off: Exact NNLS methods are computationally expensive because their active-set procedures remain too slow for the ACLS bottleneck.The paper notes that even a faster NNLS variant is not fast enough in practice.
- Practical algorithm: Practical ACLS uses unconstrained least squares and sets every negative solution element to zero.The paper describes this ad-hoc enforcement as theoretically unattractive but effective in practice.
- Implementation: The implementation initializes W randomly or with another initialization and repeats the H and W updates for maxiter iterations.The displayed procedure applies the two update equations in alternating order.
3.2 The AHCLS Algorithm
AHCLS extends ACLS with user-controlled sparsity targets for both factor matrices, using Hoyer’s sparsity measure within an alternating least-squares procedure.
- AHCLS uses Hoyer’s sparsity measure instead of the simpler vector sparsity approximation.
- Users specify αW and αH to express desired sparsity percentages for the columns of W and H.Both parameters range from 0 to 1.
- The practical AHCLS algorithm initializes W randomly or with another procedure, then alternates constrained least-squares updates for H and W.Negative entries are set to zero after each update.
3.3 Advantages and Disadvantages of ACLS and AHCLS
ACLS and AHCLS combine fast alternating least-squares updates with sparse factors and greater flexibility than methods that lock zero elements, but their ad-hoc nonnegativity enforcement weakens convergence guarantees.
- Advantages: ACLS and AHCLS solve small k × k systems, converge quickly, and produce accurate NMF factors.The algorithms are described as faster than current truncated SVD algorithms.
- Advantages: Only W requires initialization, while sparsity is incorporated into both NMF factors.
- Advantages: Unlike locking algorithms, ALS methods can change zero elements and may escape paths toward poor local minima.
- Disadvantages: With ad-hoc nonnegativity enforcement, convergence to a local minimum is unproved because saddle points remain possible.Properly enforced ACLS and AHCLS are known to converge to a local minimum, but the faster ad-hoc variant lacks that guarantee.
- Disadvantages: Alternative nonnegativity treatments retain lengthy execution times or are left for future work.The paper identifies alternating linear programming and logarithmic negativity penalties as alternatives.
3.4 Numerical Experiments
Experiments on medlars and cisi compare ACLS and AHCLS with multiplicative-update and GDCLS methods, showing strong accuracy and speed performance for the ALS-type algorithms.
- Figure 3 compares ACLS and AHCLS with Lee-Seung multiplicative updates and GDCLS on medlars and cisi.
- The ALS-type algorithms outperform Lee-Seung methods in both accuracy and speed while matching GDCLS accuracy more quickly.
- ACLS and AHCLS require roughly 2/3 the time of GDCLS on average.
- ACLS and AHCLS approach the optimal rank-10 SVD factorization error while producing sparse, nonnegative factorizations faster than SVD.
4 Initializations
NMF initialization affects convergence speed and solution quality, especially for ALS algorithms. The paper compares six initialization procedures, including four proposed methods, and examines their quantitative and qualitative behavior on reuters10.
- Initialization sensitivity: Good initialization can improve NMF speed and accuracy by producing faster convergence to an improved local minimum.NMF algorithms are iterative and may require initialization of W, H, or both.
- Initialization sensitivity: ALS algorithms require initialization only for W because H(0) is computed quickly by least squares once W(0) is known.This allows the initialization study to focus on constructing a good W(0).
- Methods compared: The six methods comprise random and centroid initialization plus SVD-centroid, random Acol, random C, and co-occurrence initialization.The latter four are proposed methods, while the first two are existing methods.
- Methods compared: Random Acol averages random columns of A to form basis vectors, providing an inexpensive alternative whose performance lies between random and centroid initialization.It builds basis vectors from sparse document vectors rather than dense random vectors.
- Methods compared: Random C selects columns from the longest columns of A, whereas co-occurrence initialization applies a basis-vector procedure to C = AA^T.The co-occurrence method is impractical for text datasets because C can be very large and dense and its basis-vector procedure is expensive.
- Reuters10 experiments: On reuters10, SVD-centroid starts with basis vectors closest to the best basis vectors, while random and random Acol begin from genuinely random bases.The experiments distinguish quantitative accuracy from qualitative accuracy and compare basis vectors across initializations.
- Reuters10 experiments: The NMF basis vectors cover 8 of the 10 correct Reuters classifications; increasing k from 10 to 12 separates corn and grain from the wheat vector.Corn and grain are described as notoriously difficult categories to classify.
5 Convergence Criterion
The paper compares fixed-iteration, Frobenius, and angular convergence criteria for NMF, emphasizing the trade-off between computational cost and convergence behavior. The angular measure is cheaper and intuitive but can lose monotonicity when basis-vector ordering changes.
- Stopping criteria: Fixed-iteration stopping is common because evaluating the natural residual criterion ∥A−WH∥≤ε is comparatively expensive.The ACLS and AHCLS algorithms use maxiter, but the paper argues that this is not mathematically appealing.
- Comparison: The ACLS experiment on the cisi dataset compares the expensive Frobenius measure with the proposed angular convergence measure.The Frobenius implementation exploits the trace form of the norm.
- Frobenius measure: The trace-form Frobenius computation reuses quantities from least-squares steps, reducing redundant computation while still requiring several trace evaluations each iteration.trace(A^T A) is computed once; other terms must be evaluated repeatedly.
- Angular measure: The angular criterion stops when every successive topic-vector angle θ_i is at most ε.It compares topic vectors in W across iterations j and j+1.
- Angular measure: The angular measure is cheaper than the Frobenius measure but may not descend continually because basis-vector column ordering can change between iterations.It becomes more useful later, when column ordering is less likely to change, and requires storing the previous W matrix.
- Stationarity: A small residual or objective value does not guarantee stationarity, motivating post-stop stationarity checks or convergence criteria that test stationarity directly.The paper cites Lin’s related convergence-criterion discussion and stationarity proposal.
6 Conclusion
The conclusion presents ACLS and AHCLS as fast NMF algorithms, discusses their convergence and initialization limitations, and recommends context-appropriate stopping criteria. It particularly favors the angular measure when qualitative properties of W matter more than attaining a very small residual.
- Algorithms: ACLS and AHCLS are among the fastest available NMF algorithms, reportedly faster than truncated SVD algorithms.The algorithms converge to a stationary point but do not guarantee a local minimum.
- Convergence: If a local minimum is required, the paper recommends using a fast ALS-type result to initialize a slower algorithm that guarantees convergence to a local minimum.This recommendation separates fast preliminary optimization from algorithms with stronger convergence guarantees.
- Initialization: The paper presents alternatives to random initialization because initialization is an important practical choice for NMF algorithms.The conclusion identifies initialization as one of the paper’s practical contributions.
- Stopping criteria: The paper recommends replacing fixed iteration counts with stopping criteria suited to the users’ context and data.For applications focused on qualitative W vectors, driving the residual to a very small level may be unnecessary.
- Stopping criteria: The angular convergence measure is recommended when qualitative results from W are more important than reducing ∥A−WH∥ to a very small value.This conclusion follows the paper’s stated scope for choosing the stopping criterion.