Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework

By Jingu Kim, Yunlong He, Haesun Park. Journal of Global Optimization, 2013

375 citations recorded by the source corpus.

We review algorithms developed for nonnegative matrix factorization (NMF) and nonnegative tensor factorization (NTF) from a unified view based on the block coordinate descent (BCD) framework. NMF and NTF are low-rank approximation methods for matrices and tensors in which the low-rank factors are constrained to have only nonnegative elements. The nonnegativity constraints have been shown to enable natural interpretations and allow better solutions in numerous applications including text analysis, computer vision, and bioinformatics. However, the computation of NMF and NTF remains challenging and expensive due the constraints. Numerous algorithmic approaches have been proposed to efficiently compute NMF and NTF. The BCD framework in constrained non-linear optimization readily explains the theoretical convergence properties of several efficient NMF and NTF algorithms, which are consistent with experimental observations reported in literature. In addition, we discuss algorithms that do not fit in the BCD framework contrasting them from those based on the BCD framework. With insights acquired from the unified perspective, we also propose efficient algorithms for updating NMF when there is a small change in the reduced dimension or in the data. The effectiveness of the proposed updating algorithms are validated experimentally with synthetic and real-world data sets.

Subfields: Computational Mathematics, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/b13266190d4cce43d3a38af683dd5939efd3155d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Mechanics

In Signal Processing

Citations in the corpus

A Unified Algorithmic Framework for Block-Structured Optimization Involving Big Data: With applications in machine learning and signal processing (2015, methodology): “Practically, it has been used in emerging large-scale signal processing and machine learning applications, such as compressive sensing/sparse signal recovery [23], [24], matrix completion [25], [26], tensor decomposition [27], [28], to name just a few.”
SUSTain: Scalable Unsupervised Scoring for Tensors and its Application to Phenotyping (2018, methodology): “To assess the factors’ conciseness, we compare 3https://github.com/bdgp/staNMF their fit with the achieved fit of the real-valued model (NN CP-ALS), which is post-processed to achieve factor sparsity (as would be done by a practitioner).”
Greedy Algorithms for Cone Constrained Optimization with Convergence Guarantees (2017, background): “The gold standard in factorization problems is projected gradient descent with alternating minimization, see [29, 2, 31, 15].”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “A complete review of the algorithms for nonnegative matrix factorization (NMF) and nonnegative tensor factorization (NTF) based on the block coordinate descent (BCD) framework is available in Kim et al; [197].”
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update (2014, background): “The problem in (3.6) can be written in the form of (1.1) by letting In the literature, most existing algorithms for solving (3.6) update X and Y alternatingly; see the review paper [24] and the references therein.”
Inferring Population Structure and Admixture Proportions in Low-Depth NGS Data (2018, background): “However by setting η (q) ik = qik (QFF)ik and η (f) ik = fsk (FQQ)sk is equal to the multiplicative update rules (equation 35), where the steps are conservative enough to ensure non-negative entries for each update [33, 46].”
The Why and How of Nonnegative Matrix Factorization (2014, methodology): “…that this problem has a particular structure as it can be decomposed into p independent NNLS in r variables since Many algorithms exist to solve the NNLS problem, and NMF algorithms based on two-block coordinate descent diﬀer by which NNLS algorithm is used; see also, e.g., the discussion in [74].”
Using Topic Modeling Methods for Short-Text Data: A Comparative Analysis (2020, methodology): “• NMF is an unsupervised matrix factorization (linear algebraic) method that is able to perform both dimension reduction and clustering simultaneously (Berry and Browne, 2005; Kim et al., 2014).”
Generalized Low Rank Models (2014, methodology): “Hence a number of specialized algorithms and codes for fitting NNMF models are available [86, 91, 78, 80, 13, 79, 81].”
Outlier Detection for Text Data (2017, methodology): “Kim, He and Park [12] provide the general introduction to BCD technique and its application to NMF in detail.”