Source-linked AI summary
Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization
Nicolas Gillis, François Glineur
TL;DR
NMF algorithms can be computationally difficult despite the usefulness of nonnegative low-rank decompositions. The paper accelerates MU and HALS by reusing expensive matrix products across cheaper inner updates, and experiments report substantially improved efficiency while preserving the original schemes’ convergence properties.
Problem
Nonnegative constraints improve interpretability in NMF applications but make factorization computationally difficult, motivating more efficient algorithms.
Method
The paper accelerates MU and HALS by analyzing per-iteration costs, repeating cheaper safeguarded factor updates, and applying the technique to projected gradient.
Results
The accelerated algorithms are empirically more efficient on image and text datasets, with A-HALS the most efficient tested method and A-MU often close to or faster than ANLS initially.
Takeaways & Limitations
Reusing expensive matrix products can substantially improve several two-block coordinate descent NMF algorithms while retaining the convergence properties of the original schemes.
Takeaways & Limitations
MU’s monotonic decrease does not by itself guarantee convergence to a stationary point, and rounding errors can trap entries at zero.
Abstract
from arXiv · showhide
Nonnegative matrix factorization (NMF) is a data analysis technique used in a great variety of applications such as text mining, image processing, hyperspectral data analysis, computational biology, and clustering. In this paper, we consider two well-known algorithms designed to solve NMF problems, namely the multiplicative updates of Lee and Seung and the hierarchical alternating least squares of Cichocki et al. We propose a simple way to significantly accelerate these schemes, based on a careful analysis of the computational cost needed at each iteration, while preserving their convergence properties. This acceleration technique can also be applied to other algorithms, which we illustrate on the projected gradient method of Lin. The efficiency of the accelerated algorithms is empirically demonstrated on image and text datasets, and compares favorably with a state-of-the-art alternating nonnegative least squares algorithm.
1 Introduction
NMF approximates a nonnegative matrix by a low-rank product of nonnegative factors, but the constraints make optimization computationally difficult. The paper develops accelerated versions of MU and HALS, grounded in their update structure and computational costs.
- NMF formulation: NMF approximates a nonnegative matrix M with a low-rank product of nonnegative matrices W and H.The approximation typically minimizes the sum of squared entrywise errors, expressed through the Frobenius norm.
- Motivation: Nonnegativity can improve interpretability in applications including text mining, image processing, hyperspectral analysis, computational biology, and clustering, but makes the problem computationally difficult.
- General framework: Most NMF algorithms alternate between updating W with H fixed and updating H with W fixed, forming a two-block coordinate descent framework.Each update seeks a nonnegative factor that reduces the reconstruction objective.
- Existing algorithms: MU updates factors multiplicatively and monotonically decreases the Frobenius-norm error, whereas HALS successively updates columns of W and rows of H through block-coordinate descent.HALS updates each column using an easily computed closed-form solution for the corresponding subproblem.
- Motivation: MU can converge slowly, especially for dense matrices, motivating later algorithms such as HALS, projected gradient methods, Newton-like methods, and ANLS.The paper focuses mainly on MU because of its popularity and HALS because of its practical efficiency.
- Paper contribution: The paper analyzes MU and HALS update costs, designs accelerated variants, applies the idea to projected gradient, studies convergence, and evaluates the methods on image and text datasets.The experiments compare the accelerated schemes with the state-of-the-art ANLS algorithm.
2 Analysis of the Computational Cost of Factor Updates
The cost analysis identifies matrix products shared across iterations as the expensive part of MU and HALS updates. The proposed acceleration reuses these products by performing multiple cheaper factor updates before recomputing them.
- Cost model: The analysis introduces K as the number of nonzero entries in M and assumes W and H are stored densely while achieving compression.For dense M, K equals mn; the compression assumption makes storing the factors cheaper than storing M.
- Cost comparison: MU and HALS have almost exactly the same computational cost, differing only by a typically negligible mr flops.
- Shared computations: In both algorithms, the first two update steps are identical and independent of the current W.
- Bottleneck: Computing MH(k)T is the most expensive step under the compression assumption, so it should be performed sparingly.
- Acceleration principle: The acceleration repeats cheaper updates of W before the next H update, reusing MH(k)T and H(k)H(k)T to improve NNLS subproblem solutions at relatively low additional cost.The original MU and HALS update W and H only once per outer iteration, so the number of inner updates becomes the central design question.
3 Stopping Criterion for the Inner Iterations
The paper compares fixed, dynamic, and hybrid rules for allocating inner iterations in accelerated MU and HALS. Fixed inner-iteration counts generally perform best, while hybrid safeguarding offers modest dense-case gains and limited sparse-case benefit.
- Fixed Number of Inner Iterations: Fixed inner iterations are chosen from flop-count ratios ρW and ρH, exploiting reused matrix products while updating one factor repeatedly.The first update is substantially more expensive than subsequent updates, motivating approximately 1 + αρW updates of W before updating H.
- Experimental Measure: E(t) normalizes objective improvement over time, enabling meaningful averages across initializations and datasets for monotonically decreasing algorithms.The experiments average E(t) over dense and sparse image and text datasets, ranks, and random initializations.
- Fixed Number of Inner Iterations: For MU, α = 1 is best among tested fixed values, and the original α = 0 algorithm converges significantly more slowly, especially on dense matrices.Figure 1 compares α = 0, 0.5, 1, 2, and 4 for dense and sparse inputs.
- Fixed Number of Inner Iterations: For HALS, α = 0.5 performs best, although acceleration is harder to distinguish from the original algorithm on sparse matrices.The sparse-case explanation is that HALS is already extremely efficient and one inner update substantially decreases the objective.
- Dynamic Stopping Criterion: Dynamic stopping based on consecutive-iterate differences does not outperform the best fixed counts and can underperform original HALS on sparse matrices.The criterion stops when the latest update becomes negligible relative to the first, without a fixed maximum count.
- Application to Lin’s Projected Gradient Algorithm: The same acceleration strategy improves Lin’s projected-gradient algorithm in both dense and sparse experiments, with α = 0.5 giving the best results.The safeguard provides little additional help for projected gradient.
4 Convergence to Stationary Points
The accelerated MU variant preserves monotonic decrease, while convergence to stationary points requires safeguards or assumptions; accelerated HALS inherits stationary-point convergence properties under bounded inner iterations.
- Multiplicative Updates: The accelerated schemes retain non-increasing objective values because they repeat updates that individually do not increase the Frobenius error.For MU, this monotonicity alone does not ensure convergence to a stationary point.
- Multiplicative Updates: MU may fail to reach a stationary point when rounding errors create zero entries that multiplicative updates cannot change.The convergence question for unmodified MU remains open, despite monotonicity.
- Multiplicative Updates: For δ > 0 and factors bounded component-wise below by δ, the modified MU updates have non-increasing error and stationary limit points.The theorem applies to the corresponding constrained optimization problem.
- Multiplicative Updates: A bounded number of inner iterations preserves the theorem’s convergence argument for the accelerated MU variant.The proof relies on update limit points being fixed points.
- Hierarchical Alternating Least Squares: HALS is cyclic exact block-coordinate descent, optimizing columns of W and rows of H in alternating order.Its block subproblems have uniquely attained optima under the stated nonzero-factor conditions.
- Hierarchical Alternating Least Squares: Accelerated HALS changes the block order by repeating factor updates, yet inherits the convergence properties of exact block-coordinate descent.This requires every block to be iterated at least once within a bounded group of iterations.
5 Numerical Experiments
Experiments compare original and accelerated MU, HALS, and projected-gradient methods with ANLS on dense image and sparse text datasets. Accelerated methods generally improve efficiency, with the strongest gains differing between dense and sparse settings.
- Dense Matrices - Images Datasets: Dense image results also preserve the baseline ordering that PG outperforms MU, ANLS outperforms MU and PG, and HALS performs best among the original methods.These comparisons are reported as confirmations of earlier observations.
- Dense Matrices - Images Datasets: Dense image results show A-MU and A-PG outperforming their original methods in all cases, while A-HALS is the most efficient tested algorithm.A-MU performs better than A-PG and only slightly worse than ANLS, often reducing error as rapidly during initial iterations.
- Sparse Matrices - Text Datasets: Sparse text results show accelerated methods are generally more efficient, with A-MU and A-PG initially converging faster than ANLS and obtaining better final solutions.A-MU, HALS, and A-HALS have the fastest initial convergence rates; HALS and A-HALS generate the best solutions in all cases.
- Sparse Matrices - Text Datasets: On sparse matrices, A-HALS does not always improve final solutions over HALS, although its initial convergence is at least as fast in every case.HALS already performs remarkably well on sparse data, and A-HALS improves final solutions on half of the datasets.
6 Conclusion
The paper accelerates MU and HALS by repeating cheaper updates after expensive matrix products, extends the idea to projected gradients, and evaluates the resulting methods on dense and sparse data.
- Conclusion: The proposed accelerations exploit expensive matrix products by repeating a safeguarded fixed number of cheaper factor updates.The approach preserves the convergence properties of the original algorithms and can also improve projected gradient.
- Conclusion: Experiments show accelerated variants significantly outperform the original algorithms, especially on dense matrices, while competing favorably with ANLS.The authors identify more sophisticated selection of inner-iteration counts as future work.
- Conclusion: The acceleration technique can in principle be applied to most NMF algorithms.The paper demonstrates this extension specifically for Lin’s projected gradient method.