IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v82y2022i2d10.1007_s10898-021-01074-3.html
   My bibliography  Save this article

Four algorithms to solve symmetric multi-type non-negative matrix tri-factorization problem

Author

Listed:
  • Rok Hribar

    (Jožef Stefan Institute
    Jožef Stefan International Postgraduate School)

  • Timotej Hrga

    (University of Ljubljana)

  • Gregor Papa

    (Jožef Stefan Institute)

  • Gašper Petelin

    (Jožef Stefan Institute
    Jožef Stefan International Postgraduate School)

  • Janez Povh

    (University of Ljubljana
    Institute of Mathematics, Physics and Mechanics)

  • Nataša Pržulj

    (Institute of Mathematics, Physics and Mechanics
    University College London
    Barcelona Supercomputing Center)

  • Vida Vukašinović

    (Jožef Stefan Institute)

Abstract

In this paper, we consider the symmetric multi-type non-negative matrix tri-factorization problem (SNMTF), which attempts to factorize several symmetric non-negative matrices simultaneously. This can be considered as a generalization of the classical non-negative matrix tri-factorization problem and includes a non-convex objective function which is a multivariate sixth degree polynomial and a has convex feasibility set. It has a special importance in data science, since it serves as a mathematical model for the fusion of different data sources in data clustering. We develop four methods to solve the SNMTF. They are based on four theoretical approaches known from the literature: the fixed point method (FPM), the block-coordinate descent with projected gradient (BCD), the gradient method with exact line search (GM-ELS) and the adaptive moment estimation method (ADAM). For each of these methods we offer a software implementation: for the former two methods we use Matlab and for the latter Python with the TensorFlow library. We test these methods on three data-sets: the synthetic data-set we generated, while the others represent real-life similarities between different objects. Extensive numerical results show that with sufficient computing time all four methods perform satisfactorily and ADAM most often yields the best mean square error (MSE). However, if the computation time is limited, FPM gives the best MSE because it shows the fastest convergence at the beginning. All data-sets and codes are publicly available on our GitLab profile.

Suggested Citation

  • Rok Hribar & Timotej Hrga & Gregor Papa & Gašper Petelin & Janez Povh & Nataša Pržulj & Vida Vukašinović, 2022. "Four algorithms to solve symmetric multi-type non-negative matrix tri-factorization problem," Journal of Global Optimization, Springer, vol. 82(2), pages 283-312, February.
    • Handle: RePEc:spr:jglopt:v:82:y:2022:i:2:d:10.1007_s10898-021-01074-3
    DOI: 10.1007/s10898-021-01074-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-021-01074-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-021-01074-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. P. Tseng, 2001. "Convergence of a Block Coordinate Descent Method for Nondifferentiable Minimization," Journal of Optimization Theory and Applications, Springer, vol. 109(3), pages 475-494, June.
    2. Shota Saito & Yoshito Hirata & Kazutoshi Sasahara & Hideyuki Suzuki, 2015. "Tracking Time Evolution of Collective Attention Clusters in Twitter: Time Evolving Nonnegative Matrix Factorisation," PLOS ONE, Public Library of Science, vol. 10(9), pages 1-17, September.
    3. Andrej Čopar & Blaž Zupan & Marinka Zitnik, 2019. "Fast optimization of non-negative matrix tri-factorization," PLOS ONE, Public Library of Science, vol. 14(6), pages 1-15, June.
    4. Soodabeh Asadi & Janez Povh, 2021. "A Block Coordinate Descent-Based Projected Gradient Algorithm for Orthogonal Non-Negative Matrix Factorization," Mathematics, MDPI, vol. 9(5), pages 1-22, March.
    5. Peter Dickinson & Luuk Gijben, 2014. "On the computational complexity of membership problems for the completely positive cone and its dual," Computational Optimization and Applications, Springer, vol. 57(2), pages 403-415, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jun Yan & Jian Huang, 2012. "Model Selection for Cox Models with Time-Varying Coefficients," Biometrics, The International Biometric Society, vol. 68(2), pages 419-428, June.
    2. Vincent, Martin & Hansen, Niels Richard, 2014. "Sparse group lasso and high dimensional multinomial classification," Computational Statistics & Data Analysis, Elsevier, vol. 71(C), pages 771-786.
    3. Shuang Zhang & Xingdong Feng, 2022. "Distributed identification of heterogeneous treatment effects," Computational Statistics, Springer, vol. 37(1), pages 57-89, March.
    4. Jung, Yoon Mo & Whang, Joyce Jiyoung & Yun, Sangwoon, 2020. "Sparse probabilistic K-means," Applied Mathematics and Computation, Elsevier, vol. 382(C).
    5. Jinyan Fan & Jiawang Nie & Anwa Zhou, 2019. "Completely Positive Binary Tensors," Mathematics of Operations Research, INFORMS, vol. 44(3), pages 1087-1100, August.
    6. Seunghwan Lee & Sang Cheol Kim & Donghyeon Yu, 2023. "An efficient GPU-parallel coordinate descent algorithm for sparse precision matrix estimation via scaled lasso," Computational Statistics, Springer, vol. 38(1), pages 217-242, March.
    7. Le Thi Khanh Hien & Duy Nhat Phan & Nicolas Gillis, 2022. "Inertial alternating direction method of multipliers for non-convex non-smooth optimization," Computational Optimization and Applications, Springer, vol. 83(1), pages 247-285, September.
    8. Victor Chernozhukov & Whitney K. Newey & Victor Quintas-Martinez & Vasilis Syrgkanis, 2021. "Automatic Debiased Machine Learning via Riesz Regression," Papers 2104.14737, arXiv.org, revised Mar 2024.
    9. Jiahe Lin & George Michailidis, 2019. "Approximate Factor Models with Strongly Correlated Idiosyncratic Errors," Papers 1912.04123, arXiv.org.
    10. Emilie Chouzenoux & Jean-Christophe Pesquet & Audrey Repetti, 2016. "A block coordinate variable metric forward–backward algorithm," Journal of Global Optimization, Springer, vol. 66(3), pages 457-485, November.
    11. Badenbroek, Riley & de Klerk, Etienne, 2022. "An analytic center cutting plane method to determine complete positivity of a matrix," Other publications TiSEM 088da653-b943-4ed0-9720-6, Tilburg University, School of Economics and Management.
    12. Immanuel M. Bomze & Vaithilingam Jeyakumar & Guoyin Li, 2018. "Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations," Journal of Global Optimization, Springer, vol. 71(3), pages 551-569, July.
    13. Chen, Kun & Huang, Rui & Chan, Ngai Hang & Yau, Chun Yip, 2019. "Subgroup analysis of zero-inflated Poisson regression model with applications to insurance data," Insurance: Mathematics and Economics, Elsevier, vol. 86(C), pages 8-18.
    14. Paul Tseng, 2004. "An Analysis of the EM Algorithm and Entropy-Like Proximal Point Methods," Mathematics of Operations Research, INFORMS, vol. 29(1), pages 27-44, February.
    15. Omer, E. & Guetta, R. & Ioslovich, I. & Gutman, P.O. & Borshchevsky, M., 2008. "“Energy Tower” combined with pumped storage and desalination: Optimal design and analysis," Renewable Energy, Elsevier, vol. 33(4), pages 597-607.
    16. Dewei Zhang & Yin Liu & Sam Davanloo Tajbakhsh, 2022. "A First-Order Optimization Algorithm for Statistical Learning with Hierarchical Sparsity Structure," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1126-1140, March.
    17. Nicholson, William B. & Matteson, David S. & Bien, Jacob, 2017. "VARX-L: Structured regularization for large vector autoregressions with exogenous variables," International Journal of Forecasting, Elsevier, vol. 33(3), pages 627-651.
    18. Brian Dandurand & Margaret M. Wiecek, 2016. "Quadratic scalarization for decomposed multiobjective optimization," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(4), pages 1071-1096, October.
    19. Yuzhu Wang & Akihiro Tanaka & Akiko Yoshise, 2021. "Polyhedral approximations of the semidefinite cone and their application," Computational Optimization and Applications, Springer, vol. 78(3), pages 893-913, April.
    20. David Degras, 2021. "Sparse group fused lasso for model segmentation: a hybrid approach," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 15(3), pages 625-671, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:82:y:2022:i:2:d:10.1007_s10898-021-01074-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.