An alternating direction algorithm for matrix completion with nonnegative factors

Yangyang Xu, Wotao Yin, Zaiwen Wen, Yin Zhang

Research output: Contribution to journalArticlepeer-review

177 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)365-384
Number of pages20
JournalFrontiers of Mathematics in China
Volume7
Issue number2
DOIs
StatePublished - Apr 2012

Bibliographical note

Funding Information:
Acknowledgements The authors are grateful to Dr. Junping Wang and an anonymous referee for their valuable comments and suggestions. The work of Y. Xu and W. Yin was supported in part by NSF Grants DMS-07-48839 and ECCS-1028790, ONR Grant N00014-08-1-1101, and ARL and ARO grant W911NF-09-1-0383. The work of Z. Wen was supported in part by NSF DMS-0439872 through UCLA IPAM and the National Natural Science Foundation of China (Grant No. 11101274). The work of Y. Zhang was supported in part by NSF DMS-0811188 and ONR grant N00014-08-1-1101.

Keywords

  • alternating direction method
  • hyperspectral unmixing
  • matrix completion
  • nonnegative matrix factorization

Fingerprint

Dive into the research topics of 'An alternating direction algorithm for matrix completion with nonnegative factors'. Together they form a unique fingerprint.

Cite this