The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Fast coordinate descent methods with variable selection for non-negative matrix factorization
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Gradient-based learning applied to document recognition
Lecun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998) · Proceedings of the IEEE · doi:10.1109/5.726791 · Cited by 58,805
Cited by
Overlapping community detection at scale: a nonnegative matrix factorization approach
Yang, J., & Leskovec, J. (2013) · Proceedings of the sixth ACM international conference on Web search and data mining · doi:10.1145/2433396.2433471 · Cited by 852
Li, S.-Y., Jiang, Y., & Zhou, Z.-H. (2014) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v28i1.8973 · Cited by 431
Kim, J., He, Y., & Park, H. (2014) · Journal of Global Optimization · doi:10.1007/s10898-013-0035-4 · Cited by 352
Generalized Incomplete Multiview Clustering With Flexible Locality Structure Diffusion
Wen, J., Zhang, Z., Zhang, Z., Fei, L., & Wang, M. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2020.2987164 · Cited by 305
Scalable Coordinate Descent Approaches to Parallel Matrix Factorization for Recommender Systems
Yu, H.-F., Hsieh, C.-J., Si, S., & Dhillon, I. (2012) · 2012 IEEE 12th International Conference on Data Mining · doi:10.1109/icdm.2012.168 · Cited by 253
Self-citation
Metadata
- Authors
- Hsieh, C.-J., & Dhillon, I. S.
- Venue
- Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining
- Publisher
- ACM
- Published
- 2011-08-21
- Pages
- 1064-1072
- OpenAlex
- W2022712430
- Cited by
- 220
- References
- 1
- FWCI
- 9.30
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Fast coordinate descent methods with variable selection for non-negative matrix factorization. https://app.cochat.ai/papers/10.1145/2020408.2020577
- The paper
- Hsieh, C.-J., & Dhillon, I. S. (2011). Fast coordinate descent methods with variable selection for non-negative matrix factorization. Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. https://doi.org/10.1145/2020408.2020577
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.