A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization

Multiplicative update rules are a well-known computational method for nonnegative matrix factorization. Depending on the error measure between two matrices, various types of multiplicative update rules have been proposed so far. However, their convergence properties are not fully understood. This pa...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2018-09, Vol.71 (1), p.221-250
Main Authors: Takahashi, Norikazu, Katayama, Jiro, Seki, Masato, Takeuchi, Jun’ichi
Format: Article
Language:English
Subjects:
Convergence
Convex and Discrete Geometry
Error analysis
Factorization
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization
Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c382t-f9507295a0fbbe7c456608dc7c4a64777c3b70401c74bddb9d093012ca4746ae3
cites cdi_FETCH-LOGICAL-c382t-f9507295a0fbbe7c456608dc7c4a64777c3b70401c74bddb9d093012ca4746ae3
container_end_page 250
container_issue 1
container_start_page 221
container_title Computational optimization and applications
container_volume 71
creator Takahashi, Norikazu
Katayama, Jiro
Seki, Masato
Takeuchi, Jun’ichi
description Multiplicative update rules are a well-known computational method for nonnegative matrix factorization. Depending on the error measure between two matrices, various types of multiplicative update rules have been proposed so far. However, their convergence properties are not fully understood. This paper provides a sufficient condition for a general multiplicative update rule to have the global convergence property in the sense that any sequence of solutions has at least one convergent subsequence and the limit of any convergent subsequence is a stationary point of the optimization problem. Using this condition, it is proved that many of the existing multiplicative update rules have the global convergence property if they are modified slightly so that all variables take positive values. This paper also proposes new multiplicative update rules based on Kullback–Leibler, Gamma, and Rényi divergences. It is shown that these three rules have the global convergence property if the same modification as above is made.
doi_str_mv 10.1007/s10589-018-9997-y
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2015635524</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2015635524</sourcerecordid><originalsourceid>FETCH-LOGICAL-c382t-f9507295a0fbbe7c456608dc7c4a64777c3b70401c74bddb9d093012ca4746ae3</originalsourceid><addsrcrecordid>eNp1kEtLxDAUhYMoOI7-AHcB19WbR5tmOQy-YMCNrkOapiVDJ6lJO1h_vR0quHJ1L_eec-B8CN0SuCcA4iERyEuZASkzKaXIpjO0IrlgGS0lP0crkLTICgB2ia5S2gOAFIyukNvg0bvG2Rq3Xah0h03wRxtb643F2utuSi7h0ODD2A2u75zRgztaPPa1HiyOY2cTbkLEPnhv2-V50EN0X7jRZgjRfc_H4K_RRaO7ZG9-5xp9PD2-b1-y3dvz63azywwr6ZA1MgdBZa6hqSorDM-LAsrazJsuuBDCsEoAB2IEr-q6kjVIBoQazQUvtGVrdLfk9jF8jjYNah_GOBdJigLJC5bnlM8qsqhMDClF26g-uoOOkyKgTkTVQlTNRNWJqJpmD108adb61sa_5P9NP0vwe8Q</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2015635524</pqid></control><display><type>article</type><title>A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization</title><source>EBSCOhost Business Source Ultimate</source><source>ABI/INFORM Global</source><source>Springer Nature</source><creator>Takahashi, Norikazu ; Katayama, Jiro ; Seki, Masato ; Takeuchi, Jun’ichi</creator><creatorcontrib>Takahashi, Norikazu ; Katayama, Jiro ; Seki, Masato ; Takeuchi, Jun’ichi</creatorcontrib><description>Multiplicative update rules are a well-known computational method for nonnegative matrix factorization. Depending on the error measure between two matrices, various types of multiplicative update rules have been proposed so far. However, their convergence properties are not fully understood. This paper provides a sufficient condition for a general multiplicative update rule to have the global convergence property in the sense that any sequence of solutions has at least one convergent subsequence and the limit of any convergent subsequence is a stationary point of the optimization problem. Using this condition, it is proved that many of the existing multiplicative update rules have the global convergence property if they are modified slightly so that all variables take positive values. This paper also proposes new multiplicative update rules based on Kullback–Leibler, Gamma, and Rényi divergences. It is shown that these three rules have the global convergence property if the same modification as above is made.</description><identifier>ISSN: 0926-6003</identifier><identifier>EISSN: 1573-2894</identifier><identifier>DOI: 10.1007/s10589-018-9997-y</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Convergence ; Convex and Discrete Geometry ; Error analysis ; Factorization ; Management Science ; Mathematics ; Mathematics and Statistics ; Operations Research ; Operations Research/Decision Theory ; Optimization ; Statistics</subject><ispartof>Computational optimization and applications, 2018-09, Vol.71 (1), p.221-250</ispartof><rights>Springer Science+Business Media, LLC, part of Springer Nature 2018</rights><rights>Computational Optimization and Applications is a copyright of Springer, (2018). All Rights Reserved.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c382t-f9507295a0fbbe7c456608dc7c4a64777c3b70401c74bddb9d093012ca4746ae3</citedby><cites>FETCH-LOGICAL-c382t-f9507295a0fbbe7c456608dc7c4a64777c3b70401c74bddb9d093012ca4746ae3</cites><orcidid>0000-0001-8222-5593</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/2015635524/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/2015635524?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,776,780,11668,27903,27904,36039,44342,74642</link.rule.ids></links><search><creatorcontrib>Takahashi, Norikazu</creatorcontrib><creatorcontrib>Katayama, Jiro</creatorcontrib><creatorcontrib>Seki, Masato</creatorcontrib><creatorcontrib>Takeuchi, Jun’ichi</creatorcontrib><title>A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization</title><title>Computational optimization and applications</title><addtitle>Comput Optim Appl</addtitle><description>Multiplicative update rules are a well-known computational method for nonnegative matrix factorization. Depending on the error measure between two matrices, various types of multiplicative update rules have been proposed so far. However, their convergence properties are not fully understood. This paper provides a sufficient condition for a general multiplicative update rule to have the global convergence property in the sense that any sequence of solutions has at least one convergent subsequence and the limit of any convergent subsequence is a stationary point of the optimization problem. Using this condition, it is proved that many of the existing multiplicative update rules have the global convergence property if they are modified slightly so that all variables take positive values. This paper also proposes new multiplicative update rules based on Kullback–Leibler, Gamma, and Rényi divergences. It is shown that these three rules have the global convergence property if the same modification as above is made.</description><subject>Convergence</subject><subject>Convex and Discrete Geometry</subject><subject>Error analysis</subject><subject>Factorization</subject><subject>Management Science</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Operations Research</subject><subject>Operations Research/Decision Theory</subject><subject>Optimization</subject><subject>Statistics</subject><issn>0926-6003</issn><issn>1573-2894</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kEtLxDAUhYMoOI7-AHcB19WbR5tmOQy-YMCNrkOapiVDJ6lJO1h_vR0quHJ1L_eec-B8CN0SuCcA4iERyEuZASkzKaXIpjO0IrlgGS0lP0crkLTICgB2ia5S2gOAFIyukNvg0bvG2Rq3Xah0h03wRxtb643F2utuSi7h0ODD2A2u75zRgztaPPa1HiyOY2cTbkLEPnhv2-V50EN0X7jRZgjRfc_H4K_RRaO7ZG9-5xp9PD2-b1-y3dvz63azywwr6ZA1MgdBZa6hqSorDM-LAsrazJsuuBDCsEoAB2IEr-q6kjVIBoQazQUvtGVrdLfk9jF8jjYNah_GOBdJigLJC5bnlM8qsqhMDClF26g-uoOOkyKgTkTVQlTNRNWJqJpmD108adb61sa_5P9NP0vwe8Q</recordid><startdate>20180901</startdate><enddate>20180901</enddate><creator>Takahashi, Norikazu</creator><creator>Katayama, Jiro</creator><creator>Seki, Masato</creator><creator>Takeuchi, Jun’ichi</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>Q9U</scope><orcidid>https://orcid.org/0000-0001-8222-5593</orcidid></search><sort><creationdate>20180901</creationdate><title>A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization</title><author>Takahashi, Norikazu ; Katayama, Jiro ; Seki, Masato ; Takeuchi, Jun’ichi</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c382t-f9507295a0fbbe7c456608dc7c4a64777c3b70401c74bddb9d093012ca4746ae3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Convergence</topic><topic>Convex and Discrete Geometry</topic><topic>Error analysis</topic><topic>Factorization</topic><topic>Management Science</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Operations Research</topic><topic>Operations Research/Decision Theory</topic><topic>Optimization</topic><topic>Statistics</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Takahashi, Norikazu</creatorcontrib><creatorcontrib>Katayama, Jiro</creatorcontrib><creatorcontrib>Seki, Masato</creatorcontrib><creatorcontrib>Takeuchi, Jun’ichi</creatorcontrib><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ABI/INFORM Collection</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>ProQuest Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central Korea</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>ProQuest Science Journals</collection><collection>Engineering Database</collection><collection>Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering collection</collection><collection>ProQuest Central Basic</collection><jtitle>Computational optimization and applications</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Takahashi, Norikazu</au><au>Katayama, Jiro</au><au>Seki, Masato</au><au>Takeuchi, Jun’ichi</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization</atitle><jtitle>Computational optimization and applications</jtitle><stitle>Comput Optim Appl</stitle><date>2018-09-01</date><risdate>2018</risdate><volume>71</volume><issue>1</issue><spage>221</spage><epage>250</epage><pages>221-250</pages><issn>0926-6003</issn><eissn>1573-2894</eissn><abstract>Multiplicative update rules are a well-known computational method for nonnegative matrix factorization. Depending on the error measure between two matrices, various types of multiplicative update rules have been proposed so far. However, their convergence properties are not fully understood. This paper provides a sufficient condition for a general multiplicative update rule to have the global convergence property in the sense that any sequence of solutions has at least one convergent subsequence and the limit of any convergent subsequence is a stationary point of the optimization problem. Using this condition, it is proved that many of the existing multiplicative update rules have the global convergence property if they are modified slightly so that all variables take positive values. This paper also proposes new multiplicative update rules based on Kullback–Leibler, Gamma, and Rényi divergences. It is shown that these three rules have the global convergence property if the same modification as above is made.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10589-018-9997-y</doi><tpages>30</tpages><orcidid>https://orcid.org/0000-0001-8222-5593</orcidid></addata></record>
fulltext fulltext
identifier ISSN: 0926-6003
ispartof Computational optimization and applications, 2018-09, Vol.71 (1), p.221-250
issn 0926-6003
1573-2894
language eng
recordid cdi_proquest_journals_2015635524
source EBSCOhost Business Source Ultimate; ABI/INFORM Global; Springer Nature
subjects Convergence
Convex and Discrete Geometry
Error analysis
Factorization
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization
Statistics
title A unified global convergence analysis of multiplicative update rules for nonnegative matrix factorization
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-22T12%3A27%3A15IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20unified%20global%20convergence%20analysis%20of%20multiplicative%20update%20rules%20for%20nonnegative%20matrix%20factorization&rft.jtitle=Computational%20optimization%20and%20applications&rft.au=Takahashi,%20Norikazu&rft.date=2018-09-01&rft.volume=71&rft.issue=1&rft.spage=221&rft.epage=250&rft.pages=221-250&rft.issn=0926-6003&rft.eissn=1573-2894&rft_id=info:doi/10.1007/s10589-018-9997-y&rft_dat=%3Cproquest_cross%3E2015635524%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c382t-f9507295a0fbbe7c456608dc7c4a64777c3b70401c74bddb9d093012ca4746ae3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2015635524&rft_id=info:pmid/&rfr_iscdi=true