An alternating direction algorithm for matrix completion with nonnegative factors

By Yangyang Xu, Wotao Yin, Zaiwen Wen, Yin Zhang. Frontiers of Mathematics in China, 2011

376 citations recorded by the source corpus.

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.

Subfields: Aerospace Engineering, Computational Mechanics, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/4503f964b36903f9e27d805ab9f03bd7ffe4d66d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Structure-Revealing Low-Light Image Enhancement Via Robust Retinex Model (2018, background): “of ADM for non-convex optimization problems [30], [31].”
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems (2014, result): “This is in contrast to the existi ng analysis of the nonconvex ADMM algorithms [27,33,35].”
Group sparse optimization by alternating direction method (2013, background): “, s } , (15) where y ∈ R, and Agi represents the submatrix collecting columns of A that corresponds to the i-th group.”
A Block Coordinate Descent Method for Regularized Multiconvex Optimization with Applications to Nonnegative Tensor Factorization and Completion (2013, methodology): “In this subsection, we compare APG-MC and the ADMbased algorithm (ADM-MC) proposed in [74] on the hyperspectral data used in last test.”
Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm (2012, methodology): “A possible acceleration technique may involve applying an extension of the classic augmented-Lag rangian-based alternating direction method (ADM) for convex optimization to the factorization model (see [29, 35 , 39] for such ADM extensions).”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, methodology): “C) Matrix decomposition ADMM has also been applied to solve matrix related problems, such as sparse principle component analysis (PCA) [27], matrix decomposition [55,62], matrix completion [8], matrix recovery [44], non-negative matrix factorization [77,72,57] and background/foreground extraction [9”
Parallel matrix factorization for low-rank tensor completion (2013, neutral): “To recover a low-rank tensor from its partially observed entries, one can unfold it into a matrix and apply a low-rank matrix completion algorithm such as FPCA [17], APGL [24], LMaFit [27], the alternating direction method [2, 31], the (cid:96) q minimization method [13], and so on.”
LR3M: Robust Low-Light Enhancement via Low-Rank Regularized Retinex Model (2020, methodology): “Then, we can easily solve it to obtain the evaluated L : 2) Solution to R-Problem (Reﬂectance Estimation): After obtaining a desirable L , we compute R : An alternating direction minimization algorithm [39] is provided to effectively optimize this objective function.”
An Augmented Linear Mixing Model to Address Spectral Variability for Hyperspectral Unmixing (2018, methodology): “ADMM-based optimization problem has been successfully applied in [40] [41] [42].”