Nonnegative Matrix Factorization via Newton Iteration for Shared-Memory Systems

Main Article Content

Markus Flatz Marián Vajteršic

Abstract

Nonnegative Matrix Factorization (NMF) can be used to approximate a large nonnegative matrix as a product of two smaller nonnegative matrices. This paper shows in detail how an NMF algorithm based on Newton iteration can be derived utilizing the general Karush-Kuhn-Tucker (KKT) conditions for first-order optimality. This algorithm is suited for parallel execution on shared-memory systems. It was implemented and tested, delivering satisfactory speedup results.

Article Details

How to Cite
FLATZ, Markus; VAJTERŠIC, Marián. Nonnegative Matrix Factorization via Newton Iteration for Shared-Memory Systems. Proceedings of the Conference Algoritmy, [S.l.], p. 312-322, feb. 2016. Available at: <http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/algoritmy/article/view/420>. Date accessed: 22 sep. 2017.
Section
Articles

References

[1] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 7th ed., 2009.

[2] M. Chu, F. Diele, R. Plemmons, and S. Ragni, Optimality, Computation, and Interpretations of Nonnegative Matrix Factorizations, Unpublished Report, (2004).

[3] M. Flatz and M. Vajteršic, A parallel algorithm for Nonnegative Matrix Factorization based on Newton iteration, in Proceedings of the IASTED International Conference Parallel and Distributed Computing and Networks (PDCN 2013), ACTA Press, 2013, pp. 600–607.

[4] P. O. Hoyer., Non-negative matrix factorization with sparseness constraints, Journal of Machine Learning Research, 5 (2004), pp. 1457–1469.

[5] D. D. Lee and H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), pp. 788–791.

[6] G. Okša, M. Bečka, and M. Vajteršic, Nonnegative Matrix Factorization: Algorithms and Parallelization, Tech. Report 2010-05, University of Salzburg, Department of Computer Sciences, 2010.

[7] P. Paatero and U. Tapper, Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values, Environmetrics, 5 (1994), pp. 111–126.