Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. https://archive.ics.uci.edu/ml/datasets/Pen-Based+Recognition+of+Handwritten+Digits

  2. http://www.cad.zju.edu.cn/home/dengcai/Data/FaceData.html.

  3. http://www.kasrl.org/jaffe.html.

  4. http://featureselection.asu.edu/datasets.php.

References

  1. Choi, S.: Algorithms for orthogonal nonnegative matrix factorization. IEEE International Joint Conference on Neural Networks. pp. 1828–1832. IEEE Press, Hong Kong (2008)

  2. Ding, C., Li, T., Peng, W., Park, H.: Orthogonal nonnegative matrix \(t\)-factorizations for clustering. In: Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 126–135. ACM Press, Philadelphia (2006)

  3. Li, X., Cui, G., Dong, Y.: Discriminative and orthogonal subspace constraints-based nonnegative matrix factorization. ACM Trans. Intell. Syst. Technol. 9(6), Article No. 65 (2019)

  4. Mirzal, A.: Orthogonal nonnegative matrix factorization for blind image separation. In: International Visual Informatics Conference, pp. 25–35. Springer, Cham (2013)

  5. Tolic, D., Antulov-Fantulin, N., Kopriva, I.: A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering. Pattern Recogn. 82, 40–55 (2018)

    Article  Google Scholar 

  6. Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. 142(1), 397–434 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  7. Li, B., Zhou, G., Cichocki, A.: Two efficient algorithms for approximately orthogonal nonnegative matrix factorization. IEEE Signal Process. Lett. 22(7), 843–846 (2015)

    Article  Google Scholar 

  8. Li, P., Bu, J., Yang, Y., Ji, R., Chen, C., Cai, D.: Discriminative orthogonal nonnegative matrix factorization with flexibility for data representation. Expert Syst. Appl. 41(4), 1283–1293 (2017)

    Article  Google Scholar 

  9. Li, Z., Wu, X., Peng, H.: Nonnegative matrix factorization on orthogonal subspace. Pattern Recogn. Lett. 31(9), 905–911 (2010)

    Article  Google Scholar 

  10. Mirzal, A.: A convergent algorithm for orthogonal nonnegative matrix factorization. J. Comput. Appl. Math. 260(2), 149–166 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  11. Ye, J., Jin, Z.: Nonnegative matrix factorization on orthogonal subspace with smoothed \(L_0\) norm constrained. In: Yang, J., Fang, F., Sun, C. (eds.) Intelligent Science and Intelligent Data Engineering. IScIDE 2012. Lecture Notes in Computer Science, vol. 7751. Springer, Berlin (2013)

  12. Yoo, J., Choi, S.: Orthogonal nonnegative matrix factorization: multiplicative updates on Stiefel manifolds. In: Yang, J., Fang, F., Sun, C. (eds.) Intelligent Data Engineering and Automated Learning–IDEAL 2008, vol. 5326, pp. 140–147. Springer, Daejeon (2008)

    Chapter  Google Scholar 

  13. Pompili, F., Gillis, N., Absil, P.A., Glineur, F.: Two algorithms for orthogonal nonnegative matrix factorization with application to clustering. Neurocomputing 141, 15–25 (2014)

    Article  Google Scholar 

  14. Jin, Q.G., Liang, G.L.: Fast hierarchical alternating nonnegative least squares algorithm for nonnegative matrix factorization. Comput. Simul. 29(11), 174–185 (2012)

    Google Scholar 

  15. Kimura, K., Kudo, M., Tanaka, Y.: A column-wise update algorithm for nonnegative matrix factorization in Bregman divergence with an orthogonal constraint. Mach. Learn. 103(2), 285–306 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kimura, K., Tanaka, Y., Kudo, M.: A fast hierarchical alternating least squares algorithm for orthogonal nonnegative matrix factorization. In: Phung, D., Li, H. (eds.) Proceedings of the Sixth Asian Conference on Machine Learning, vol. 39, pp. 129–141 (2014)

  17. Drineas, P., Mahoney, M.W.: Randnla: randomized numerical linear algebra. Commun. ACM 59(6), 80–90 (2016)

    Article  Google Scholar 

  18. Erichson, N.B., Mendible, A., Wihlborn, S., Kutz, J.N.: Randomized nonnegative matrix factorization. Pattern Recogn. Lett. 104, 1–7 (2018)

    Article  Google Scholar 

  19. Erichson, N.B., Voronin, S., Brunton, S.L., Kutz, J.N.: Randomized matrix decompositions using R. J. Stat, Softw 89(11), 1–48 (2019). https://doi.org/10.18637/jss.v089.i11

  20. Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217–288 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ghashami, M., Liberty, E., Phillips, J.M., Woodruff, D.P.: Frequent directions: simple and deterministic matrix sketching. SIAM J. Comput. 45(5), 1762–1792 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  22. Tepper, M., Sapiro, G.: Compressed nonnegative matrix factorization is fast and accurate. IEEE Trans. Signal Process. 64(9), 2269–2283 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  23. Lin, C.J.: Projected gradient methods for nonnegative matrix factorization. Neural Comput. 19(10), 2756–2779 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  24. Lin, L., Liu, Z.Y.: An alternating projected gradient algorithm for nonnegative matrix factorization. Appl. Math. Comput. 217(24), 9997–10002 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  25. Dai, Y.H., Han, D.R., Yuan, X.M., Zhang, W.X.: A sequential updating scheme of the Lagrange multiplier for separable convex programming. Math. Comput. 86, 315–343 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  26. Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889–916 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Sun, D., Toh, K.C., Yang, L.: A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with \(4\)-type of constraints. SIAM J. Optim. 25, 882–915 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  28. Wu, Z., Li, M., Wang, D.Z.W., Han, D.: A symmetric alternating direction Method of multipliers for separable nonconvex minimization problems. Asia Pac. J. Oper. Res. 34(6), 1–27 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  29. Yang, J., Zhang, Y.: Alternating direction algorithms for \(\ell _1\)-problems in compressive sensing. SIAM J. Sci. Comput. 33(1), 250–278 (2009)

    Article  Google Scholar 

  30. Wang, X., Xie, X., Lu, L.: An effective initialization for orthogonal nonnegative matrix factorization. J. Comput. Math. 30(1), 34–46 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  31. Nie, F., Xu, D., Li, X.: Initialization independent clustering with actively self-training method. IEEE Trans. Syst. Man Cybern. B Cybern. 42(1), 17–27 (2012)

Download references

Acknowledgements

We would like to thank Prof. Zai-Wen Wen for the discussions on the random projection method. The authors are grateful to editor and anonymous referees for their detailed and valuable comments and suggestions.

Author information

Authors and Affiliations

  1. College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao, 266590, Shandong, China

    Yong-Yong Chen & Fang-Fang Xu

Authors
  1. Yong-Yong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Fang-Fang Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Fang-Fang Xu.

Additional information

This work was supported in part by the National Natural Science Foundation of China (No. 11901359), and Shandong Provincial Natural Science Foundation (No. ZR2019QA017).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chen, YY., Xu, FF. Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization. J. Oper. Res. Soc. China 11, 327–345 (2023). https://doi.org/10.1007/s40305-020-00322-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-020-00322-9

Keywords

Mathematics Subject Classification

Search

Navigation