poster

Fast coordinate descent methods with variable selection for non-negative matrix factorization

Authors:

Inderjit S. DhillonAuthors Info & Claims

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

Pages 1064 - 1072

https://doi.org/10.1145/2020408.2020577

Published: 21 August 2011 Publication History

Abstract

Nonnegative Matrix Factorization (NMF) is an effective dimension reduction method for non-negative dyadic data, and has proven to be useful in many areas, such as text mining, bioinformatics and image processing. NMF is usually formulated as a constrained non-convex optimization problem, and many algorithms have been developed for solving it. Recently, a coordinate descent method, called FastHals, has been proposed to solve least squares NMF and is regarded as one of the state-of-the-art techniques for the problem. In this paper, we first show that FastHals has an inefficiency in that it uses a cyclic coordinate descent scheme and thus, performs unneeded descent steps on unimportant variables. We then present a variable selection scheme that uses the gradient of the objective function to arrive at a new coordinate descent method. Our new method is considerably faster in practice and we show that it has theoretical convergence guarantees. Moreover when the solution is sparse, as is often the case in real applications, our new method benefits by selecting important variables to update more often, thus resulting in higher speed. As an example, on a text dataset RCV1, our method is 7 times faster than FastHals, and more than 15 times faster when the sparsity is increased by adding an L1 penalty. We also develop new coordinate descent methods when error in NMF is measured by KL-divergence by applying the Newton method to solve the one-variable sub-problems. Experiments indicate that our algorithm for minimizing the KL-divergence is faster than the Lee & Seung multiplicative rule by a factor of 10 on the CBCL image dataset.

References

[1]

M. Berry, M. Browne, A. Langville, P. Pauca, and R. Plemmon. Algorithms and applications for approximate nonnegative matrix factorization. Computational Statistics and Data Analysis, 2007. Submitted.

[2]

D. Bersekas and J. Tsitsiklis. Parallel and distributed computation. Prentice-Hall, 1989.

Digital Library

[3]

A. Cichocki and A.-H. Phan. Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE Transaction on Fundamentals, E92-A(3):708--721, 2009.

[4]

E. Gaussier and C. Goutte. Relation between PLSA and NMF and implications. 28th Annual International ACM SIGIR Conference, 2005.

Digital Library

[5]

E. F. Gonzales and Y. Zhang. Accelerating the Lee-Seung algorithm for non-negative matrix factorization. Technical report, Department of Computational and Applied Mathematics, Rice University, 2005.

[6]

L. Grippo and M. Sciandrone. On the convergence of the block nonlinear Gauss-Seidel method under convex constraints. Operations Research Letters, 26:127--136, 2000.

Digital Library

[7]

P. O. Hoyer. Non-negative sparse coding. In Proceedings of IEEE Workshop on Neural Networks for Signal Processing, pages 557--565, 2002.

[8]

P. O. Hoyer. Non-negative matrix factorization with sparseness constraints. Journal of Machine Learning Research, 5:1457--1469, 2004.

Digital Library

[9]

C.-J. Hsieh and I. S. Dhillon. Fast coordinate descent methods with variable selection for non-negative matrix factorization. Department of Computer Science TR-11-06, University of Texas at Austin, 2011.

[10]

D. Kim, S. Sra, and I. S. Dhillon. Fast Newton-type methods for the least squares nonnegative matrix appoximation problem. Proceedings of the Sixth SIAM International Conference on Data Mining, pages 343--354, 2007.

[11]

J. Kim and H. Park. Non-negative matrix factorization based on alternating non-negativity constrained least squares and active set method. SIAM Journal on Matrix Analysis and Applications, 30(2):713--730, 2008.

Digital Library

[12]

J. Kim and H. Park. Toward faster nonnegative matrix factorization: A new algorithm and comparisons. Proceedings of the IEEE International Conference on Data Mining, pages 353--362, 2008.

Digital Library

[13]

Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278--2324, November 1998. MNIST database available at http://yann.lecun.com/exdb/mnist/.

[14]

D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788--791, 1999.

[15]

D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 556--562. MIT Press, 2001.

[16]

D. D. Lewis, Y. Yang, T. G. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5:361--397, 2004.

Digital Library

[17]

Y. Li and S. Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Probl. Imaging, 3(3):487--503, 2009.

[18]

C.-J. Lin. Projected gradient methods for non-negative matrix factorization. Neural Computation, 19:2756--2779, 2007.

Digital Library

[19]

C. Liu, H. chih Yang, J. Fan, L.-W. He, and Y.-M. Wang. Distributed Non-negative Matrix Factorization for Web-Scale Dyadic Data Analysis on MapReduce. 2010.

[20]

P. Paatero and U. Tapper. Positive matrix factorization: A non-negative factor model with optimal utilization of error. Environmetrics, 5:111--126, 1994.

[21]

S. Perkins, K. Lacker, and J. Theiler. Grafting: Fast, incremental feature selection by gradient descent in function space. Journal of Machine Learning Research, 3:1333--1356, 2003.

Digital Library

[22]

J. Piper, P. Pauca, R. Plemmons, and M. Giffin. Object characterization from spectral data using nonnegative factorization and information theory. In Proceedings of AMOS Technical Conference, 2004.

[23]

R. Zdunek and A. Cichocki. Non-negative matrix factorization with quasi-newton optimization. Eighth International Conference on Artificial Intelligence and Soft Computing, ICAISC, pages 870--879, 2006.

Digital Library

Cited By

Hajibabaei HSeydi VKoochari A(2024)A motif-based probabilistic approach for community detection in complex networksJournal of Intelligent Information Systems10.1007/s10844-024-00850-362:5(1285-1303)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10844-024-00850-3
Bahadori SMirzaie MNooraei Abadeh M(2024)A multi-objective optimization approach for overlapping dynamic community detectionSoft Computing10.1007/s00500-024-09895-628:19(11323-11342)Online publication date: 24-Jul-2024
https://doi.org/10.1007/s00500-024-09895-6
Si TVan Hung TNgoc DLe Q(2024)A Study on Parallel Recommender System with Stream Data Using Stochastic Gradient DescentSoftware Engineering and Management: Theory and Application10.1007/978-3-031-55174-1_5(55-68)Online publication date: 3-May-2024
https://doi.org/10.1007/978-3-031-55174-1_5
Show More Cited By

Index Terms

Fast coordinate descent methods with variable selection for non-negative matrix factorization

Recommendations

Fast bregman divergence NMF using taylor expansion and coordinate descent
KDD '12: Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining

Non-negative matrix factorization (NMF) provides a lower rank approximation of a matrix. Due to nonnegativity imposed on the factors, it gives a latent structure that is often more physically meaningful than other lower rank approximations such as ...
New SVD based initialization strategy for non-negative matrix factorization

We give a new method to determine the rank of the factorization for NMF algorithms.We propose a novel method SVD-NMF to enhance initialization for NMF.The compute process is cheap.Numerical results show that SVD-NMF convergent faster than NNDSVD and ...
Non-negative Matrix Factorization for Binary Data
IC3K 2015: Proceedings of the International Joint Conference on Knowledge Discovery, Knowledge Engineering and Knowledge Management

We propose the Logistic Non-negative Matrix Factorization for decomposition of binary data. Binary data

are frequently generated in e.g. text analysis, sensory data, market basket data etc. A common method for

analysing non-negative data is the Non-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining

August 2011

1446 pages

ISBN:9781450308137

DOI:10.1145/2020408

General Chair:
Chid Apte
IBM Research
,
Program Chairs:
Joydeep Ghosh
UT Austin
,
Padhraic Smyth
UC Irvine

Copyright © 2011 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 August 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

KDD '11

Sponsor:

KDD '11: The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 21 - 24, 2011

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 1,133 of 8,635 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

141
Total Citations
View Citations
870
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)4

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hajibabaei HSeydi VKoochari A(2024)A motif-based probabilistic approach for community detection in complex networksJournal of Intelligent Information Systems10.1007/s10844-024-00850-362:5(1285-1303)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10844-024-00850-3
Bahadori SMirzaie MNooraei Abadeh M(2024)A multi-objective optimization approach for overlapping dynamic community detectionSoft Computing10.1007/s00500-024-09895-628:19(11323-11342)Online publication date: 24-Jul-2024
https://doi.org/10.1007/s00500-024-09895-6
Si TVan Hung TNgoc DLe Q(2024)A Study on Parallel Recommender System with Stream Data Using Stochastic Gradient DescentSoftware Engineering and Management: Theory and Application10.1007/978-3-031-55174-1_5(55-68)Online publication date: 3-May-2024
https://doi.org/10.1007/978-3-031-55174-1_5
Yuan GKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)Coordinate descent methods for fractional minimizationProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3620104(40488-40518)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3620104
Li XTyagi A(2023)Block-Active ADMM to Minimize NMF with Bregman DivergencesSensors10.3390/s2316722923:16(7229)Online publication date: 17-Aug-2023
https://doi.org/10.3390/s23167229
Carbonetto PLuo KSarkar AHung ATayeb KPott SStephens M(2023)GoM DE: interpreting structure in sequence count data with differential expression analysis allowing for grades of membershipGenome Biology10.1186/s13059-023-03067-924:1Online publication date: 19-Oct-2023
https://doi.org/10.1186/s13059-023-03067-9
Lu ZNie FWang RLi X(2023)A Differentiable Perspective for Multi-View Spectral Clustering With Flexible ExtensionIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2022.322497845:6(7087-7098)Online publication date: 1-Jun-2023
https://doi.org/10.1109/TPAMI.2022.3224978
Gaydamaka ASamuylov AMoltchanov DAshraf MTan BKoucheryavy Y(2023)Dynamic Topology Organization and Maintenance Algorithms for Autonomous UAV SwarmsIEEE Transactions on Mobile Computing10.1109/TMC.2023.329303423:5(4423-4439)Online publication date: 6-Jul-2023
https://dl.acm.org/doi/10.1109/TMC.2023.3293034
Deng PLi TWang DWang HPeng HHorng S(2023)Multi-view clustering guided by unconstrained non-negative matrix factorizationKnowledge-Based Systems10.1016/j.knosys.2023.110425266:COnline publication date: 22-Apr-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110425
Brie DGillis NMoussaoui S(2023)Non‐negative Matrix FactorizationSource Separation in Physical‐Chemical Sensing10.1002/9781119137252.ch3(103-149)Online publication date: 13-Oct-2023
https://doi.org/10.1002/9781119137252.ch3
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents