IDEAS home Printed from https://ideas.repec.org/p/cor/louvco/2010059.html
   My bibliography  Save this paper

Nonnegative factorization and the maximum edge biclique problem

Author

Listed:
  • GILLIS, Nicolas

    (Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium)

  • GLINEUR, François

    (Université catholique de Louvain, CORE, B-1348 Louvain-la-Neuve, Belgium)

Abstract

Nonnegative matrix factorization (NMF) is a data analysis technique based on the approximation of a nonnegative matrix with a product of two nonnegative factors, which allows compression and interpretation of nonnegative data. In this paper, we study the case of rank-one factorization and show that when the matrix to be factored is not required to be nonnegative, the corresponding problem (R1NF) becomes NP-hard. This sheds new light on the complexity of NMF since any algorithm for fixed-rank NMF must be able to solve at least implicitly such rank-one subproblems. Our proof relies on a reduction of the maximum edge biclique problem to R1NF. We also link stationary points of R1NF to feasible solutions of the biclique problem, which allows us to design a new type of biclique finding algorithm based on the application of a block-coordinate descent scheme to R1NF. We show that this algorithm, whose algorithmic complexity per iteration is proportional to the number of edges in the graph, is guaranteed to converge to a biclique and that it performs competitively with existing methods on random graphs and text mining datasets.

Suggested Citation

  • GILLIS, Nicolas & GLINEUR, François, 2010. "Nonnegative factorization and the maximum edge biclique problem," LIDAM Discussion Papers CORE 2010059, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    • Handle: RePEc:cor:louvco:2010059
    as

    Download full text from publisher

    File URL: https://sites.uclouvain.be/core/publications/coredp/coredp2010.html
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Berry, Michael W. & Browne, Murray & Langville, Amy N. & Pauca, V. Paul & Plemmons, Robert J., 2007. "Algorithms and applications for approximate nonnegative matrix factorization," Computational Statistics & Data Analysis, Elsevier, vol. 52(1), pages 155-173, September.
    2. Peeters, M.J.P., 2003. "The maximum edge biclique problem is NP-complete," Other publications TiSEM 3e340431-37b3-4bc5-9b14-9, Tilburg University, School of Economics and Management.
    3. Karthik Devarajan, 2008. "Nonnegative Matrix Factorization: An Analytical and Interpretive Tool in Computational Biology," PLOS Computational Biology, Public Library of Science, vol. 4(7), pages 1-12, July.
    4. GILLIS, Nicolas & GLINEUR, François, 2009. "Using underapproximations for sparse nonnegative matrix factorization," LIDAM Discussion Papers CORE 2009006, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. GILLIS, Nicolas & GLINEUR, François, 2011. "Accelerated multiplicative updates and hierarchical als algorithms for nonnegative matrix factorization," LIDAM Discussion Papers CORE 2011030, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. GILLIS, Nicolas & GLINEUR, François, 2010. "On the geometric interpretation of the nonnegative rank," LIDAM Discussion Papers CORE 2010051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. GILLIS, Nicolas & GLINEUR, François, 2010. "Low-rank matrix approximation with weights or missing data is NP-hard," LIDAM Discussion Papers CORE 2010075, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Norikazu Takahashi & Ryota Hibi, 2014. "Global convergence of modified multiplicative updates for nonnegative matrix factorization," Computational Optimization and Applications, Springer, vol. 57(2), pages 417-440, March.
    5. Jingu Kim & Yunlong He & Haesun Park, 2014. "Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework," Journal of Global Optimization, Springer, vol. 58(2), pages 285-319, February.
    6. Takehiro Sano & Tsuyoshi Migita & Norikazu Takahashi, 2022. "A novel update rule of HALS algorithm for nonnegative matrix factorization and Zangwill’s global convergence," Journal of Global Optimization, Springer, vol. 84(3), pages 755-781, November.
    7. Nicolas Gillis & François Glineur, 2014. "A continuous characterization of the maximum-edge biclique problem," Journal of Global Optimization, Springer, vol. 58(3), pages 439-464, March.
    8. Norikazu Takahashi & Jiro Katayama & Masato Seki & Jun’ichi Takeuchi, 2018. "A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization," Computational Optimization and Applications, Springer, vol. 71(1), pages 221-250, September.

    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. Jingu Kim & Yunlong He & Haesun Park, 2014. "Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework," Journal of Global Optimization, Springer, vol. 58(2), pages 285-319, February.
    2. GILLIS, Nicolas & GLINEUR, François, 2010. "On the geometric interpretation of the nonnegative rank," LIDAM Discussion Papers CORE 2010051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. GILLIS, Nicolas & GLINEUR, François, 2011. "Accelerated multiplicative updates and hierarchical als algorithms for nonnegative matrix factorization," LIDAM Discussion Papers CORE 2011030, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    4. Paul Fogel & Yann Gaston-Mathé & Douglas Hawkins & Fajwel Fogel & George Luta & S. Stanley Young, 2016. "Applications of a Novel Clustering Approach Using Non-Negative Matrix Factorization to Environmental Research in Public Health," IJERPH, MDPI, vol. 13(5), pages 1-14, May.
    5. Jianfei Cao & Han Yang & Jianshu Lv & Quanyuan Wu & Baolei Zhang, 2023. "Estimating Soil Salinity with Different Levels of Vegetation Cover by Using Hyperspectral and Non-Negative Matrix Factorization Algorithm," IJERPH, MDPI, vol. 20(4), pages 1-15, February.
    6. Takehiro Sano & Tsuyoshi Migita & Norikazu Takahashi, 2022. "A novel update rule of HALS algorithm for nonnegative matrix factorization and Zangwill’s global convergence," Journal of Global Optimization, Springer, vol. 84(3), pages 755-781, November.
    7. 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.
    8. Sumit Kunnumkal & Kalyan Talluri, 2019. "Choice Network Revenue Management Based on New Tractable Approximations," Transportation Science, INFORMS, vol. 53(6), pages 1591-1608, November.
    9. Shanika L Wickramasuriya & Berwin A Turlach & Rob J Hyndman, 2019. "Optimal Non-negative Forecast Reconciliation," Monash Econometrics and Business Statistics Working Papers 15/19, Monash University, Department of Econometrics and Business Statistics.
    10. Alejandra Casado & Sergio Pérez-Peló & Jesús Sánchez-Oro & Abraham Duarte, 2022. "A GRASP algorithm with Tabu Search improvement for solving the maximum intersection of k-subsets problem," Journal of Heuristics, Springer, vol. 28(1), pages 121-146, February.
    11. Lei Zhu & Fernando Soldevila & Claudio Moretti & Alexandra d’Arco & Antoine Boniface & Xiaopeng Shao & Hilton B. Aguiar & Sylvain Gigan, 2022. "Large field-of-view non-invasive imaging through scattering layers using fluctuating random illumination," Nature Communications, Nature, vol. 13(1), pages 1-6, December.
    12. Yoshi Fujiwara & Rubaiyat Islam, 2021. "Bitcoin's Crypto Flow Network," Papers 2106.11446, arXiv.org, revised Jul 2021.
    13. Yin Liu & Sam Davanloo Tajbakhsh, 2023. "Stochastic Composition Optimization of Functions Without Lipschitz Continuous Gradient," Journal of Optimization Theory and Applications, Springer, vol. 198(1), pages 239-289, July.
    14. Immanuel Bomze & Werner Schachinger & Gabriele Uchida, 2012. "Think co(mpletely)positive ! Matrix properties, examples and a clustered bibliography on copositive optimization," Journal of Global Optimization, Springer, vol. 52(3), pages 423-445, March.
    15. Hiroyasu Abe & Hiroshi Yadohisa, 2019. "Orthogonal nonnegative matrix tri-factorization based on Tweedie distributions," 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. 13(4), pages 825-853, December.
    16. Derval, Guillaume & Schaus, Pierre, 2022. "Maximal-Sum submatrix search using a hybrid contraint programming/linear programming approach," European Journal of Operational Research, Elsevier, vol. 297(3), pages 853-865.
    17. Guowei Yang & Lin Zhang & Minghua Wan, 2022. "Exponential Graph Regularized Non-Negative Low-Rank Factorization for Robust Latent Representation," Mathematics, MDPI, vol. 10(22), pages 1-20, November.
    18. Minghao Li & Zicheng Zhang & Qianrong Wang & Yan Yi & Baosheng Li, 2022. "Integrated cohort of esophageal squamous cell cancer reveals genomic features underlying clinical characteristics," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    19. José M. Maisog & Andrew T. DeMarco & Karthik Devarajan & Stanley Young & Paul Fogel & George Luta, 2021. "Assessing Methods for Evaluating the Number of Components in Non-Negative Matrix Factorization," Mathematics, MDPI, vol. 9(22), pages 1-13, November.
    20. Sumit Kunnumkal & Kalyan Talluri, 2012. "A New Compact Linear Programming Formulation for Choice Network Revenue Management," Working Papers 677, Barcelona School of Economics.

    More about this item

    Keywords

    nonnegative matrix factorization; rank-one factorization; maximum edge biclique problem; algorithmic complexity; biclique finding algorithm;
    All these keywords.

    JEL classification:

    • A23 - General Economics and Teaching - - Economic Education and Teaching of Economics - - - Graduate
    • Q25 - Agricultural and Natural Resource Economics; Environmental and Ecological Economics - - Renewable Resources and Conservation - - - Water
    • C35 - Mathematical and Quantitative Methods - - Multiple or Simultaneous Equation Models; Multiple Variables - - - Discrete Regression and Qualitative Choice Models; Discrete Regressors; Proportions
    • C59 - Mathematical and Quantitative Methods - - Econometric Modeling - - - Other

    Statistics

    Access and download statistics

    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:cor:louvco:2010059. 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: Alain GILLIS (email available below). General contact details of provider: https://edirc.repec.org/data/coreebe.html .

    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.