research-article

Factor-Bounded Nonnegative Matrix Factorization

Authors:

Lodewijk Brand,

Hua WangAuthors Info & Claims

ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 15, Issue 6

Article No.: 111, Pages 1 - 18

https://doi.org/10.1145/3451395

Published: 19 May 2021 Publication History

Abstract

Nonnegative Matrix Factorization (NMF) is broadly used to determine class membership in a variety of clustering applications. From movie recommendations and image clustering to visual feature extractions, NMF has applications to solve a large number of knowledge discovery and data mining problems. Traditional optimization methods, such as the Multiplicative Updating Algorithm (MUA), solves the NMF problem by utilizing an auxiliary function to ensure that the objective monotonically decreases. Although the objective in MUA converges, there exists no proof to show that the learned matrix factors converge as well. Without this rigorous analysis, the clustering performance and stability of the NMF algorithms cannot be guaranteed. To address this knowledge gap, in this article, we study the factor-bounded NMF problem and provide a solution algorithm with proven convergence by rigorous mathematical analysis, which ensures that both the objective and matrix factors converge. In addition, we show the relationship between MUA and our solution followed by an analysis of the convergence of MUA. Experiments on both toy data and real-world datasets validate the correctness of our proposed method and its utility as an effective clustering algorithm.

References

[1]

Hedy Attouch and Jérôme Bolte. 2009. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming 116, 1-2 (2009), 5–16.

Digital Library

[2]

Hedy Attouch, Jérôme Bolte, and Benar Fux Svaiter. 2013. Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Mathematical Programming 137, 1-2 (2013), 91–129.

[3]

Jérôme Bolte, Aris Daniilidis, and Adrian Lewis. 2007. The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization 17, 4 (2007), 1205–1223.

Digital Library

[4]

Deng Cai, Xiaofei He, Jiawei Han, and Thomas S. Huang. 2011. Graph regularized nonnegative matrix factorization for data representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 33, 8 (2011), 1548–1560.

Digital Library

[5]

Paul H. Calamai and Jorge J. Moré. 1987. Projected gradient methods for linearly constrained problems. Mathematical Programming 39, 1 (1987), 93–116.

Digital Library

[6]

Mulin Chen, Qi Wang, and Xuelong Li. 2018. Adaptive projected matrix factorization method for data clustering. Neurocomputing 306 (2018), 182–188.

[7]

Moody Chu, Fasma Diele, Robert Plemmons, and Stefania Ragni. 2004. Optimality, computation, and interpretation of nonnegative matrix factorizations. SIAM Journal on Matrix Analysis (2004).

[8]

Chris Ding, Xiaofeng He, and Horst D. Simon. 2005. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM, 606–610.

[9]

Chris Ding, Tao Li, and Michael I. Jordan. 2010. Convex and semi-nonnegative matrix factorizations. IEEE Transactions on Pattern Analysis and Machine Intelligence 32, 1 (2010), 45–55.

Digital Library

[10]

Chris Ding, Tao Li, Wei Peng, and Haesun Park. 2006. Orthogonal nonnegative matrix t-factorizations for clustering. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 126–135.

Digital Library

[11]

Hongchang Gao, Feiping Nie, Weidong Cai, and Heng Huang. 2015. Robust capped norm nonnegative matrix factorization: Capped norm NMF. In Proceedings of the 24th ACM International on Conference on Information and Knowledge Management. ACM, 871–880.

Digital Library

[12]

Quanquan Gu and Jie Zhou. 2009. Co-clustering on manifolds. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 359–368.

Digital Library

[13]

Xiaofei He and Partha Niyogi. 2004. Locality preserving projections. In Proceedings of the 16th International Conference on Neural Information Processing. ACM, 153–160.

[14]

Patrik O. Hoyer. 2004. Non-negative matrix factorization with sparseness constraints. Journal of Machine Learning Research 5 (2004), 1457–1469. https://jmlr.org/papers/volume5/hoyer04a/hoyer04a.pdf.

Digital Library

[15]

Kejun Huang, Nicholas D. Sidiropoulos, and Athanasios P. Liavas. 2016. A flexible and efficient algorithmic framework for constrained matrix and tensor factorization. IEEE Transactions on Signal Processing 64, 19 (2016), 5052–5065.

Digital Library

[16]

Hyunsoo Kim and Haesun Park. 2007. Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis. Bioinformatics 23, 12 (2007), 1495–1502.

Digital Library

[17]

Deguang Kong, Chris Ding, and Heng Huang. 2011. Robust nonnegative matrix factorization using l21-norm. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management. ACM, 673–682.

Digital Library

[18]

Hans Laurberg, Mads Græsbøll Christensen, Mark D. Plumbley, Lars Kai Hansen, and Søren Holdt Jensen. 2008. Theorems on positive data: On the uniqueness of NMF. Computational Intelligence and Neuroscience 2008 (2008), 764206. https://doi.org/10.1155/2008/764206

[19]

Daniel D. Lee and H. Sebastian Seung. 1999. Learning the parts of objects by non-negative matrix factorization. Nature 401, 6755 (1999), 788.

[20]

Daniel D. Lee and H. Sebastian Seung. 2001. Algorithms for non-negative matrix factorization. In Proceedings of the 13th International Conference on Neural Information Processing Systems. ACM, 556–562.

[21]

Xuelong Li, Mulin Chen, and Qi Wang. 2019. Discrimination-aware projected matrix factorization. IEEE Transactions on Knowledge and Data Engineering 32, 4 (2019), 809–814.

[22]

Chih-Jen Lin. 2007. Projected gradient methods for nonnegative matrix factorization. Neural Computation 19, 10 (2007), 2756–2779.

Digital Library

[23]

Kai Liu and Hua Wang. 2015. Robust multi-relational clustering via l1-norm symmetric nonnegative matrix factorization. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers), Vol. 2. 397–401.

[24]

Weixiang Liu, Kehong Yuan, and Datian Ye. 2008. Reducing microarray data via nonnegative matrix factorization for visualization and clustering analysis. Journal of Biomedical Informatics 41, 4 (2008), 602–606.

Digital Library

[25]

Lei Luo, Yanfu Zhang, and Heng Huang. 2020. Adversarial nonnegative matrix factorization. In Proceedings of the 37th International Conference on Machine Learning. PMLR, 6479–6488.

[26]

Alberto Pascual-Montano, Jose Maria Carazo, Kieko Kochi, Dietrich Lehmann, and Roberto D. Pascual-Marqui. 2006. Nonsmooth nonnegative matrix factorization (nsNMF). IEEE Transactions on Pattern Analysis and Machine Intelligence 28, 3 (2006), 403–415.

Digital Library

[27]

Anh Huy Phan and Andrzej Cichocki. 2008. Multi-way nonnegative tensor factorization using fast hierarchical alternating least squares algorithm (HALS). In Proceedings of the 2008 International Symposium on Nonlinear Theory and its Applications.

[28]

Meisam Razaviyayn, Mingyi Hong, and Zhi-Quan Luo. 2013. A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM Journal on Optimization 23, 2 (2013), 1126–1153.

[29]

Mikkel N. Schmidt and Rasmus K. Olsson. 2006. Single-channel speech separation using sparse non-negative matrix factorization. In Proceedings of the 9th International Conference on Spoken Language Processing.

[30]

Martin Slawski, Matthias Hein, and Pavlo Lutsik. 2013. Matrix factorization with binary components. Advances in Neural Information Processing Systems 26 (2013), 3210–3218. https://papers.nips.cc/paper/2013/file/226d1f15ecd35f784d2a20c3ecf56d7f-Paper.pdf.

Digital Library

[31]

Paris Smaragdis and Judith C. Brown. 2003. Non-negative matrix factorization for polyphonic music transcription. In Proceedings of the 2003 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics. IEEE, 177–180.

[32]

Norikazu Takahashi and Masato Seki. 2016. Multiplicative update for a class of constrained optimization problems related to NMF and its global convergence. In Proceedings of the 2016 24th European Signal Processing Conference. IEEE, 438–442.

[33]

Hua Wang, Heng Huang, Chris Ding, and Feiping Nie. 2013. Predicting protein–protein interactions from multimodal biological data sources via nonnegative matrix tri-factorization. Journal of Computational Biology 20, 4 (2013), 344–358.

[34]

Hua Wang, Feiping Nie, Heng Huang, and Chris Ding. 2011. Nonnegative matrix tri-factorization based high-order co-clustering and its fast implementation. In Proceedings of the 2011 IEEE 11th International Conference on Data Mining,. IEEE, 774–783.

Digital Library

[35]

Hua Wang, Feiping Nie, Heng Huang, and Fillia Makedon. 2011. Fast nonnegative matrix tri-factorization for large-scale data co-clustering. In Proceedings of the 22nd International Joint Conference on Artificial Intelligence.

Digital Library

[36]

Wei Xu, Xin Liu, and Yihong Gong. 2003. Document clustering based on non-negative matrix factorization. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 267–273.

Digital Library

[37]

Yangyang Xu and Wotao Yin. 2013. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM Journal on Imaging Sciences 6, 3 (2013), 1758–1789.

Digital Library

[38]

Felipe Yanez and Francis Bach. 2017. Primal-dual algorithms for non-negative matrix factorization with the Kullback–Leibler divergence. In Proceedings of the 2017 IEEE International Conference on Acoustics, Speech and Signal Processing,. IEEE, 2257–2261.

[39]

Rafal Zdunek. 2008. Data clustering with semi-binary nonnegative matrix factorization. In Proceedings of the International Conference on Artificial Intelligence and Soft Computing. Springer, 705–716.

Digital Library

[40]

Xiang Zhang, Naiyang Guan, Long Lan, Dacheng Tao, and Zhigang Luo. 2014. Box-constrained projective nonnegative matrix factorization via augmented Lagrangian method. In Proceedings of the 2014 International Joint Conference on Neural Networks. IEEE, 1900–1906.

[41]

Marinka Žitnik and Blaž Zupan. 2012. NIMFA: A Python library for nonnegative matrix factorization. Journal of Machine Learning Research 13, (2012), 849–853. https://www.jmlr.org/papers/volume13/zitnik12a/zitnik12a.pdf.

Digital Library

Cited By

Li XWang H(2024)On Mean-Optimal Robust Linear Discriminant AnalysisACM Transactions on Knowledge Discovery from Data10.1145/366550018:8(1-27)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3665500
Dornaika FEl Hajjar S(2024)An End-to-End Approach for Graph-Based Multi-View Data ClusteringIEEE Transactions on Big Data10.1109/TBDATA.2024.337135710:5(644-654)Online publication date: Oct-2024
https://doi.org/10.1109/TBDATA.2024.3371357
Peng CZhang PChen YKang ZChen CCheng Q(2024)Fine-Grained Bipartite Concept Factorization for Clustering2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02481(26254-26264)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02481
Show More Cited By

Index Terms

Factor-Bounded Nonnegative Matrix Factorization
1. Computing methodologies
  1. Machine learning
    1. Machine learning algorithms

Recommendations

Heuristics for exact nonnegative matrix factorization

The exact nonnegative matrix factorization (exact NMF) problem is the following: given an m-by-n nonnegative matrix X and a factorization rank r, find, if possible, an m-by-r nonnegative matrix W and an r-by-n nonnegative matrix H such that $$X = WH$$X=...
Quadratic nonnegative matrix factorization

In Nonnegative Matrix Factorization (NMF), a nonnegative matrix is approximated by a product of lower-rank factorizing matrices. Most NMF methods assume that each factorizing matrix appears only once in the approximation, thus the approximation is ...
Monotonous (semi-)nonnegative matrix factorization
CODS '15: Proceedings of the 2nd ACM IKDD Conference on Data Sciences

Nonnegative matrix factorization (NMF) factorizes a non-negative matrix into product of two non-negative matrices, namely a signal matrix and a mixing matrix. NMF suffers from the scale and ordering ambiguities. Often, the source signals can be ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Knowledge Discovery from Data

ACM Transactions on Knowledge Discovery from Data Volume 15, Issue 6

June 2021

474 pages

ISSN:1556-4681

EISSN:1556-472X

DOI:10.1145/3465438

Editor:
Charu Aggarwal
IBM T. J. Watson Research, USA

Issue’s Table of Contents

Copyright © 2021 Association for Computing Machinery.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2021

Accepted: 01 February 2021

Revised: 01 January 2021

Received: 01 July 2020

Published in TKDD Volume 15, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Science Foundation (NSF)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
309
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)7

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li XWang H(2024)On Mean-Optimal Robust Linear Discriminant AnalysisACM Transactions on Knowledge Discovery from Data10.1145/366550018:8(1-27)Online publication date: 21-May-2024
https://dl.acm.org/doi/10.1145/3665500
Dornaika FEl Hajjar S(2024)An End-to-End Approach for Graph-Based Multi-View Data ClusteringIEEE Transactions on Big Data10.1109/TBDATA.2024.337135710:5(644-654)Online publication date: Oct-2024
https://doi.org/10.1109/TBDATA.2024.3371357
Peng CZhang PChen YKang ZChen CCheng Q(2024)Fine-Grained Bipartite Concept Factorization for Clustering2024 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR52733.2024.02481(26254-26264)Online publication date: 16-Jun-2024
https://doi.org/10.1109/CVPR52733.2024.02481
Dornaika FEl Hajjar S(2024)Towards a unified framework for graph-based multi-view clusteringNeural Networks10.1016/j.neunet.2024.106197173(106197)Online publication date: May-2024
https://doi.org/10.1016/j.neunet.2024.106197
Guo YLi QLiang C(2024)The rise of nonnegative matrix factorization: Algorithms and applicationsInformation Systems10.1016/j.is.2024.102379123(102379)Online publication date: Jul-2024
https://doi.org/10.1016/j.is.2024.102379
Thanh OGillis N(2023)Identifiability of Polytopic Matrix Factorization2023 31st European Signal Processing Conference (EUSIPCO)10.23919/EUSIPCO58844.2023.10290012(1290-1294)Online publication date: 4-Sep-2023
https://doi.org/10.23919/EUSIPCO58844.2023.10290012
Shi LZhang ZFan ZXi CLi ZWu G(2023)Kernel Fisher Dictionary Transfer LearningACM Transactions on Knowledge Discovery from Data10.1145/358857517:8(1-17)Online publication date: 12-May-2023
https://dl.acm.org/doi/10.1145/3588575
Thanh OGillis NLecron F(2023)Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and ApplicationsIEEE Transactions on Signal Processing10.1109/TSP.2023.328970471(2434-2447)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TSP.2023.3289704
Liu HGuo YYin JGao ZNie L(2023)Review Polarity-Wise RecommenderIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2022.316378934:12(10039-10050)Online publication date: Dec-2023
https://doi.org/10.1109/TNNLS.2022.3163789
Fang ULi MLi JGao LJia TZhang Y(2023)A Comprehensive Survey on Multi-View ClusteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.327031135:12(12350-12368)Online publication date: 25-Apr-2023
https://dl.acm.org/doi/10.1109/TKDE.2023.3270311
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents