Non-negative Matrix Factorization with Low-Dimension Polytope Approximation

Non-negative Matrix Factorization with Low-Dimension Polytope Approximation

蕭詠耀(Yung-Yao Hsiao)

指導教授 ： 卓建宏

國立中正大學/理學院/數學系應用數學研究所/碩士(2013年)

並列摘要

Non-negative matrix factorization (NMF) has been shown to be a useful decomposition for multivariate data in recent decades. In this study, we will focus on the numerical algorithm for NMF which is recast as the problem of approximating a polytope on the probability simplex by another polytope with fewer facets. Chu and Lin [1] proposed an algorithm for computing the proximity map which is more convenient to nd the unique global minimum per iteration than the existing methods. Nevertheless, their method is less competitive in speed with other methods though one could have much smaller residual errors in factorization. To improve the eciency of Chu-Lin method, we program the algorithm by C language, which successfully speeds up the computation than the one given in [1]. We also compare the computational cost for di erent settings of matrices dimensions.

並列關鍵字

polytope approximation ； non-negative matrix factorization ； probability simplex

參考文獻

[1] Moody T. Chu and Matthew M. Lin. Low-dimensional polytope approximation and its applications to nonnegative matrix factorization. 2008.

[2] Sanjeev Arora, Rong Ge, and Ankur Moitra. Learning topic models

[3] J. Larsen Schmidt, M.N. and F.T. Hsiao. Wind noise reduction using non-negative sparse coding. Machine Learning for Signal Processing, IEEE Workshop, page 431 to 436, 2007.

[4] Chih-Jen Lin. On the convergence of multiplicative update algorithms for nonnegative matrix factorization. IEEE Transactions on Neural Networks 18 (6), page 1589 to 1596, November 2007.

[5] Hyunsoo Kim and Haesun Park. Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method. SIAM Journal on Matrix Analysis and Applications 30 (2),