Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization
- PDF / 535,732 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 52 Downloads / 251 Views
Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization Yong-Yong Chen1 · Fang-Fang Xu1 Received: 26 November 2019 / Revised: 7 June 2020 / Accepted: 3 September 2020 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Orthogonal nonnegative matrix factorization (ONMF) is widely used in blind image separation problem, document classification, and human face recognition. The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method. When the given matrix is huge, the cost of computation and communication is too high. Therefore, ONMF becomes challenging in the large-scale setting. The random projection is an efficient method of dimensionality reduction. In this paper, we apply the random projection to ONMF and propose two randomized algorithms. Numerical experiments show that our proposed algorithms perform well on both simulated and real data. Keywords Orthogonal nonnegative matrix factorization · Random projection method · Dimensionality reduction · Augmented lagrangian method · Hierarchical alternating least squares algorithm Mathematics Subject Classification 68W20 · 90C06
1 Introduction Orthogonal nonnegative matrix factorization (ONMF) works well at blind image separation problem, document classification, and human face recognition [1–5]. In this paper, the following orthogonal nonnegative matrix factorization model is considered:
This work was supported in part by the National Natural Science Foundation of China (No. 11901359), and Shandong Provincial Natural Science Foundation (No. ZR2019QA017).
B
Fang-Fang Xu [email protected] Yong-Yong Chen [email protected]
1
College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao 266590, Shandong, China
123
Y.-Y. Chen. F.-F. Xu
minU ,V s.t.
M − U V 2F U 0, V 0, V V = Ik ,
(1)
where M ∈ Rm×n is known, U ∈ Rm×k is the centroid matrix, and V ∈ Rn×k is the cluster assignment matrix. The inequality U 0 is element-wise, which means Ui j 0 for all entries (i, j). Likewise, the inequality V 0 means Vi j 0. Note that the orthogonal constraint V V = Ik is imposed on the cluster assignment matrix V . The orthogonal constraint set is called the Stiefel manifold. Therefore, Model (1) is actually an optimization problem on the Stiefel manifold [6]. ONMF is much more difficult than nonnegative matrix factorization. Recently, extensive researches have already been conducted on ONMF and several efficient algorithms have been put forward [7–12]. Traditionally, ONMF algorithm strictly satisfied nonnegativity constraint in each iteration while achieving orthogonality at the limit. Pompili et al. [13] proposed a new algorithm from the opposite side. It satisfied orthogonality constraint in each iteration, while obtaining nonnegativity asymptotically. All the algorithms mentioned above treat each ma
Data Loading...
