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

Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization

Author

Listed:
  • GILLIS, Nicolas
  • GLINEUR, François

Abstract

Nonnegative matrix factorization (NMF) is a data analysis technique used in a great variety of applications such as text mining, image processing, hyperspectral data analysis, computational biology, and clustering. In this paper, we consider two well-known algorithms designed to solve NMF problems, namely the multiplicative updates of Lee and Seung and the hierarchical alternating least squares of Cichocki et al. We propose a simple way to significantly accelerate their convergence, based on a careful analysis of the computational cost needed at each iteration. This acceleration technique can also be applied to other algorithms, which we illustrate on the projected gradient method of Lin. The efficiency of the accelerated algorithms is empirically demonstrated on image and text datasets, and compares favorably with a state-of-the-art alternating nonnegative least squares algorithm. Finally, we provide a theoretical argument based on the properties of NMF and its solutions that explains in particular the very good performance of HALS and its accelerated version observed in our numerical experiments.
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • GILLIS, Nicolas & GLINEUR, François, 2012. "Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization," LIDAM Reprints CORE 2389, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
  • Handle: RePEc:cor:louvrp:2389
    DOI: 10.1162/NECO_a_00256
    Note: In : Neural Computation, 24, 1085-1105, 2012
    as

    Download full text from publisher

    To our knowledge, this item is not available for download. To find whether it is available, there are three options:
    1. Check below whether another version of this item is available online.
    2. Check on the provider's web page whether it is in fact available.
    3. Perform a search for a similarly titled item that would be available.

    Other versions of this item:

    References listed on IDEAS

    as
    1. GILLIS, Nicolas & GLINEUR, François, 2008. "Nonnegative factorization and the maximum edge biclique problem," LIDAM Discussion Papers CORE 2008064, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. Pierre-Philippe Combes & Thierry Mayer & Jacques-François Thisse, 2008. "Economic Geography: The Integration of Regions and Nations," Université Paris1 Panthéon-Sorbonne (Post-Print and Working Papers) hal-00311000, HAL.
    3. 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.
    4. Belleflamme,Paul & Peitz,Martin, 2010. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9780521681599, November.
    5. Duranton, Gilles & Martin, Philippe & Mayer, Thierry & Mayneris, Florian, 2010. "The Economics of Clusters: Lessons from the French Experience," OUP Catalogue, Oxford University Press, number 9780199592203, December.
    6. Huriot,Jean-Marie & Thisse,Jacques-François (ed.), 2009. "Economics of Cities," Cambridge Books, Cambridge University Press, number 9780521118279.
    7. Belleflamme,Paul & Peitz,Martin, 2015. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9781107069978.
    8. 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.
    9. Belleflamme,Paul & Peitz,Martin, 2015. "Industrial Organization," Cambridge Books, Cambridge University Press, number 9781107687899.
    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. GAHUNGU, Joachim & SMEERS, Yves, 2011. "A real options model for electricity capacity expansion," LIDAM Discussion Papers CORE 2011044, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. 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.
    3. Lei Yang, 2024. "Proximal Gradient Method with Extrapolation and Line Search for a Class of Non-convex and Non-smooth Problems," Journal of Optimization Theory and Applications, Springer, vol. 200(1), pages 68-103, January.
    4. GABSZEWICZ, Jean J. & VAN YPERSELE, Tanguy & ZANAJ, Skerdilajda, 2011. "Does the seller of a house facing a large number of buyers always decrease its price when its first offer is rejected?," LIDAM Discussion Papers CORE 2011049, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Gillis, Nicolas & Glineur, François & Tuyttens, Daniel & Vandaele, Arnaud, 2015. "Heuristics for exact nonnegative matrix factorization," LIDAM Discussion Papers CORE 2015006, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. VAN VYVE, Mathieu, 2011. "Linear prices for non-convex electricity markets: models and algorithms," LIDAM Discussion Papers CORE 2011050, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Arnaud Vandaele & François Glineur & Nicolas Gillis, 2018. "Algorithms for positive semidefinite factorization," Computational Optimization and Applications, Springer, vol. 71(1), pages 193-219, September.
    10. 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.
    11. CHANDER, Parkash & TULKENS, Henry, 2011. "The kyoto Protocol, the Copenhagen Accord, the Cancun Agreements, and beyond: an economic and game theoretical exploration and interpretation," LIDAM Discussion Papers CORE 2011051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    12. Rundong Du & Da Kuang & Barry Drake & Haesun Park, 2017. "DC-NMF: nonnegative matrix factorization based on divide-and-conquer for fast clustering and topic modeling," Journal of Global Optimization, Springer, vol. 68(4), pages 777-798, August.
    13. Duy Khuong Nguyen & Tu Bao Ho, 2017. "Accelerated parallel and distributed algorithm using limited internal memory for nonnegative matrix factorization," Journal of Global Optimization, Springer, vol. 68(2), pages 307-328, June.

    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. Dimitris Korobilis, 2013. "Var Forecasting Using Bayesian Variable Selection," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 28(2), pages 204-230, March.
    2. MANEZ, Juan A. & MONER-COLONQUES, Rafael & SEMPERE-MONERRIS, José J. & URBANO, Amparo, 2011. "Price differentials among brands in retail distribution: product quality and service quality," LIDAM Discussion Papers CORE 2011017, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Korobilis, Dimitris, 2013. "Hierarchical shrinkage priors for dynamic regressions with many predictors," International Journal of Forecasting, Elsevier, vol. 29(1), pages 43-59.
    4. 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).
    5. Bruno Van Pottelsberghe & Pierre M. Picard, 2011. "Patent office Governance and Patent System Quality," Working Papers ECARES ECARES 2011-007, ULB -- Universite Libre de Bruxelles.
    6. MAULEON, Ana & MOLIS, Elena & VANNETELBOSCH, Vincent & VERGOTE, Wouter, 2011. "Absolutely stable roommate problems," LIDAM Discussion Papers CORE 2011029, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    7. GAHUNGU, Joachim & SMEERS, Yves, 2011. "Sufficient and necessary conditions for perpetual multi-assets exchange options," LIDAM Discussion Papers CORE 2011035, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    8. FLEURBAEY, Marc & SCHOKKAERT, Erik, 2011. "Equity in health and health care," LIDAM Discussion Papers CORE 2011026, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    9. Pierre Pestieau & Gregory Ponthiere, 2012. "The Public Economics of Increasing Longevity," Hacienda Pública Española / Review of Public Economics, IEF, vol. 200(1), pages 41-74, March.
    10. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2012. "A unifying framework for the problem of adjudicating conflicting claims," Journal of Mathematical Economics, Elsevier, vol. 48(2), pages 107-114.
    11. Bocart, Fabian Y.R.P. & Hafner, Christian M., 2012. "Econometric analysis of volatile art markets," Computational Statistics & Data Analysis, Elsevier, vol. 56(11), pages 3091-3104.
    12. Bauwens, Luc & Dufays, Arnaud & Rombouts, Jeroen V.K., 2014. "Marginal likelihood for Markov-switching and change-point GARCH models," Journal of Econometrics, Elsevier, vol. 178(P3), pages 508-522.
    13. DEVOLDER, Olivier, 2011. "Stochastic first order methods in smooth convex optimization," LIDAM Discussion Papers CORE 2011070, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. CHANDER, Parkash & TULKENS, Henry, 2011. "The kyoto Protocol, the Copenhagen Accord, the Cancun Agreements, and beyond: an economic and game theoretical exploration and interpretation," LIDAM Discussion Papers CORE 2011051, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    15. Luc Bauwens & Christian M. Hafner & Diane Pierret, 2013. "Multivariate Volatility Modeling Of Electricity Futures," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 28(5), pages 743-761, August.
    16. GAHUNGU, Joachim & SMEERS, Yves, 2011. "A real options model for electricity capacity expansion," LIDAM Discussion Papers CORE 2011044, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    17. BAUWENS, Luc & HAFNER, Christian & LAURENT, Sébastien, 2011. "Volatility models," LIDAM Discussion Papers CORE 2011058, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
      • Bauwens, L. & Hafner, C. & Laurent, S., 2012. "Volatility Models," LIDAM Reprints ISBA 2012028, Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA).
      • Bauwens, L. & Hafner C. & Laurent, S., 2011. "Volatility Models," LIDAM Discussion Papers ISBA 2011044, Université catholique de Louvain, Institute of Statistics, Biostatistics and Actuarial Sciences (ISBA).
    18. GABSZEWICZ, Jean & TAROLA, Ornella, 2011. "Migration, wage differentials and fiscal competition," LIDAM Discussion Papers CORE 2011065, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    19. GILLIS, Nicolas & GLINEUR, François, 2010. "A multilevel approach for nonnegative matrix factorization," LIDAM Discussion Papers CORE 2010047, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Rombouts, Jeroen & Stentoft, Lars & Violante, Franceso, 2014. "The value of multivariate model sophistication: An application to pricing Dow Jones Industrial Average options," International Journal of Forecasting, Elsevier, vol. 30(1), pages 78-98.

    More about this item

    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:louvrp:2389. 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.