An alternating direction algorithm for matrix completion with nonnegative factors

doi:10.1007/s11464-012-0194-5

Front Math Chin

2012, Vol. 7

Issue (2) : 365-384 https://doi.org/10.1007/s11464-012-0194-5

RESEARCH ARTICLE

An alternating direction algorithm for matrix completion with nonnegative factors

Yangyang XU¹, Wotao YIN¹(

), Zaiwen WEN², Yin ZHANG¹

1. Department of Computational and Applied Mathematics, Rice University, Houston, TX 77005, USA; 2. Department of Mathematics and Institute of Natural Sciences, Shanghai Jiao Tong University, Shanghai 200240, China

Download: PDF(538 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

Keywords nonnegative matrix factorization matrix completion alternating direction method hyperspectral unmixing

Corresponding Author(s): YIN Wotao,Email:wotao.yin@rice.edu

Issue Date: 01 April 2012

Cite this article:

Yangyang XU,Wotao YIN,Zaiwen WEN, et al. An alternating direction algorithm for matrix completion with nonnegative factors[J]. Front Math Chin, 2012, 7(2): 365-384.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-012-0194-5
https://academic.hep.com.cn/fmc/EN/Y2012/V7/I2/365

1	Berry M W, Browne M, Langville A N, Pauca V P, Plemmons R J. Algorithms and applications for approximate nonnegative matrix factorization. Comput Statist Data Anal , 2007, 52(1): 155-173 doi: 10.1016/j.csda.2006.11.006
2	Bertsekas D P, Tsitsiklis J N. Parallel and Distributed Computation: Numerical Methods. Upper Saddle River: Prentice-Hall, Inc, 1989
3	Biswas P, Lian T C, Wang T C, Ye Y. Semidefinite programming based algorithms for sensor network localization. ACM Trans Sensor Networks , 2006, 2(2): 188-220 doi: 10.1145/1149283.1149286
4	Cai J F, Candes E J, Shen Z. A singular value thresholding algorithm for matrix completion export. SIAM J Optim , 2010, 20: 1956-1982 doi: 10.1137/080738970
5	Cand`es E J, Li X, Ma Y, Wright J. Robust principal component analysis? J ACM, 2011, 58(3): 11
6	Cand`es E J, Recht B. Exact matrix completion via convex optimization. Found Comput Math , 2009, 9(6): 717-772 doi: 10.1007/s10208-009-9045-5
7	Cand`es E J, Tao T. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans Inform Theory , 2010, 56(5): 2053-2080 doi: 10.1109/TIT.2010.2044061
8	Cichocki A, Morup M, Smaragdis P, Wang W, Zdunek R. Advances in Nonnegative Matrix and Tensor Factorization. Computational Intelligence Neuroscience . New York: Hindawi Publishing Corporation, 2008
9	Cichocki A, Zdunek R, Phan A H, Amari S. Nonnegative Matrix and Tensor Factorizations—Applications to Exploratory Multiway Data Analysis and Blind Source Separation. Hoboken: John Wiley & Sons, Ltd, 2009
10	Fazel M. Matrix Rank Minimization with Applications. PhD Thesis, Stanford University . 2002
11	Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl , 1976, 2(1): 17-40 doi: 10.1016/0898-1221(76)90003-1
12	Glowinski R, Marrocco A. Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires. Rev Francaise dAut Inf Rech Oper , 1975, 41-76
13	Goldberg D, Nichols D, Oki B M, Terry D. Using collaborative filtering to weave an information tapestry. Commun ACM , 1992, 35(12): 61-70 doi: 10.1145/138859.138867
14	Goldfarb D, Ma S, Wen Z. Solving low-rank matrix completion problems efficiently. In: Proceedings of 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, Illinois . 2009 doi: 10.1109/ALLERTON.2009.5394884
15	Grippo L, Sciandrone M. On the convergence of the block nonlinear Gauss-Seidel method under convex constraints. Oper Res Lett , 2000, 26(3): 127-136 doi: 10.1016/S0167-6377(99)00074-7
16	Hale E T, YinW, Zhang Y. Fixed-point continuation for l1-minimization: methodology and convergence. SIAM J Optim , 2008, 19(3): 1107-1130 doi: 10.1137/070698920
17	Hestenes M R. Multiplier and gradient methods. J Optim Theory Appl , 1969, 4(5): 303-320 doi: 10.1007/BF00927673
18	Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization. Nature , 1999, 401(6755): 788-791 doi: 10.1038/44565
19	Lee D D, Seung H S. Algorithms for non-negative matrix factorization. Adv Neural Inf Process Syst , 2001, 13: 556-562
20	Liu Z, Vandenberghe L. Interior-point method for nuclear norm approximation with application to system identification. SIAM J Matrix Anal Appl , 2009, 31(3): 1235-1256 doi: 10.1137/090755436
21	Ma S, Goldfarb D, Chen L. Fixed point and Bregman iterative methods for matrix rank minimization. Math Program, Ser A , 2011, 128(1-2): 321-353
22	Paatero P. Least squares formulation of robust non-negative factor analysis. Chemometrics Intell Lab Syst , 1997, 37(1): 23-35 doi: 10.1016/S0169-7439(96)00044-5
23	Paatero P. The multilinear engine: A table-driven, least squares program for solving multilinear problems, including the n-way parallel factor analysis model. J Comput Graph Statist , 1999, 8(4): 854-888 doi: 10.2307/1390831
24	Paatero P, Tapper U. Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics , 1994, 5(2): 111-126 doi: 10.1002/env.3170050203
25	Powell M J D. A method for nonlinear constraints in minimization problems. In: Fletcher R, ed. Optimization . New York: Academic Press, 1969, 283-298
26	Recht B, Fazel M, Parrilo P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Review , 2010, 52(3): 471-501 doi: 10.1137/070697835
27	Rockafellar R T. The multiplier method of Hestenes and Powell applied to convex programming. J Optim Theory Appl , 1973, 12(6): 555-562 doi: 10.1007/BF00934777
28	Wang Y, Yang J, Yin W, Zhang Y. A new alternating minimization algorithm for total variation image reconstruction. SIAM J Imaging Sci , 2008, 1(3): 248-272 doi: 10.1137/080724265
29	Wen Z, Goldfarb D, Yin W. Alternating direction augmented Lagrangian methods for semidefinite programming. Math Program Comput , 2010, 2(3-4): 203-230 doi: 10.1007/s12532-010-0017-1
30	Wen Z, Yin W, Zhang Y. Solving a low-rank factorization model for matrix completion by a non-linear successive over-relaxation algorithm. Rice Univ CAAM Technical Report TR 10-07 , 2010
31	Yang J, Yuan X. Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Math Comp (to appear)
32	Yang J, Zhang Y, Yin W. An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise. SIAM J Sci Comput , 2008, 31: 2842-2865 doi: 10.1137/080732894
33	Yin W, Osher S, Goldfarb D, Darbon J. Bregman iterative algorithms for 1-minimization with applications to compressed sensing. SIAM J Imaging Sci , 2008, 1(1): 143-168 doi: 10.1137/070703983
34	Zhang Y. An alternating direction algorithm for nonnegative matrix factorization. Rice Technical Report TR 10-03 , 2010

[1]	Ke GUO, Deren HAN, David Z. W. WANG, Tingting WU. Convergence of ADMM for multi-block nonconvex separable optimization models[J]. Front. Math. China, 2017, 12(5): 1139-1162.
[2]	Xingju CAI, Yannan CHEN, Deren HAN. Nonnegative tensor factorizations using an alternating direction method[J]. Front Math Chin, 2013, 8(1): 3-18.
[3]	Bingsheng HE, Zheng PENG, Xiangfeng WANG. Proximal alternating direction-based contraction methods for separable linearly constrained convex optimization[J]. Front Math Chin, 2011, 6(1): 79-114.

Viewed

Full text

Abstract

Cited

Shared

Discussed