An alternating direction algorithm for matrix completion with nonnegative factors
Open accessThe DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Abstract
This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
Learning the parts of objects by non-negative matrix factorization
Lee, D. D., & Seung, H. S. (1999) · Nature · doi:10.1038/44565 · Cited by 13,868
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Lee, D. D., & Seung, H. S. (2000) · neural information processing systems · Cited by 9,875
Robust principal component analysis?
Candès, E. J., Li, X., Ma, Y., & Wright, J. (2011) · Journal of the ACM · doi:10.1145/1970392.1970395 · Cited by 6,921
Paatero, P., & Tapper, U. (1994) · Environmetrics · doi:10.1002/env.3170050203 · Cited by 6,023
A Singular Value Thresholding Algorithm for Matrix Completion
Cai, J.-F., Candès, E. J., & Shen, Z. (2010) · SIAM Journal on Optimization · doi:10.1137/080738970 · Cited by 5,809
Parallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Exact Matrix Completion via Convex Optimization
Candès, E. J., & Recht, B. (2009) · Foundations of Computational Mathematics · doi:10.1007/s10208-009-9045-5 · Cited by 4,877
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Seung, D., & Lee, L.-W. (2001) · Cited by 4,753
Using collaborative filtering to weave an information tapestry
Goldberg, D., Nichols, D., Oki, B. M., & Terry, D. (1992) · Communications of the ACM · doi:10.1145/138859.138867 · Cited by 4,066
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
Recht, B., Fazel, M., & Parrilo, P. A. (2010) · SIAM Review · doi:10.1137/070697835 · Cited by 3,471
A dual algorithm for the solution of nonlinear variational problems via finite element approximation
Gabay, D., & Mercier, B. (1976) · Computers & Mathematics with Applications · doi:10.1016/0898-1221(76)90003-1 · Cited by 2,514
Multiplier and gradient methods
Hestenes, M. R. (1969) · Journal of Optimization Theory and Applications · doi:10.1007/bf00927673 · Cited by 2,446
The Power of Convex Relaxation: Near-Optimal Matrix Completion
Candes, E. J., & Tao, T. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2044061 · Cited by 2,060
Least squares formulation of robust non-negative factor analysis
Paatero, P. (1997) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/s0169-7439(96)00044-5 · Cited by 1,978
A New Alternating Minimization Algorithm for Total Variation Image Reconstruction
Wang, Y., Yang, J., Yin, W., & Zhang, Y. (2008) · SIAM Journal on Imaging Sciences · doi:10.1137/080724265 · Cited by 1,975 · cited 11×
“Section 2 reviews the ADM algorithm and presents an ADM-based algorithm for NMFC.”
MethodInfluentialSelf-citationCichocki, A., Zdunek, R., Phan, A. H., & Amari, S. (2009) · doi:10.1002/9780470747278 · Cited by 1,540
Algorithms and applications for approximate nonnegative matrix factorization
Berry, M. W., Browne, M., Langville, A. N., Pauca, V. P., & Plemmons, R. J. (2007) · Computational Statistics & Data Analysis · doi:10.1016/j.csda.2006.11.006 · Cited by 1,512
Wright, J. N., Ganesh, A., Rao, S., Peng, Y., & Ma, Y. (2009) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · Cited by 1,495
Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
Yin, W., Osher, S., Goldfarb, D., & Darbon, J. (2008) · SIAM Journal on Imaging Sciences · doi:10.1137/070703983 · Cited by 1,414
Self-citationGlowinski, R., & Marroco, A. (1975) · Revue française d'automatique, informatique, recherche opérationnelle. Analyse numérique · doi:10.1051/m2an/197509r200411 · Cited by 1,105
Fixed point and Bregman iterative methods for matrix rank minimization
Ma, S., Goldfarb, D., & Chen, L. (2011) · Mathematical Programming · doi:10.1007/s10107-009-0306-5 · Cited by 1,048
Fixed-Point Continuation for $\ell_1$-Minimization: Methodology and Convergence
Hale, E. T., Yin, W., & Zhang, Y. (2008) · SIAM Journal on Optimization · doi:10.1137/070698920 · Cited by 909
Self-citationWen, Z., Yin, W., & Zhang, Y. (2012) · Mathematical Programming Computation · doi:10.1007/s12532-012-0044-1 · Cited by 774
Self-citationPaatero, P. (1999) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.1999.10474853 · Cited by 756
The multiplier method of Hestenes and Powell applied to convex programming
Rockafellar, R. T. (1973) · Journal of Optimization Theory and Applications · doi:10.1007/bf00934777 · Cited by 705
On the convergence of the block nonlinear Gauss–Seidel method under convex constraints
Grippo, L., & Sciandrone, M. (2000) · Operations Research Letters · doi:10.1016/s0167-6377(99)00074-7 · Cited by 678
Semidefinite programming based algorithms for sensor network localization
Biswas, P., Lian, T.-C., Wang, T.-C., & Ye, Y. (2006) · ACM Transactions on Sensor Networks · doi:10.1145/1149283.1149286 · Cited by 631
Paatero, P. (1999) · Journal of Computational and Graphical Statistics · doi:10.2307/1390831 · Cited by 510
Interior-Point Method for Nuclear Norm Approximation with Application to System Identification
Liu, Z., & Vandenberghe, L. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090755436 · Cited by 490
Alternating direction augmented Lagrangian methods for semidefinite programming
Wen, Z., Goldfarb, D., & Yin, W. (2010) · Mathematical Programming Computation · doi:10.1007/s12532-010-0017-1 · Cited by 359
Self-citationAn Efficient TVL1 Algorithm for Deblurring Multichannel Images Corrupted by Impulsive Noise
Yang, J., Zhang, Y., & Yin, W. (2009) · SIAM Journal on Scientific Computing · doi:10.1137/080732894 · Cited by 336
Self-citationAdvances in Nonnegative Matrix and Tensor Factorization
Cichocki, A. S., Mørup, M., Smaragdis, P., Wang, W., & Zdunek, R. (2008) · Computational Intelligence and Neuroscience · doi:10.1155/2008/852187 · Cited by 32
Cited by
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
Wang, Y., Yin, W., & Zeng, J. (2019) · Journal of Scientific Computing · doi:10.1007/s10915-018-0757-z · Cited by 1,268
Self-citationStructure-Revealing Low-Light Image Enhancement Via Robust Retinex Model
Li, M., Liu, J., Yang, W., Sun, X., & Guo, Z. (2018) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2810539 · Cited by 1,245
Xu, Y., & Yin, W. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120887795 · Cited by 1,160
Self-citationAn Augmented Linear Mixing Model to Address Spectral Variability for Hyperspectral Unmixing
Hong, D., Yokoya, N., Chanussot, J., & Zhu, X. X. (2019) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2878958 · Cited by 948
Wen, Z., Yin, W., & Zhang, Y. (2012) · Mathematical Programming Computation · doi:10.1007/s12532-012-0044-1 · Cited by 774
Self-citation
Metadata
- Authors
- Xu, Y., Yin, W., Wen, Z., & Zhang, Y.
- Venue
- Frontiers of Mathematics in China
- Published
- 2012-04
- Volume
- 7
- Issue
- 2
- Pages
- 365-384
- ISSN
- 1673-3452 (ISSN-L)
- 1673-3576
- OpenAlex
- W1846534543
- Cited by
- 339
- References
- 32
- FWCI
- 15.57
- Type
- journal article
- Language
- en
- Open access
- green
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
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.