[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Off-diagonal symmetric nonnegative matrix factorization

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

Symmetric nonnegative matrix factorization (symNMF) is a variant of nonnegative matrix factorization (NMF) that allows handling symmetric input matrices and has been shown to be particularly well suited for clustering tasks. In this paper, we present a new model, dubbed off-diagonal symNMF (ODsymNMF), that does not take into account the diagonal entries of the input matrix in the objective function. ODsymNMF has three key advantages compared to symNMF. First, ODsymNMF is theoretically much more sound as there always exists an exact factorization of size at most n(n − 1)/2 where n is the dimension of the input matrix. Second, it makes more sense in practice as diagonal entries of the input matrix typically correspond to the similarity between an item and itself, not bringing much information. Third, it makes the optimization problem much easier to solve. In particular, it will allow us to design an algorithm based on coordinate descent that minimizes the component-wise ℓ1 norm between the input matrix and its approximation. We prove that this norm is much better suited for binary input matrices often encountered in practice. We also derive a coordinate descent method for the component-wise ℓ2 norm, and compare the two approaches with symNMF on synthetic and document datasets.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Abraham, B., Naomi, S.M.: Completely Positive Matrices. World Scientific (2003)

  2. Beck, A.: First-Order Methods in Optimization, vol. 25. SIAM (2017)

  3. Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences, vol. 9. SIAM (1994)

  4. Bertsekas, D.: Corrections for the book nonlinear programming (1999)

  5. Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Massachusetts (1999)

    Google Scholar 

  6. Borsdorf, R., Higham, N.J., Raydan, M.: Computing a nearest correlation matrix with factor structure. SIAM J. Matrix Anal. Applic. 31(5), 2603–2622 (2010)

    Article  MathSciNet  Google Scholar 

  7. Chen, Y., Rege, M., Dong, M., Hua, J.: Non-negative matrix factorization for semi-supervised data clustering. Knowl. Inf. Syst. 17(3), 355–379 (2008)

    Article  Google Scholar 

  8. Cichocki, A., Zdunek, R., Phan, A.H., Amari, S.i.: Nonnegative matrix and tensor factorizations: Applications to exploratory multi-way data analysis and blind source separation. Wiley (2009)

  9. Dickinson, P.J., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Applic. 57(2), 403–415 (2014)

    Article  MathSciNet  Google Scholar 

  10. Fortunato, S.: Community detection in graphs. Phys. Rep. 486 (3–5), 75–174 (2010)

    Article  MathSciNet  Google Scholar 

  11. Fu, X., Huang, K., Sidiropoulos, N.D., Ma, W.K.: Nonnegative matrix factorization for signal and data analytics: Identifiability, algorithms, and applications. IEEE Signal Process. Mag. 36(2), 59–80 (2019)

    Article  Google Scholar 

  12. Gillis, N.: The why and how of nonnegative matrix factorization. In: Suykens, J., Signoretto, M., Argyriou, A. (eds.) Regularization, Optimization, Kernels, and Support Vector Machines, chap. 12, pp 257–291. Chapman & Hall/CRC, Boca Raton (2014)

  13. Gillis, N., Hien, L.T.K., Leplat, V., Tan, V.Y.: Distributionally robust and multi-objective nonnegative matrix factorization. arXiv:1901.10757 (2019)

  14. Gillis, N., Vavasis, S.A.: On the complexity of robust pca and ℓ1-norm low-rank matrix approximation. Math. Oper. Res. 43(4), 1072–1084 (2018)

    Article  MathSciNet  Google Scholar 

  15. Gionis, A., Mannila, H., Tsaparas, P.: Clustering aggregation. ACM Trans. Knowl. Discov.from Data (TKDD) 1(1), 4–es (2007)

    Article  Google Scholar 

  16. Gurwitz, C.: Weighted median algorithms for l1 approximation. BIT 30(2), 301–310 (1990)

    Article  MathSciNet  Google Scholar 

  17. Huang, K., Sidiropoulos, N.D., Swami, A.: Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition. IEEE Trans. Signal Process. 62(1), 211–224 (2013)

    Article  MathSciNet  Google Scholar 

  18. Kuang, D., Ding, C., Park, H.: Symmetric nonnegative matrix factorization for graph clustering. In: Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 106–117. SIAM (2012)

  19. Kuang, D., Yun, S., Park, H.: Symnmf: Nonnegative low-rank approximation of a similarity matrix for graph clustering. J. Glob. Optim. 62(3), 545–574 (2015)

    Article  MathSciNet  Google Scholar 

  20. Long, B., Zhang, Z.M., Wu, X., Yu, P.S.: Relational clustering by symmetric convex coding. In: Proceedings of the 24th international conference on Machine learning, pp. 569–576. ACM (2007)

  21. Peng, Z., Wu, T., Xu, Y., Yan, M., Yin, W.: Coordinate-friendly structures, algorithms and applications. Ann. Math. Sci. Applic. 1(1), 57–119 (2016)

    MathSciNet  MATH  Google Scholar 

  22. Pham, Q.M., Lachmund, D., Hào, D. N.: Convergence of proximal algorithms with stepsize controls for non-linear inverse problems and application to sparse non-negative matrix factorization. Numerical Algorithms (2020)

  23. 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 

  24. Shi, Q., Sun, H., Lu, S., Hong, M., Razaviyayn, M.: Inexact block coordinate descent methods for symmetric nonnegative matrix factorization. IEEE Trans. Signal Process. 65(22), 5995–6008 (2017)

    Article  MathSciNet  Google Scholar 

  25. Strehl, A., Ghosh, J., Mooney, R.: Impact of similarity measures on web-page clustering. In: Workshop on Artificial Intelligence for Web Search (AAAI 2000), vol. 58, p. 64 (2000)

  26. Vandaele, A., Gillis, N., Lei, Q., Zhong, K., Dhillon, I.: Efficient and non-convex coordinate descent for symmetric nonnegative matrix factorization. IEEE Trans. Signal Process. 64(21), 5571–5584 (2016)

    Article  MathSciNet  Google Scholar 

  27. Wright, S.J.: Coordinate descent algorithms. Math. Program. 151(1), 3–34 (2015)

    Article  MathSciNet  Google Scholar 

  28. Yan, X., Guo, J., Liu, S., Cheng, X., Wang, Y.: Learning topics in short texts by non-negative matrix factorization on term correlation matrix. In: proceedings of the 2013 SIAM International Conference on Data Mining, pp. 749–757. SIAM (2013)

  29. Yang, Z., Hao, T., Dikmen, O., Chen, X., Oja, E.: Clustering by nonnegative matrix factorization using graph random walk. In: Advances in Neural Information Processing Systems, pp. 1079–1087 (2012)

  30. Zass, R., Shashua, A.: A unifying approach to hard and probabilistic clustering. In: Tenth IEEE International Conference on Computer Vision (ICCV’05), vol. 1, pp. 294–301. IEEE (2005)

  31. Zhang, Z., Li, T., Ding, C., Zhang, X.: Binary matrix factorization with applications. In: Seventh IEEE International Conference on Data Mining (ICDM 2007), pp. 391–400. IEEE (2007)

  32. Zhong, S., Ghosh, J.: Generative model-based document clustering: A comparative study. Knowl. Inf. Syst. 8(3), 374–384 (2005)

    Article  Google Scholar 

Download references

Funding

This work is supported by the Fonds de la Recherche Scientifique - FNRS and the Fonds Wetenschappelijk Onderzoek - Vlanderen (FWO) under EOS Project no O005318F-RG47, and by the European Research Council (ERC starting grant no 679515)

Author information

Authors and Affiliations

  1. Department of Mathematics and Operational Research, Faculté Polytechnique, Université de Mons, Rue de Houdain 9, 7000, Mons, Belgium

    François Moutier, Arnaud Vandaele & Nicolas Gillis

Authors
  1. François Moutier
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arnaud Vandaele
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nicolas Gillis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to François Moutier.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: The constrained weighted median problem

Appendix: The constrained weighted median problem

Algorithm 7 provides a pseudocode to compute the solution to the constrained weighted median problem:

$$ \min_{x \geq 0} {\sum}_{i} |a_{i} x - b_{i}|. $$

The algorithm works as follows:

  • The set S of breakpoints \(\frac {b_{i}}{a_{i}}\) is initialized for all i = 1,...,n such that ai≠ 0 (because when ai = 0, the contribution of the i th term in the objective function is a constant) and the vector a is then sorted and normalized according to the values in S,

  • As the values ai correspond to the slopes, the second step of the algorithm looks for the k th breakpoint for which we have \({\sum }_{i=1}^{k-1} a_{i} < {\sum }_{i=k}^{n} a_{i}\) and \({\sum }_{i=1}^{k} a_{i} \geq {\sum }_{i=k+1}^{n} a_{i}\). It corresponds to a global optimum since the slope on the left is negative, and on the right is nonnegative.

figure i

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Moutier, F., Vandaele, A. & Gillis, N. Off-diagonal symmetric nonnegative matrix factorization. Numer Algor 88, 939–963 (2021). https://doi.org/10.1007/s11075-020-01063-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-020-01063-9

Keywords

Search

Navigation