Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework
Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework
复制标题
DOI：
10.1007/s10898-013-0035-4
复制
发表时间：
2014-02-01
影响因子：
1.8
通讯作者：
Park, Haesun
中科院分区：
文献类型：
--
作者：
Kim, Jingu;He, Yunlong;Park, Haesun
我们回顾算法开发的非负矩阵分解（NMF）和非负张量分解（NTF）从一个统一的观点的基础上块坐标下降（BCD）框架。NMF和NTF是矩阵和张量的低秩近似方法，其中低秩因子被限制为只有非负元素。非负性约束已被证明可以实现自然解释，并在许多应用中提供更好的解决方案，包括文本分析，计算机视觉和生物信息学。然而，NMF和NTF的计算仍然具有挑战性和昂贵的，由于限制。已经提出了许多算法方法来有效地计算NMF和NTF。约束非线性优化中的BCD框架很容易解释几个有效的NMF和NTF算法的理论收敛性，这与文献中报道的实验观察结果一致。此外，我们讨论的算法，不适合在BCD框架对比他们从那些基础上的BCD框架。从统一的角度获得的见解，我们还提出了有效的算法更新NMF时，有一个小的变化，在减少的维度或数据。所提出的更新算法的有效性进行了实验验证与合成和真实世界的数据集。
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.